Knowledge bases and preferred update actions: searching for consistency through dynamic logic programs

Abstract

In the database literature it has been proposed to resort to active integrity constraints in order to restore database integrity. Such active integrity constraints consist of a classical constraint together with a set of preferred update actions that can be triggered when the constraint is violated. In the first part of this thesis, we review the main repairing routes that have been proposed in the literature and capture them by means of Dynamic Logic programs. The main tool we employ for our investigations is the recently introduced logic DL-PA, which constitutes a variant of PDL. We then go on to explore a new, dynamic kind of database repairing whose computational complexity and general properties are compared to the previous established approaches. In the second part of the thesis we leave the propositional setting and pursue to adapt the aforementioned ideas to higher level languages. More specifically, we venture into Description Logics and investigate extensions of TBox axioms by update actions that denote the preferred ways an ABox should be repaired in case of inconsistency with the axioms of the TBox. The extension of the TBox axioms with these update actions constitute new, active TBoxes. We tackle the problem of repairing an ABox with respect to such an active TBox both from a syntactic as well as a semantic perspective. Given an initial ABox, the syntactic approach allows us to construct a set of new ABoxes out of which we then identify the most suitable repairs. On the other hand, for the semantic approach we once again resort to a dynamic logic framework and view update actions, active inclusion axioms and repairs as programs. Given an active TBox aT , the framework allows to check (1) whether a set of update actions is able to repair an ABox according to the active axioms of aT by interpreting the update actions locally and (2) whether an ABox A′ is the repair of a given ABox A under the active axioms of aT using a bounded number of computations by interpreting the update actions globally. After discussing the strong points of each direction, we conclude by combining the syntactic and semantic investigations into a cohesive approach.

Στη βιβλιογραφία των βάσεων δεδομένων έχει προταθεί η προσφυγή σε ενεργούς περιορισμούς ακεραιότητας για την αποκατάσταση της ακεραιότητας μιας βάσης δεδομένων. Τέτοιοι ενεργοί περιορισμοί ακεραιότητας αποτελούνται από έναν κλασικό περιορισμό μαζί με ένα σύνολο προτιμώμενων ενεργειών ενημέρωσης που μπορούν να ενεργοποιηθούν όταν παραβιαστεί ο περιορισμός. Στο πρώτο μέρος αυτής της διατριβής, εξετάζουμε τις κύριες οδούς επιδιόρθωσης που έχουν προταθεί στη βιβλιογραφία και τις καταγράφουμε μέσω προγραμμάτων Δυναμικής Λογικής. Το κύριο εργαλείο που χρησιμοποιούμε για τις έρευνές μας είναι η πρόσφατα εισαχθείσα λογική DL-PA, η οποία αποτελεί μια παραλλαγή της PDL. Στη συνέχεια προχωράμε στην εξερεύνηση ενός νέου, δυναμικού είδους επιδιόρθωσης βάσεων δεδομένων της οποίας η υπολογιστική πολυπλοκότητα και οι γενικές ιδιότητες συγκρίνονται με τις προηγούμενες καθιερωμένες προσεγγίσεις. Στο δεύτερο μέρος της διατριβής αφήνουμε το προτασιακό περιβάλλον και επιδιώκουμε να προσαρμόσουμε τις προαναφερθείσες ιδέες σε γλώσσες υψηλότερου επιπέδου. Πιο συγκεκριμένα, ασχολούμαστε με τις Περιγραφικές Λογικές και διερευνούμε επεκτάσεις των αξιωμάτων του TBox μέσω ενεργειών ενημέρωσης που υποδηλώνουν τους προτιμώμενους τρόπους με τους οποίους ένα ABox θα πρέπει να επιδιορθωθεί σε περίπτωση ασυνέπειας με τα αξιώματα του TBox. Η επέκταση των αξιωμάτων του TBox με αυτές τις ενέργειες ενημέρωσης αποτελεί νέα, ενεργά TBox. Αντιμετωπίζουμε το πρόβλημα της επιδιόρθωσης ενός ABox σε σχέση με ένα τέτοιο ενεργό TBox τόσο από συντακτική όσο και από σημασιολογική άποψη. Δεδομένου ενός αρχικού ABox, η συντακτική προσέγγιση μας επιτρέπει να κατασκευάσουμε ένα σύνολο νέων ABox από τα οποία στη συνέχεια προσδιορίζουμε τις πιο κατάλληλες επιδιορθώσεις. Από την άλλη πλευρά, για τη σημασιολογική προσέγγιση καταφεύγουμε για άλλη μια φορά σε ένα πλαίσιο δυναμικής λογικής και βλέπουμε τις ενέργειες ενημέρωσης, τα αξιώματα ενεργητικής ένταξης και τις επιδιορθώσεις ως προγράμματα. Δεδομένου ενός ενεργού TBox aT, το πλαίσιο επιτρέπει να ελεγχθεί (1) εάν ένα σύνολο ενεργειών ενημέρωσης είναι σε θέση να επιδιορθώσει ένα ABox σύμφωνα με τα ενεργά αξιώματα του aT ερμηνεύοντας τις ενέργειες ενημέρωσης τοπικά και (2) εάν ένα ABox A′ είναι η επιδιόρθωση ενός δεδομένου ABox A υπό τα ενεργά αξιώματα του aT χρησιμοποιώντας έναν περιορισμένο αριθμό υπολογισμών ερμηνεύοντας τις ενέργειες ενημέρωσης καθολικά. Αφού συζητήσουμε τα δυνατά σημεία κάθε κατεύθυνσης, καταλήγουμε συνδυάζοντας τις συντακτικές και σημασιολογικές έρευνες σε μια συνεκτική προσέγγιση.

