Checking conjunctive query containment under relational constraints
Andrea Cali
University of Bozen - Bolzano

Abstract: Containment of queries is a fundamental issue in query optimisation, since it is necessary to test equivalence among queries. In this talk we shall focus on conjunctive queries, and we will address the problem of query containment in the presence of dependencies (constraints) on the database schema. We will show algorithms for containment and complexity results first with a relational schema, with inclusion and functional dependencies expressed over it, and then when the schema is expressed in a conceptual model. We show how far we can go with expressiveness of constraints before we get into undecidability of query containment, and we provide algorithms for query containment and complexity results for different decidable cases, that cover most practical situations.

back to the list of talks