Actualització consistent de bases de dades deductives

Abstract

En aquesta tesi, proposem un nou mètode per a l'actualització consistent de bases de dades deductives. Donada una petició d'actualització, aquest mètode tradueix de forma automàtica aquesta petició en el conjunt de totes les possibles formes d'actualitzar la base de dades extensional de forma que la petició sigui satisfeta i que no es violi cap restricció d'integritat. <br/>Aquest nostre mètode està basat en un conjunt de regles que defineixen la diferència entre dos estats consecutius de la base de dades. Aquesta diferència es determina definint explícitament les insercions, esborrats i les modificacions que es poden induir com a conseqüència de l'aplicació d'una actualització a la base de dades. <br/>El mètode està basat en una extensió del procediment de resolució SLDNF. Sigui D una base de dades deductiva, A(D) la base de dades augmentada associada, U una petició inicial d'actualització i T un conjunt d'actualitzacions de fets bàsics. Direm que el conjunt T satisfà la petició d'actualització U i no viola cap restricció d'integritat de D si, utilitzant la resolució SLDNF, l'objectiu &#61612; U &#61657; ¬&#61545;Ic té èxit amb el conjunt d'entrada A(D) &#61640; T. Així doncs, el mètode consistirà en fer tenir èxit a les derivacions SLDNF fracassades. Per a fer-ho, s'inclouran al conjunt T aquelles actualitzacions de fets bàsics que cal realitzar per tal de que la derivació assoleixi l'èxit. Les diferent formes com es pot assolir aquest èxit es corresponen a les diferents solucions a la petició d'actualització U. <br/>El mètode proposat es demostra que és correcte i complet. En aquest sentit, es garanteix que donada una petició d'actualització U, el mètode obté totes les possibles formes de satisfer aquesta petició i que, a la vegada, se satisfacin les restriccions d'integritat definides a la base de dades. <br/>A diferència d'altres mètodes, el nostre gestiona les modificacions de fets com un nou tipus d'actualització bàsic. Aquest nou tipus d'actualització, junt amb la demostració de correctesa i completesa, és una de les principals aportacions del nostre mètode respecte els mètodes apareguts recentment. La segona gran aportació del nostre mètode és el fet d'utilitzar tècniques per a millorar l'eficiència del procés de traducció de vistes i del procés de manteniment de restriccions d'integritat. <br/>Per a millorar l'eficiència del procés de manteniment de restriccions d'integritat, proposem una tècnica per a determinar l'ordre en què cal comprovar les restriccions d'integritat. Aquesta tècnica està basada en la generació en temps de compilació del anomenat Graf de Precedències, el qual estableix les relacions entre violadors i reparadors potencials d'aquestes restriccions. Aquest Graf és utilitzat en temps d'execució per a determinar l'ordre en què es comproven i reparen les restriccions d'integritat. Aquest ordre redueix el nombre de vegades que cada restricció d'integritat ha de ser comprovada (i reparada) després de reparar qualsevol altre restricció. Per a millorar l'eficiència del procés d'actualització de vistes, proposem fer una anàlisi de la petició d'actualització, del contingut de la base de dades i de les regles de la base de dades augmentada abans d'iniciar la traducció de la petició d'actualització U. Aquesta anàlisi té com a objectiu el minimitzar el nombre d'accessos al contingut de base de dades que cal realitzar per a traduir la petició d'actualització, i per altra banda, aquesta anàlisi també ha de permetre determinar quines alternatives no podran donar lloc a una traducció vàlida a la petició U, permetent així, considerar únicament aquelles alternatives que sí proporcionaran una traducció vàlida a U.

Deductive databases generalize relational databases by including not only base facts and integrity constraints, but also deductive rules. Several problems may arise when a deductive database is updated. The problems that are addressed in this thesis are those of integrity maintenance and view updating. <br/>Integrity maintenance is aimed to ensure that, after a database update, integrity constraints remain satisfied. When these integrity constraints are violated by some update, such violations must be repaired by performing additional updates. <br/>The second problem we deal with is view updating. In a deductive database, derived facts are not explicitly stored into the database and they are deduced from base facts using deductive rules. Therefore, requests to update view (or derived) facts must be appropriately translated into correct updates of the underlying base facts. <br/>There is a close relationship between updating a deductive database and maintaining integrity constraints because, in general, integrity constraints can only be violated when performing an update. For instance, updates of base facts obtained as a result of view updating could violate some integrity constraint. On the other hand, to repair an integrity constraint could require to solve the view update problem when integrity constraint may be defined by some derived predicate.<br/>In this thesis, we propose a method that deals satisfactorily and efficiently with both problems in an integrated way. In this sense, given an update request, our method automatically translates it into all possible ways of changing the extensional database such that the update request is satisfied and no integrity constraint is violated. <br/>Concretely, we formally define the proposed method and we prove its soundness and completeness. The method is sound and complete in the sense that it provides all possible ways to satisfy an update request and that each provided solution satisfies the update request and does not violate any integrity constraint. Moreover, to compare how our method extends previous work in the area, we have proposed a general framework that allows us to classify and to compare previous research in the field of view updating and integrity constraint maintenance. This framework is based on taking into account five relevant dimensions that participate into this process, i.e. the kind of update requests, the database schema considered, the problem addressed, the solutions obtained and the technique used to obtain these solutions. <br/>Efficiency issues are also addressed in our approach, either for integrity maintenance as well as for view updating.<br/>To perform integrity maintenance efficiently, we propose a technique for determining the order in which integrity constraints should be handled. This technique is based on the generation at compile time of a graph, the Precedence Graph, which states the relationships between potential violations and potential repairs of integrity constraints. This graph is used at run-time to determine the proper order to check and repair integrity constraints. This order reduces significantly the number of times that each integrity constraint needs to be reconsidered after any integrity constraint repair. <br/>To improve efficiency during view updating, we propose to perform an initial analysis of the update request, the database contents and the rules of the database. The purpose of this analysis is to minimize the number of accesses to the base facts needed to translate a view update request and to explore only relevant alternatives that may lead to valid solutions of the update request. <br/>Furthermore, a detailed comparison with respect to some methods for integrity maintenance that consider efficiency issues is also provided, showing several contributions of our approach.