Incremental checking and maintenance of UML/OCL integrity constraints

Author

Oriol Hilari, Xavier

Director

Teniente, Ernest

Date of defense

2017-07-11

Pages

191 p.



Department/Institute

Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics

Universitat Politècnica de Catalunya. Departament de Ciències de la Computació

Abstract

Ensuring the data correctness of some information system is a crucial task. So, software engineers specify sets of integrity constraints that should be satisfied by the system's data. These constraints, however, can be violated every time a user modifies the data state. To avoid so, the system should either check that the current update does not cause any violation before applying it, or maintain the constraints after applying the update (i.e., apply the update together some additional corrective measures to avoid the violation). This thesis contributes on both problems, i.e., how to automatically check and/or maintain a set of integrity constraints after a user update, considering information systems and constraints described with two of the currently most spread conceptual modeling languages: UML for describing the information schema, and OCL for defining its constraints. In the first part of the thesis, we start analysing the expressiveness of OCL for defining integrity constraints. In this analysis, we show that the OCL language is so expressive than checking its constraints is non-decidable. To tackle this phenomenon, we determine the subset of the OCL language which is expressively equivalent to relational algebra (OCLfo), and thus, tractable at least in the case of checking. Consequently, in the second part, we tackle the integrity checking/maintenance problem for OCLfo constraints departing from a currently existing method for relational databases (the event rules) which we extend in several directions. For the case of checking constraints, we extend the event rules to deal with aggregation functions (such as sum, count, etc), thus, pushing the expressiveness of the constraints they can deal with (that is, OCLfo extended with aggregates), and exploit this extension to increase the performance of the original method. For the case of maintenance, we show that, with a slight modification of the event rules, we can maintain the constraints using a simple complete implementation of the well-known chase algorithm. At this point, we realize that the problem of maintenance is non-decidable for OCLfo, so, we determine a subset of it, OCLuniv, which is decidable. Furthermore, in order to show the high applicability of our approach, in the third part, we export our work into the context of Description Logics, in which we present a variant of the event rules that permits maintaining a DL-Lite ontology in polynomial time through SQL queries.


Assegurar la correctesa de les dades d'un sistema d'informació és una tasca crucial. Per això, els enginyers del software especifiquen restriccions d'integritat que haurien de ser satisfetes per les dades del sistema. Aquestes restriccions, no obstant, poden violar-se cada vegada que un usuari modifica l'estat de les dades. Per evitar-ho, el sistema hauria de, o bé, comprovar que l'actualització de les dades no causa cap violació de les restriccions abans d'aplicar-la, o bé reparar les restriccions un cop aplicada l'actualització (és a dir, aplicar l'actualització conjuntament amb certes mesures correctives per evitar les violacions). Aquesta tesi és una contribució a ambdós problemes, és a dir, tant en el problema de comprovar automàticament les restriccions com el de mantenir-les, considerant els sistemes d'informació i les seves restriccions descrites en dos dels llenguatges de modelització conceptual més usats del moment: UML per descriure el sistema d'informació, i OCL per descriure'n les restriccions. A la primera part de la tesi, comencem analitzant l'expressivitat del llenguatge OCL per definir restriccions d'integritat. Fruït d'aquest anàlisi, demostrem que el llenguatge OCL és tan expressiu que el problema de comprovar-ne les restriccions és no-decidible. Per pal·liar aquest fenomen, determinem el subconjunt d’OCL equivalent a l’àlgebra relacional (OCLfo), el qual és, per tant, tractable almenys en el cas de la comprovació de restriccions. Conseqüentment, a la segona part, tractem el problema de comprovació/manteniment de restriccions OCLfo partint d’un mètode preexistent en el camp de les bases de dades relacional (el mètode dels esdeveniments) el qual estenem en diferents direccions. En el cas de la comprovació de restriccions, estenem el mètode dels esdeveniments per poder fer front a funcions d’agregació (per exemple, comptatges, sumes totals, etc.) de tal manera que augmentem l’expressivitat de les restriccions que poden fer front (és a dir, OCLfo estès amb agregats), i a més, explotem aquesta extensió per millorar el temps d’execució del mètode dels esdeveniments original. En el cas del manteniment de restriccions, demostrem que amb una lleugera variació del mètode dels esdeveniments podem resoldre el manteniment de restriccions utilitzant una implementació del conegut algorisme chase. En aquest punt, observem com el problema de manteniment de restriccions segueix sent no-decidible fins i tot en el cas d’OCLfo, i determinem un altre subconjunt d’OCL, l’OCLuniv, que sí és decidible pel manteniment. Finalment, per tal de demostrar l’alta aplicabilitat de la nostra proposta, a la tercera part de la tesi, exportem els nostres resultats en un altre context, els Descripcion Logics, on demostrem que amb petites variacions del nostre mètode podem mantenir una ontologia DL-Lite en temps polinòmic mitjançant consultes SQL.

Subjects

004 - Computer science and technology. Computing. Data processing

Knowledge Area

Àrees temàtiques de la UPC::Informàtica

Documents

TXOH1de1.pdf

1.631Mb

 

Rights

L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/4.0/
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc/4.0/

This item appears in the following Collection(s)