[Date Prev][Date Next][Date Index]

Talk announcement: Monday, January 21, 2019, 16:00 c.t.: Francesco Scarcello "Tree projection width and fixed-parameter tractable queries"

Dear all,

the Research Unit "Databases and Artificial Intelligence" cordially invites you to the following talk:


Speaker: Prof. Dr. Francesco Scarcello

University of Calabria, Rende, Italy


DATE:   Monday, January 21, 2019

TIME:   16:00 c.t.

VENUE: Seminarraum von Neumann, Favoritenstraße 9-11, 1040 Wien, RoomNo.:  HBEG16
       (access from yard)



Tree projection width and fixed-parameter tractable queries



Identifying the frontier of tractability for conjunctive queries is a long-standing question in database theory. Recent advances in structural decomposition methods provide important answers regarding the fixed-parameter tractability of conjunctive queries, and efficient algorithms based on decomposition methods have been implemented in database management systems. However, for classes of instances where we have information on the data, such as functional dependencies or the more general degree constraints, there is still an important gap between the ideal information-theoretic bound and the performances of the available algorithms. Moreover, it was open whether the best possible bound is computable or not.

In this work, we revisit and generalize purely structural and degree-aware bounds, by using the classical and powerful notion of tree projection, where the decompositions are based on the solutions of sub-problems of the given instance. The new notions are parameterized by a desired level of uniformity, where the best width is obtained in the theoretical perfectly uniform case. We thus get a finer hierarchy of bounds, which can be tuned by acting on this parameter. The more powerful variant of the tree-projection width, called full tree-projection width, is computable and is at most the entropic degree-aware submodular width. The two widths coincide asymptotically, that is, for classes with unbounded values.

A crucial property of decomposition methods is to represent in a compact way the query answers of a given instance, in the form of  an equivalent acyclic query. This way, query answers can be computed easily from the decompositions, and can be enumerated in linear time (with respect to the output size). We show that the notion of full tree-projection width is tight with respect to this acyclic-representation power. These results can be easily combined with tools developed for structural decomposition methods, in particular for enumerating answers of queries with existential quantifiers.


best regards
Reinhard Pichler

TU Wien
Institut für Logic & Computation
Favoritenstr. 9 - 11/ 192-02
A-1040 Wien
TEL.: +43 1 58801 18403

DVR 0005886