Semantic Optimization of Conjunctive Queries

8^th January 2019, 13:00 Ashton Lecture Theater
Dr. Andreas Pieris
School of Informatics
Laboratory for Foundations of Computer Science
University of Edinburgh

Abstract

This talk will report on recent advances in semantic query optimization focussing 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 classical notion of acyclicity. We will investigate the problem of reformulating a query into one of bounded generalized hypertreewidth. Furthermore, we will discuss whether knowing that such a reformulation exists alleviates the cost of query evaluation. The above issues will be examined both for the constraint-free case, and the case where integrity constraints are present.