On Low Treewidth Approximations of Conjunctive Queries

Pablo Barcelo, Leonid Libkin, Miguel Romero

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We recently initiated the study of approximations of conjunctive queries within classes that admit tractable query evaluation (with respect to combined complexity). Those include classes of acyclic, bounded treewidth, or bounded hypertreewidth queries. Such approximations are always guaranteed to exist. However, while for acyclic and bounded hypertreewidth queries we have shown a number of examples of interesting approximations, for queries of bounded treewidth the study had been restricted to queries over graphs, where such approximations usually trivialize. In this note we show that for relations of arity greater than two, the notion of low treewidth approximations is a rich one, as many queries possess them. In fact we look at approximations of queries of maximum possible treewidth by queries of minimum possible treewidth (i.e., one), and show that even in this case the structure of approximations remain rather rich as long as input relations are not binary.
Original languageEnglish
Title of host publicationProceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management
Number of pages11
Publication statusPublished - 2012


Dive into the research topics of 'On Low Treewidth Approximations of Conjunctive Queries'. Together they form a unique fingerprint.

Cite this