UCQ-rewritings for disjunctive knowledge and queries with negated atoms

Abstract

In this thesis, the problem of query rewriting for conjunctive queries with negation with respect to disjunctive existential rules is studied. Query rewriting is a well-known approach for query answering on knowledge bases with incomplete data. Three rewriting techniques are proposed that find -rewritings for queries with negation on the (disjunctive) existential rules framework. The first technique uses resolution with respect to constraints in order to eliminate the negated atoms from the input query. A set of conjunctive queries is produced and it can be rewritten with the existential rules in the knowledge base producing more -rewritings. The second technique focuses on finding a -rewriting of queries with not more than one negated atom. Such queries are transformed into existential rules and the constraints or the knowledge base are rewritten. The method keeps track of the rewritings produced by the rule corresponding to the transformed query and yields a complete -rewriting. The third rewriting technique uses constraints and conjunctive queries to remove the disjunctive components of disjunctive existential rules. This process eventually generates new non-disjunctive rules, i.e., existential rules. The generated rules can then be used to produce new rewritings using existing rewriting approaches for existential rules. With the proposed technique we are able to provide complete -rewritings for union of conjunctive queries with universally quantified negation. The proposed techniques are implemented in the COMPLETO system (v1, v2, and v3 respectively) and some experiments were carried out to evaluate the viability of the proposed solutions. We also address the undecidability of the existence of a finite and complete -rewriting and the identification of finite unification sets (fus) of rules. We introduce new rule classes, connected linear rules and connected domain restricted rules, that exhibit the fus property for existential rules. Additionally, we propose disconnected disjunction for disjunctive existential rules to achieve the fus property when we extend the introduced rule fragments to disjunctive existential rules. Finally, we present ECOMPLETO, a version of our system implemented in Elixir programming language, capable of handling ¬ s with universally quantified negation and disjunctive existential rules. Our experiments demonstrate ECOMPLETO’s consistent ability to produce finite -rewritings, and describe the performance on different ontologies and queries.

Σε αυτή τη διατριβή, μελετάται το πρόβλημα του μετασχηματισμού ερωτημάτων για συζευκτικά ερωτήματα με άρνηση σε σχέση με διαζευκτικούς υπαρξιακούς κανόνες. Ο μετασχηματισμός ερωτημάτων είναι μια γνωστή προσέγγιση για την απάντηση ερωτημάτων σε βάσεις γνώσεων με ελλιπή δεδομένα. Προτείνονται τρεις τεχνικές μετασχηματισμού που βρίσκουν μετασχηματισμούς UCQ για ερωτήματα με άρνηση στο πλαίσιο των (διαζευκτικών) υπαρξιακών κανόνων.Η πρώτη τεχνική χρησιμοποιεί ανάλυση σε σχέση με τους περιορισμούς για την εξάλειψη των αρνημένων ατομικών τύπων από το εισαγόμενο ερώτημα. Παράγεται ένα σύνολο συζευκτικών ερωτημάτων το οποίο μπορεί να μετασχηματιστεί με τους υπαρξιακούς κανόνες στη βάση γνώσεων, παράγοντας περισσότερους μετασχηματισμούς UCQ.Η δεύτερη τεχνική εστιάζει στην εύρεση ενός μετασχηματισμού UCQ για ερωτήματα με όχι περισσότερους από έναν αρνημένο ατομικό τύπο. Τέτοια ερωτήματα μετασχηματίζονται σε υπαρξιακούς κανόνες και οι περιορισμοί ή η βάση γνώσεων μετασχηματίζονται. Η μέθοδος παρακολουθεί τους μετασχηματισμούς που παράγονται από τον κανόνα που αντιστοιχεί στο μετασχηματισμένο ερώτημα και αποδίδει έναν πλήρη μετασχηματισμό UCQ. Η τρίτη τεχνική μετασχηματισμού χρησιμοποιεί περιορισμούς και συζευκτικά ερωτήματα για να αφαιρέσει τα διαζευκτικά συστατικά των διαζευκτικών υπαρξιακών κανόνων. Αυτή η διαδικασία τελικά παράγει νέους μη διαζευκτικούς κανόνες, δηλαδή υπαρξιακούς κανόνες. Οι παραγόμενοι κανόνες μπορούν στη συνέχεια να χρησιμοποιηθούν για την παραγωγή νέων μετασχηματισμών χρησιμοποιώντας υπάρχουσες προσεγγίσεις μετασχηματισμού για υπαρξιακούς κανόνες. Με την προτεινόμενη τεχνική είμαστε σε θέση να παρέχουμε πλήρεις μετασχηματισμούς UCQ για ένωση συζευκτικών ερωτημάτων με καθολικά ποσοτικοποιημένη άρνηση.Οι προτεινόμενες τεχνικές υλοποιούνται στο σύστημα COMPLETO (v1, v2 και v3 αντίστοιχα) και διεξήχθησαν μερικά πειράματα για την αξιολόγηση της βιωσιμότητας των προτεινόμενων λύσεων. Αντιμετωπίζουμε επίσης την αναποφασιστικότητα της ύπαρξης ενός πεπερασμένου και πλήρους μετασχηματισμού UCQ και την ταυτοποίηση πεπερασμένων συνόλων ενοποίησης (fus) κανόνων. Εισάγουμε νέες κατηγορίες κανόνων, συνδεδεμένους γραμμικούς κανόνες και συνδεδεμένους περιορισμένους κανόνες πεδίου, που επιδεικνύουν την ιδιότητα fus για υπαρξιακούς κανόνες. Επιπλέον, προτείνουμε αποσυνδεδεμένη διαζευκτικότητα για διαζευκτικούς υπαρξιακούς κανόνες ώστε να επιτευχθεί η ιδιότητα fus όταν επεκτείνουμε τα εισαχθέντα θραύσματα κανόνων σε διαζευκτικούς υπαρξιακούς κανόνες. Τέλος, παρουσιάζουμε το ECOMPLETO, μια έκδοση του συστήματός μας υλοποιημένη στη γλώσσα προγραμματισμού Elixir, ικανή να χειριστεί UCQ¬ με καθολικά ποσοτικοποιημένη άρνηση και διαζευκτικούς υπαρξιακούς κανόνες. Τα πειράματά μας δείχνουν τη συνεπή ικανότητα του ECOMPLETO να παράγει πεπερασμένους μετασχηματισμούς UCQ και περιγράφουν την απόδοση σε διαφορετικές οντολογίες και ερωτήματα.