Dans la littérature sur les bases de données, il a été proposé d’utiliser des contraintes d’intégrité actives afin de restaurer l’intégrité de la base. Ces contraintes d’intégrité actives consistent en une contrainte classique augmentée d’un ensemble d’actions de mise à jour préférées qui peuvent être déclenchées quand la contrainte est violée. Dans la première partie de cette thèse, nous passons en revue les principales stratégies de réparation qui ont été proposées dans la littérature et proposons une formalisation par des programmes de la Logique Dynamique. L’outil principal que nous employons dans notre recherche est la logique DL-PA, une variante de PDL récemment introduite. Nous explorons ensuite une nouvelle façon dynamique de réparer les bases de données et comparons sa complexité calculatoire et ses propriétés générales aux approches classiques. Dans la seconde partie de la thèse nous abandonnons le cadre propositionnel et adaptons les idées susmentionnées à des langages d’un niveau supérieur. Plus précisément, nous nous intéressons aux Logiques de Description, et étudions des extensions des axiomes d’une TBox par des actions de mise à jour donnant les manières préférées par lesquelles une ABox doit être réparée dans le cas d’une inconsistance avec les axiomes de la TBox. L’extension des axiomes d’une TBox avec de telles actions de mise à jour constitue une nouvelle TBox, qui est active. Nous nous intéressons à la manière de réparer une ABox en rapport avec une telle TBox active, du point de vue syntaxique ainsi que du point de vue sémantique. Étant donnée une ABox initiale, l’approche syntaxique nous permet de construire un nouvel ensemble d’ABox dans lequel nous identifions les réparations les mieux adaptées. D’autre part, pour l’approche sémantique, nous faisons de nouveau appel au cadre de la logique dynamique et considérons les actions de mise à jour, les axiomes d’inclusion actives et les réparations comme des programmes. Étant donné une TBox active aT , ce cadre nous permet de vérifier (1) si un ensemble d’actions de mise à jour est capable de réparer une ABox en accord avec les axiomes actifs d’aT en effectuant une interprétation locale des actions de mise à jour et (2) si une ABox A′ est la réparation d’une ABox donnée A sous les axiomes actifs d’aT moyennant un nombre borné de calculs, en utilisant une interprétation globale des actions de mise à jour. Après une discussion des avantages de chaque approche nous concluons en proposant une intégration des approches syntaxiques et sémantiques dans une approche cohésive.