Projects per year
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 language  English 

Title of host publication  Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management 
Pages  91101 
Number of pages  11 
Publication status  Published  2012 
Fingerprint
Dive into the research topics of 'On Low Treewidth Approximations of Conjunctive Queries'. Together they form a unique fingerprint.Projects
 2 Finished

XML with Incomplete Information: Representation, Querying and Applications
1/09/09 → 30/11/13
Project: Research

Heterogeneous and Permanent data
Buneman, P., Fan, W., Libkin, L. & Viglas, S.
1/03/08 → 29/02/12
Project: Research