Επαναγραφή και συνεπής απάντηση συζευκτικών ερωτημάτων σε εξελισσόμενες βάσεις γνώσης

Abstract

The 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.

Τα τελευταία χρόνια το πεδίο απάντησης συζευκτικών ερωτημάτων σε μεγάλα σύνολα δεδομένων έχει καταστεί αντικείμενο συνεχούς έρευνας.Μια από τις πιο διαδεδομένες προσεγγίσεις στο πρόβλημα αυτό βασίζεται στην τεχνική της επαναγραφής ερωτημάτων. Το πρόβλημα, γενικά, ορίζεται ωςεξής: Δεδομένου ενός συζευκτικού ερωτήματος και μίας οντολογίας, μία διαδικασία επαναγραφής του ερωτήματος παράγει ένα σύνολο κανόνων στο οποίο ενσωματώνει τους περιορισμούς της οντολογίας, με τέτοιο τρόπο ώστε για οποιοδήποτε σύνολο δεδομένων, η αποτίμηση του τιθέμενου ερωτήματος πάνω στην οντολογία και το σύνολο δεδομένων να επιστρέφει τις ίδιες απαντήσεις με την αποτίμηση μόνο της επαναγραφής στο ίδιο σύνολο δεδομένων. Τα υπάρχοντα συστήματα επαναγραφής ερωτημάτων δέχονται στην είσοδο τους ένα συζευκτικό ερώτημα και μία οντολογία και υπολογίζουν μία επαναγραφή του ερωτήματος με βάση την οντολογία. Ωστόσο, τα συστήματα αυτά είναι έτσι σχεδιασμένα ώστε κάθε φορά που η οντολογία τροποποιείται -δηλαδή, επεκτείνεται ή μειώνεται κατά ένα σύνολο αξιωμάτων- να υπολογίζουν τη νέα επαναγραφή από την αρχή, χωρίς να αξιοποιούν την πληροφορία που έχει παραχθεί από τις προηγούμενες επαναγραφές. Οι οντολογίες όμως που χρησιμοποιούνται για να μοντελοποιήσουν την επιστημονική γνώση σε πραγματικά πεδία συνεχώς τροποποιούνται και συνεπώς τα υπάρχοντα συστήματα, που επαναϋπολογίζουν εξαρχής την επαναγραφή, θα καθυστερούν σημαντικά.Στο πλαίσιο αυτό, στην παρούσα διατριβή αρχικά μελετάμε το πρόβλημα υπολογισμού μίας επαναγραφής ενός ερωτήματος με βάση μία οντολογία που έχει εξελιχθεί,αξιοποιώντας την πληροφορία που έχει παραχθεί από τον υπολογισμό μίας επαναγραφής για μία προηγούμενη έκδοση της οντολογίας. Αρχικά, το πρόβλημα μελετάται για την περίπτωση που η οντολογία επεκτείνεται κατά ένα σύνολο αξιωμάτων. H προσέγγιση που ακολουθείται εστιάζει μόνο στους συμπερασμούς που πρέπει πιθανά να εφαρμοστούν εξαιτίας της προσθήκης των νέων αξιωμάτων. Στη συνέχεια, μελετάται η περίπτωση που η οντολογία συστέλλεται κατά ένα σύνολο αξιωμάτων. Στην αρχή, παρουσιάζουμε έναν γενικό αλγόριθμο ο οποίος, αφαιρεί με αυτόματο τρόπο τις προτάσεις που δεν παράγονται πλέον από τη νέα οντολογία και το ερώτημα και στη συνέχεια εφαρμόζει τους επιπλέον συμπερασμούς που είναι πιθανά απαραίτητοι.Επιπλέον, επιθυμώντας να ελαχιστοποιήσουμε τη συλλογιστική διαδικασία, μελετάμ εαν και υπό ποιες συνθήκες είναι εφικτός ο υπολογισμός μίας νέας επαναγραφής χωρίς την εφαρμογή νέων συμπερασμών. Επίσης, βελτιστοποιούμε τους προηγούμενους αλγορίθμους εφαρμόζοντας τεχνικές που στηρίζονται σε αναπαράσταση με τη χρήση γράφων. Για κάθε μία από τις περιπτώσεις προτείνουμε έναν νέο αλγόριθμο τον οποίο παρουσιάζουμε αναλυτικά και αποδεικνύουμε την ορθότητα του. Τέλος, αξιολογούμε πειραματικά τους προτεινόμενους αλγορίθμους και τους συγκρίνουμε με τα συστήματαRequiem και Rapid, που αποτελούν τεχνολογία αιχμής στην περιοχή της επαναγραφής με αλγόριθμους ανάλυσης. Τα αποτελέσματα της αξιολόγησης αυτής είναι ιδιαίτερα ενθαρρυντικά.Στη συνέχεια, στο πλαίσιο της διατριβής, ασχολούμαστε με ένα από τα κυριότερα προβλήματα που εμφανίζονται κατά την συνεχή τροποποίηση των οντολογιών, δηλαδή μία πιθανή ασυνέπεια που μπορεί να εμφανιστεί στη βάση γνώσης. Συγκεκριμένα,ιδιαίτερα σε περιπτώσεις που η βάση γνώσης ανανεώνεται συνεχώς από διαφορετικούς παρόχους είναι πιθανό τα δεδομένα να είναι ασυνεπή σε σχέση με τα αξιώματα της οντολογίας. Για την επίλυση του προβλήματος αυτού προτείνονται δύο βασικές προσεγγίσεις. Η πρώτη στοχεύει στην επιδιόρθωση του συνόλου δεδομένων ώστε η βάση γνώσης να γίνει συνεπής. Η δεύτερη δεν προτείνει την τροποποίηση της βάσης γνώσης, αλλά νέους αλγόριθμους για τον υπολογισμό απαντήσεων σε περιβάλλον ασυνέπειας.Στην παρούσα διατριβή προτείνουμε ένα πλαίσιο απάντησης ερωτημάτων που βασίζεται σε συστήματα κορεσμού δεδομένων υπό τις σημασιολογίες Τομή Διορθωμένων ABox(Intersection ABox Repair-IAR) και Τομή Διορθωμένων Κλεισμένων ABox(Intersection Closed ABox Repair- ICAR). Ένα σημαντικό πλεονέκτημα των συστημάτων αυτών είναι ότι μπορούν να διαχειριστούν με αποδοτικό τρόπο πολύ μεγάλο όγκο δεδομένων. Συγκεκριμένα, αρχικά, ακολουθώντας τη δεύτερη προσέγγιση, προτείνουμε έναν αλγόριθμο υπολογισμού των ICAR απαντήσεων.Ταυτόχρονα, αξιοποιώντας τις ιδιότητες των συστημάτων κορεσμού δεδομένων αυξάνουμε την αποδοτικότητα του προτεινόμενου αλγορίθμου. Επίσης, εισάγουμε μία νέα σημασιολογία, βασισμένη στη σημασιολογία ICAR, κατά την οποία η απάντηση ερωτημάτων ακόμα και για πιο εκφραστικές Περιγραφικές Λογικές υπολογίζεται σε πολυωνυμικό χρόνο. Προτείνουμε,επίσης, έναν αλγόριθμο υπολογισμού των απαντήσεων υπό την σημασιολογία αυτή αποδεικνύοντας την ορθότητά του.Επιπλέον, ακολουθώντας την πρώτη προσέγγιση, παρουσιάζουμε έναν αποδοτικό αλγόριθμο υπολογισμού των IAR απαντήσεων για DL-LiteR και ELnr οντολογίες.Τέλος, παρουσιάζουμε τα πειραματικά αποτελέσματα των συστημάτων που αφορούν στον υπολογισμό απαντήσεων σε ασυνεπείς βάσεις γνώσης για βατές Περιγραφικές Λογικές.Συγκρίνοντας τα χρονικά αποτελέσματά μας με τα χρονικά αποτελέσματα των αντίστοιχων υπαρχόντων συστημάτων διαπιστώνουμε ότι τα συστήματά μας είναι ιδιαίτερα αποδοτικά.