On low treewidth approximations of conjunctive queries

Pablo Barceló, Leonid Libkin, Miguel Romero

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


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
Pages (from-to)91-101
Number of pages11
JournalCEUR Workshop Proceedings
StatePublished - 2012
Externally publishedYes
Event6th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2012 - Ouro Preto, Brazil
Duration: 27 Jun 201230 Jun 2012

Cite this