Tree projection width and fixed-parameter tractable queries

VCLA hosted a talk by Francesco Scarcello

ABSTRACT

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.

Francesco Scarcello, University of Calabria