Semantic Optimization in Tractable Classes of Conjunctive Queries

Pablo Barceló, Andreas Pieris, Miguel Romero

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

This paper reports on recent advances in semantic query optimization. We focus on the core class of conjunctive queries (CQs). Since CQ evaluation is NP-complete, a long line of research has concentrated on identifying fragments of CQs that can be efficiently evaluated. One of the most general such restrictions corresponds to bounded generalized hypertreewidth, which extends the notion of acyclicity. Here we discuss the problem of reformulating a CQ into one of bounded generalized hypertreewidth. Furthermore, we study whether knowing
that such a reformulation exists alleviates the cost of CQ evaluation. In case a CQ cannot be reformulated as one of bounded generalized hypertreewidth, we discuss how it can be approximated in an optimal way. All the above issues are examined both for the constraint-free case, and the case where constraints, in fact, tuple-generating and equality-generating dependencies, are present.
Original languageEnglish
Pages (from-to)5-17
Number of pages13
JournalACM SIGMOD Record
Issue number2
Publication statusPublished - 1 Jun 2017


Dive into the research topics of 'Semantic Optimization in Tractable Classes of Conjunctive Queries'. Together they form a unique fingerprint.

Cite this