A Dynamic Logic Account of Active Integrity Constraints

• Autorzy: Feuillade Guillaume , Herzig Andreas , Rantsoudis Christos

Identyfikatory

DOI

10.3233/FI-2019-1843

• Języki publikacji: EN

Abstrakty

EN

Active integrity constraints have been introduced in the database community as a way to restore integrity based on a set of preferred update actions. We view active integrity constraints as dynamic logic programs and show how several semantics of database repair that were proposed in the literature can be characterised in Dynamic Logic of Propositional Assignments DL-PA. We moreover propose a new definition of repair which makes use of the programs of Dynamic Logic to provide repair solutions based on an iterating procedure. After an analysis of their properties and a comparison to the previous approaches, we provide complexity results for the problem of existence of these new repairs. Furthermore, an extension on databases with history is explored and the behavior of the various repairs is adjusted to work in this setting. For all these definitions we provide DL-PA counterparts of reasoning and decision problems, such as the existence of a repair or the existence of a unique repair.

Słowa kluczowe

EN

active integrity constraints; dynamic logic; propositional assignments

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 3
• Strony: 179--210
• Opis fizyczny: Bibliogr. 29 poz., tab.

Twórcy

autor

Feuillade Guillaume

• Institut de Recherche en Informatique de Toulouse (IRIT), Université Toulouse, France

autor

Herzig Andreas

• Institut de Recherche en Informatique de Toulouse (IRIT), CNRS, France

autor

Rantsoudis Christos

• Institut de Recherche en Informatique de Toulouse (IRIT), Université Toulouse, France

Bibliografia

