- Expanded acyclic queries: Containment and an application in explaining missing answers
- Award date
- 12 February 2016
- Number of pages
- Document type
- PhD thesis
- Faculty of Science (FNWI)
- Informatics Institute (IVI)
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.
- Research conducted at: Universiteit van Amsterdam
Series: SIKS dissertation series 2016-05
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.