View publication
| Title | On Low Treewidth Approximations of Conjunctive Queries |
| Authors | Pablo Barceló, Leonid Libkin, Miguel Romero |
| Publication date | 2012 |
| Abstract | We recently initiated the study of approximations of con- junctive 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 approxi- mations 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 approxima- tions remain rather rich as long as input relations are not binary. |
| Pages | 91-101 |
| Conference name | Alberto Mendelzon International Workshop on Foundations of Data Management |
| Publisher | CEUR Publications |
| Reference URL |
|