• [1] Abiteboul S. Updates, A New Frontier. In: Gyssens M, Paredaens J, Gucht DV (eds.), ICDT’88, 2nd International Conference on Database Theory, Bruges, Belgium, August 31 - September 2, 1988, Proceedings, volume 326 of Lecture Notes in Computer Science. Springer. ISBN 3-540-50171-1, 1988 pp. 1-18. doi:10.1007/3-540-50171-1\_1.
• [2] Ceri S, Fraternali P, Paraboschi S, Tanca L. Automatic Generation of Production Rules for Integrity Maintenance. ACM Trans. Database Syst., 1994. 19(3):367-422. doi:10.1145/185827.185828.
• [3] Bertossi LE. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. doi:10.2200/S00379ED1V01Y201108DTM020.
• [4] Winslett M. Updating Logical Databases. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1990.
• [5] Herzig A, Rifi O. Propositional Belief Base Update and Minimal Change. Artif. Intell., 1999. 115(1):107-138. doi:10.1016/S0004-3702(99)00072-7.
• [6] Chomicki J, Marcinkowski J. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 2005. 197(1-2):90-121. doi:10.1016/j.ic.2004.04.007.
• [7] Flesca S, Greco S, Zumpano E. Active integrity constraints. In: Moggi E, Warren DS (eds.), Proceedings of the 6th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, 24-26 August 2004, Verona, Italy. ACM. ISBN 1-58113-819-9, 2004 pp. 98-107. doi:10.1145/1013963.1013977.
• [8] Caroprese L, Greco S, Zumpano E. Active Integrity Constraints for Database Consistency Maintenance. IEEE Trans. Knowl. Data Eng., 2009. 21(7):1042-1058. doi:10.1109/TKDE.2008.226.
• [9] Caroprese L, Truszczynski M. Active integrity constraints and revision programming. TPLP, 2011. 11(6):905-952. doi:10.1017/S1471068410000475.
• [10] Cruz-Filipe L. Optimizing Computation of Repairs from Active Integrity Constraints. In: Beierle C, Meghini C (eds.), Foundations of Information and Knowledge Systems - 8th International Symposium, FoIKS 2014, Bordeaux, France, March 3-7, 2014. Proceedings, volume 8367 of Lecture Notes in Computer Science. Springer. ISBN 978-3-319-04938-0, 2014 pp. 361-380. doi:10.1007/978-3-319-04939-7_18.
• [11] Bogaerts B, Cruz-Filipe L. Fixpoint semantics for active integrity constraints. Artif. Intell., 2018. 255:43-70. doi:10.1016/j.artint.2017.11.003.
• [12] Herzig A, Lorini E, Moisan F, Troquard N. A Dynamic Logic of Normative Systems. In: Walsh T (ed.), IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. IJCAI/AAAI. ISBN 978-1-57735-516-8, 2011 pp. 228-233. doi:10.5591/978-1-57735-516-8/IJCAI11-049.
• [13] Balbiani P, Herzig A, Troquard N. Dynamic Logic of Propositional Assignments: A Well-Behaved Variant of PDL. In: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013. IEEE Computer Society. ISBN 978-1-4799-0413-6, 2013 pp. 143-152. doi:10.1109/LICS.2013.20.
• [14] Balbiani P, Herzig A, Schwarzentruber F, Troquard N. DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE. CoRR, 2014. abs/1411.7825. URL http://arxiv.org/abs/1411.7825.
• [15] Harel D. Dynamic Logic. In: Gabbay DM, Günthner F (eds.), Handbook of Philosophical Logic, volume II, pp. 497-604. Springer Netherlands, Dordrecht. ISBN 978-94-009-6259-0, 1984. doi:10.1007/978-94-009-6259-0_10.
• [16] Harel D, Kozen D, Tiuryn J. Dynamic Logic. MIT Press, 2000.
• [17] Feuillade G, Herzig A. A Dynamic View of Active Integrity Constraints. In: Fermé E, Leite J (eds.), Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, volume 8761 of Lecture Notes in Computer Science. Springer. ISBN 978-3-319-11557-3, 2014 pp. 486-499. doi:10.1007/978-3-319-11558-0_34.
• [18] Tiomkin ML, Makowsky JA. Propositional Dynamic Logic with Local Assignments. Theor. Comput. Sci., 1985. 36:71-87. doi:10.1016/0304-3975(85)90031-3.
• [19] van Eijck J. Making Things Happen. Studia Logica, 2000. 66(1):41-58. doi:10.1023/A:1026792711025.
• [20] Herzig A. Belief Change Operations: A Short History of Nearly Everything, Told in Dynamic Logic of Propositional Assignments. In: Baral C, Giacomo GD, Eiter T (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. AAAI Press. ISBN 978-1-57735-657-8, 2014.
• [21] Doutre S, Herzig A, Perrussel L. A Dynamic Logic Framework for Abstract Argumentation. In: Baral C, Giacomo GD, Eiter T (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. AAAI Press. ISBN 978-1-57735-657-8, 2014.
• [22] Herzig A, de Menezes MV, de Barros LN, Wassermann R. On the revision of planning tasks. In: Schaub T, Friedrich G, O’Sullivan B (eds.), ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), volume 263 of Frontiers in Artificial Intelligence and Applications. IOS Press. ISBN 978-1-61499-418-3, 2014 pp. 435-440. doi:10.3233/978-1-61499-419-0-435.
• [23] Herzig A, Lorini E, Maffre F, Schwarzentruber F. Epistemic Boolean Games Based on a Logic of Visibility and Control. In: Kambhampati S (ed.), Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016. IJCAI/AAAI Press. ISBN 978-1-57735-770-4, 2016 pp. 1116-1122.
• [24] Cooper MC, Herzig A, Maffre F, Maris F, Régnier P. A Simple Account of Multi-Agent Epistemic Planning. In: Kaminka GA, Fox M, Bouquet P, Hüllermeier E, Dignum V, Dignum F, van Harmelen F (eds.), ECAI 2016 - 22nd European Conference on Artificial Intelligence, 29 August-2 September 2016, The Hague, The Netherlands - Including Prestigious Applications of Artificial Intelligence (PAIS 2016), volume 285 of Frontiers in Artificial Intelligence and Applications. IOS Press. ISBN 978-1-61499-671-2, 2016 pp. 193-201. doi:10.3233/978-1-61499-672-9-193.
• [25] Charrier T, Schwarzentruber F. A Succinct Language for Dynamic Epistemic Logic. In: Larson K, Winikoff M, Das S, Durfee EH (eds.), Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2017, São Paulo, Brazil, May 8-12, 2017. ACM, 2017 pp. 123-131.
• [26] Katsuno H, Mendelzon AO. On the difference between updating a knowledge base and revising it. In: Gärdenfors P (ed.), Belief revision, pp. 183-203. Cambridge University Press, 1992. (preliminary version in Allen, J.A., Fikes, R., and Sandewall, E., eds., Principles of Knowledge Representation and Reasoning: Proc. 2nd Int. Conf., pages 387-394. Morgan Kaufmann Publishers, 1991).
• [27] Peppas P, Nayak AC, Pagnucco M, Foo NY, Kwok RBH, Prokopenko M. Revision vs. Update: Taking a Closer Look. In: Wahlster W (ed.), 12th European Conference on Artificial Intelligence, Budapest, Hungary, August 11-16, 1996, Proceedings. John Wiley and Sons, Chichester, 1996 pp. 95-99.
• [28] Winslett M. Reasoning about Action Using a Possible Models Approach. In: Shrobe HE, Mitchell TM, Smith RG (eds.), Proceedings of the 7th National Conference on Artificial Intelligence, St. Paul, MN, USA, August 21-26, 1988. AAAI Press / The MIT Press. ISBN 0-262-51055-3, 1988 pp. 89-93.
• [29] Stockmeyer LJ, Meyer AR. Word Problems Requiring Exponential Time: Preliminary Report. In: Aho AV, Borodin A, Constable RL, Floyd RW, Harrison MA, Karp RM, Strong HR (eds.), Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA. ACM, 1973 pp. 1-9. doi:10.1145/800125.804029.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).