Expanded acyclic queries: Containment and an application in explaining missing answers

The first part of this thesis concerns the query containment problem, a fundamental static analysis problem in database theory. Given two queries in a language under consideration, the containment problem is to decide whether the answers of one query form a subset of the answers of the other one, over arbitrary databases. This problem finds applications in query optimization, query answering using views, query answering under constraints, etc. Because of its importance, the containment problem has been thoroughly studied for various query languages and data models in the past.
In this thesis we continue to study the containment problem for various query languages over trees and relational databases that share one structural property — acyclicity. Namely, we consider:
1) Conjunctive and Positive Xpath queries interpreted on trees expanded with negation and attribute value comparisons;
2) Tree Patterns expanded with the conditional descendant axis, interpreted over trees; and
3) Acyclic conjunctive queries expanded with atomic negation and arithmetic comparisons over relational structures.
We obtain complexity bounds for the containment problem for these languages.
The second part of the dissertation proposes a new formal framework for why-not explanations. Our why-not explanations leverage concepts from an ontology to provide high-level and meaningful reasons for why certain data is missing from the result of a query. In this framework, we are interested in finding most general explanations relative to an ontology. We first address the problem of extracting an ontology from the database instance or schema. We show that this problem can be casted as the containment problem and provide the complexity analysis of it. Then we address the problem of computing a most general explanation. We study the complexity of this problem and associated problems, and present concrete algorithms for computing why-not explanations.