National Technical University of Athens (NTUA)
Επαναγραφή και συνεπής απάντηση συζευκτικών ερωτημάτων σε εξελισσόμενες βάσεις γνώσης
Abstract
dc:descriptionThe last years conjunctive query answering constitutes a key reasoning service for many applications which involve managing very large datasets. One of the most important reasoning techniques for query answering is query rewriting. Given a conjunctive query (CQ), a process of query rewriting produces a set of rules that captures all the information of the ontology is such a way that for every dataset, the set of answers returned from the ontology over the dataset is the same with the set of answers returned from the rewriting over the same dataset. The existing rewriting systems accept as input a conjunctive query and an ontology and compute a rewriting of the query with respect to this ontology. However, a drawback of these techniques is that every time the initial ontology is modified --that is, new axioms are added(ontology revision) or existing ones removed (ontology contraction), they compute a new rewriting from scratch without exploiting the similarities between the different versions of the ontology. This may introduce considerable efficiency problems, as many real world applications involve frequent and relatively small modifications on the used ontologies. In this thesis, we study the problem of computing a rewriting for a CQ over anontology that has been modified, by reusing the information obtained by the extraction of some previous rewriting. Initially, we study the problem when the ontology is extended by a set of axioms. Our approach is to focus only on the new inferences introduced by the new set of axioms. Next, we study the problem when the ontology is contracted by as set of axioms. Initially,we provide a general algorithm which initially removes automatically the information that is no longer derivable from the new ontology and the query and then it performs some necessary new inferences. With the aim of minimizing any reasoning tasks, we investigate how a new rewriting can be produced under the constraint of not applying any inferences. Also, we provide graph-based approaches for both algorithms that optimize their performance.Finally, we evaluate experimentally the suggested algorithms and we compare their efficiency to the highly efficient systems Requiem and Rapid. The demonstrated results are very encouraging. An issue that arises from the continuous ontology modifications, is that theknowledge base is subject to inconsistencies. Particularly, in cases where the knowledge base is being updated frequently from multiple sources it is very likely that the data will be inconsistent to the axioms of the ontology.There are two main approaches that solve this problem. The straightforward approach is to try and resolve the inconsistencies by ``cleaning'' the dataset from the conflicting elements. The second approach, called consistent query answering, is to try and compute some ``meaningful'' answers despite the conflicting information. In this thesis, we present a framework for efficient query answering, under the Intersection ABox Repair (IAR) and Intersection Closed ABox Repair (ICAR)semantics, that is based on highly efficient mature data saturation(triple-store) systems. This is particularly interesting as these systems have shown to be able to handle billions of (ontology) data. Moreover, their properties enable us to propose additional refinements and optimisations for the computation of the ICAR answers. At the same time, we suggest a new type of ICAR-like semantics which we show that can be computed in polynomial time for a very large number of highly expressive DLs, which makes them the first ever such semantics. Subsequently, we show that our framework can also be used to compute answers according to the IAR semantics for ontologies expressed in the DLs DL-LiteR and ELnr after some data preprocessing for which task we give an optimised algorithm.Finally, we have conducted an experimental evaluation of the algorithms obtaining encouraging results as both our approaches (IARand ICAR) are more efficient than existing IAR-answering systems.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2016
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Tsalapati, Eleni
- Τσαλαπάτη, Ελένη
Subjects
dc:subject × 6- Επαναγραφή και συνεπής απάντηση ερωτημάτων σε εξελισσόμενες βάσεις γνώσης
- Rewriting and consistent conjunctive query answering under knowledge base evolution
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/37593