Abstract
The problem of database consistency relative to a set of integrity constraints has been extensively studied since the 1980s, and is still recognized as one of the most important and complex in the field. In recent years, with the proliferation of knowledge repositories (not only databases) in practical applications, there has also been an effort to develop implementations of consistency maintenance algorithms that have a solid theoretical basis.
The framework of active integrity constraints (AICs) is one example of such an effort, providing theoretical grounds for rule-based algorithms for ensuring database consistency. An AIC consists of an integrity constraint together with a specification of actions that may be taken to repair a database that does not satisfy it. Both denotational and operational semantics have been proposed for AICs. In this paper, we describe repAIrC, a prototype implementation of the algorithms previously proposed targetting SQL databases, i.e., the most prolific type of databases. Using repAIrC, we can both validate an SQL database with respect to a given set of AICs and compute possible repairs in case the database is inconsistent; the tool is able to work with the different kinds of repairs that have been considered, and achieves optimal asymptotic complexity in their computation. It also implements strategies for parallelizing the search for repairs, which in many cases can make untractable problems become easily solvable.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abiteboul, S.: Updates, a new frontier. In: Gyssens, M., Paredaens, J., Gucht, D. (eds.) ICDT 1988. LNCS, vol. 326, pp. 1–18. Springer, Heidelberg (1983). doi:10.1007/3-540-50171-1_1
Brewka, G., Eiter, T.: Equilibria in heterogeneous nonmonotonic multi-context systems. In: AAAI, pp. 385–390. AAAI Press (2007)
Caroprese, L., Greco, S., Molinaro, C.: Prioritized active integrity constraints for database maintenance. In: Kotagiri, R., Krishna, P.R., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 459–471. Springer, Heidelberg (2007)
Caroprese, L., Greco, S., Zumpano, E.: Active integrity constraints for database consistency maintenance. IEEE Trans. Knowl. Data Eng. 21(7), 1042–1058 (2009)
Caroprese, L., Truszczyński, M.: Active integrity constraints and revision programming. Theory Pract. Logic Prog. 11(6), 905–952 (2011)
Cruz-Filipe, L.: Optimizing computation of repairs from active integrity constraints. In: Beierle, C., Meghini, C. (eds.) FoIKS 2014. LNCS, vol. 8367, pp. 361–380. Springer, Heidelberg (2014)
Cruz-Filipe, L., Engrácia, P., Gaspar, G., Nunes, I.: Computing repairs from active integrity constraints. In: Wang, H., Banach, R. (eds.) TASE, pp. 183–190. Piscataway, IEEE (2013)
Cruz-Filipe, L., Franz, M., Hakhverdyan, A., Ludovico, M., Nunes, I., Schneider-Kamp, P.: repAIrC: a tool for ensuring data consistency by means of active integrity constraints. In: Fred, A., Dietz, J., Aveiro, D., Liu, K., Filipe, J. (eds.) IC3K, vol. 3, pp. 17–26. SCITEPRESS, Setúbal (2015)
Cruz-Filipe, L., Nunes, I., Schneider-Kamp, P.: Integrity constraints for general-purpose knowledge bases. In: Gyssens, M., Simari, G. (eds.) FoIKS 2016. LNCS, vol. 9616, pp. 235–254. Springer, Heidelberg (2016)
Eiter, T., Gottlob, G.: On the complexity of propositional knowledge base revision, updates, counterfactuals. Artif. Intell. 57(2–3), 227–270 (1992)
Flesca, S., Greco, S., Zumpano, E.: Active integrity constraints. In: Moggi, E., Warren, D.S. (eds.) PPDP, pp. 98–107. ACM, New York (2004)
Kakas, A.C., Mancarella, P.: Database updates through abduction. In: McLeod, D., Sacks-Davis, R., Schek, H.-J. (eds.) VLDB, pp. 650–661. Morgan Kaufmann, San Francisco (1990)
Katsuno, H., Mendelzon, A.O.: On the difference between updating a knowledge base and revising it. In: Allen, J.F., Fikes, R., Sandewall, E. (eds.) KR, pp. 387–394. Morgan Kaufmann, San Francisco (1991)
Marek, V.W., Truszczyński, M.: Revision programming, database updates and integrity constraints. In: Gottlob, G., Vardi, M.Y. (eds.) ICDT 1995. LNCS, vol. 893, pp. 368–382. Springer, Heidelberg (1995)
Mayol, E., Teniente, E.: A survey of current methods for integrity constraint maintenance and view updating. In: Chen, P.P., Embley, D.W., Kouloumdjian, J., Liddle, S.W., Roddick, J.F. (eds.) ER 1999. LNCS, vol. 1727, pp. 62–73. Springer, Heidelberg (1999). doi:10.1007/3-540-48054-4_6
Naqvi, S.A., Krishnamurthy, R.: Database updates in logic programming. In: Edmondson-Yurkanan, C., Yannakakis, M. (eds.) PODS 1988, pp. 251–262. ACM, New York (1988)
Przymusinski, T.C., Turner, H.: Update by means of inference rules. J. Log. Program. 30(2), 125–143 (1997)
Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)
Teniente, E., Olivé, A.: Updating knowledge bases while maintaining their consistency. VLDB J. 4(2), 193–241 (1995)
Widom, J., Ceri, S. (eds.): Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufmann, San Francisco (1996)
Winslett, M.: Updating Logical Databases. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge (1990)
Acknowledgements
This work was supported by the Danish Council for Independent Research, Natural Sciences, and by FCT/MCTES/PIDDAC under centre grant to BioISI (Centre Reference: UID/MULTI/04046/2013). Marta Ludovico was sponsored by a grant “Bolsa Universidade de Lisboa / Fundação Amadeu Dias”. The authors would also like to thank Graça Gaspar and Patrícia Engrácia for many interesting discussions on the topic of active integrity constraints.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Cruz-Filipe, L., Franz, M., Hakhverdyan, A., Ludovico, M., Nunes, I., Schneider-Kamp, P. (2016). Active Integrity Constraints: From Theory to Implementation. In: Fred, A., Dietz, J., Aveiro, D., Liu, K., Filipe, J. (eds) Knowledge Discovery, Knowledge Engineering and Knowledge Management. IC3K 2015. Communications in Computer and Information Science, vol 631. Springer, Cham. https://doi.org/10.1007/978-3-319-52758-1_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-52758-1_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-52757-4
Online ISBN: 978-3-319-52758-1
eBook Packages: Computer ScienceComputer Science (R0)