- 127 views
- 430 downloads
Chase-Based Ontology Mediated Query Answering: Increasing Expressiveness and Performance
-
- Author / Creator
- Karimi, Arash
-
In this dissertation we consider the problem of ontology-based data access when the underlying ontology language is represented using tuple-generating dependencies (a term used in theory of databases), also known as existential rules (in the artificial intelligence literature). This problem is prominent and challenging in knowledge representation and reasoning, as it allows one to gain semantic knowledge in the presence of unknown entities that are not explicitly defined in the database. Unsurprisingly, the problem of query answering with these rules is undecidable, which means that there is no algorithm in general for which queries can be answered using finite resources.
In this dissertation we build on top of the state of the art and introduce classes of rules for which the above problem is decidable with the goal of increasing expressiveness as well as improving performance.
The chase procedure provides a bottom-up method in dealing with the above problem, which comes in many variants.
Toward achieving expressiveness improvements for reasoning with existential rules as the underlying ontology language, in this investigation we consider the restricted variant of the chase procedure.
This procedure is an indispensable tool for several database applications, where its termination guarantees decidability of these tasks. Most previous studies have focused on the {\em Skolem chase variant} and its termination analysis. It is known that the restricted chase variant is a more powerful tool in termination analysis provided a database is given. But all-instance termination (termination for any database)
presents a challenge since the critical database and similar techniques developed for the Skolem chase variant do not work for restricted chase.
In the first part of this dissertation, we develop a novel technique to characterize the activeness of all possible cycles of a certain length for the restricted chase, which leads to the formulation of a framework of parametrized class of the finite restricted chase, called k-safe rule sets. This approach is applicable to any class of finite Skolem chase identified with a condition of acyclicity.
More generally, we show that the approach can be extended to the hierarchy of bounded rule sets previously only studied for Skolem chase. Experiments on a collection of ontologies from the web show the applicability of the proposed methods on real-world ontologies.
For the direction of performance improvements for query answering based on the chase algorithm, we study the problem of distributed reasoning over connected database components. Again, distributability over connected components is in general undecidable.
We introduce the class of what we call restricted weakly-linear disjunctive tuple-generating dependencies as well as what is known as generalized regular Datalog queries.
The former extends a syntactic subset of linear tuple-generating dependencies as well as that of linear disjunctive Datalog. The latter is the most expressive subset of Datalog with a decidable containment problem with which transitive closure can be expressed.
Distributed reasoning is key to unleashing the power of ontology-mediated queries constructed from these rules. We provide the first distributability results on the above classes of queries.
To evaluate the practical implications of the proposed approach, we conduct experiments using real-world ontology benchmark suites.
Our experimental results suggest that the performance of chase engines can be improved for query answering tasks over real-world ontologies for a subset of expressive rule languages. -
- Graduation date
- Fall 2020
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.