Foundations of Modal Deductive Databases

• Autorzy: Nguyen L.A. L.A.
• Języki publikacji: EN

Abstrakty

EN

We give formulations for modal deductive databases and present a modal query language called MDatalog. We define modal relational algebras and give the seminaive evaluation algorithm, the top-down evaluation algorithm, and the magic-set transformation for MDatalog queries. The results of this paper like soundness and completeness of the top-down evaluation algorithm or correctness of the magic-set transformation are proved for the multimodal logics of belief KDI4s5, KDI45, KD4s5s, KD45(m), KD4Ig5a, and the class of serial context-free grammar logics. We also show that MDatalog has PTIME data complexity in the logics KDI4s5, KDI45, KD4s5s, and KD45(m).

Słowa kluczowe

EN

modal logic; deductive databases; modal logic programming; relational algebra; seminaive evaluation; query-subquery evaluation; magic-set transformation; data complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 1-2
• Strony: 85--135
• Opis fizyczny: bibliogr. 30 poz.

Twórcy

autor

Nguyen L.A. L.A.

• Institute of Informatics Warsaw University ul. Banacha 2 02-097 Warsaw, Poland,

Bibliografia

• [1] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. AddisonWesley, 1995.
• [2] H. Aldewereld,W. van der Hoek, and J.-J.Ch.Meyer. Rational teams: Logical aspects of multi-agent systems. Fundamenta Informaticae, 63(2-3):159-183, 2004.
• [3] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2002.
• [4] M. Cadoli, L. Palopoli, and M. Lenzerini. Datalog and description logics: Expressive power. In S. Cluet and R. Hull, editors, DBPL-6, LNCS 1369, pages 281-298. Springer, 1998.
• [5] D. Calvanese, G. De Giacomo, D. Lembo,M. Lenzerini, and R. Rosati. Data complexity of query answering in description logics. In I. Horrocks, U. Sattler, and F. Wolter, editors, Description Logics, 2005.
• [6] M.J. Cresswell and G.E. Hughes. A New Introduction to Modal Logic. Routledge, 1996.
• [7] F. Debart, P. Enjalbert, and M. Lescot. Multimodal logic programming using equational and order-sorted logic. Theoretical Computer Science, 105:141-166, 1992.
• [8] L. Farinas del Cerro and M. Penttonen. Grammar logics. Logique et Analyse, 121-122:123-134, 1988.
• [9] M. Fitting and R.L. Mendelsohn. First-Order Modal Logic. Kluwer Academic Publishers, 1999.
• [10] E. Franconi and S. Tessaris. Rules and queries with ontologies: A unified logical framework. In H.J. Ohlbach and S. Schaffert, editors, PPSWR 2004, LNCS 3208, pages 50-60. Springer, 2004.
• [11] J. W. Garson. Quantification in modal logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic: Volume II: Extensions of Classical Logic, pages 249-307. Reidel, Dordrecht, 1984.
• [12] R. Goré and L.A. Nguyen. Clausal tableau systems for multimodal logics of belief. Available at http://www.mimuw.edu.pl/_nguyen/papers.html.
• [13] G. Gottlob, E. Grädel, and H. Veith. Linear time Datalog and branching time logic. In Logic-Based Artif. Int., pages 443-467. Kluwer Academic Publishers, 2000.
• [14] B.N. Grosof, I. Horrocks, R. Volz, and S. Decker. Description logic programs: combining logic programs with description logic. In WWW'2003, pages 48-57. ACM, 2003.
• [15] U. Hustadt, B. Motik, and U. Sattler. Data complexity of reasoning in very expressive description logics. In L.P. Kaelbling and A. Saffiotti, editors, IJCAI, pages 466-471. Professional Book Center, 2005.
• [16] Ch. Koch and S. Scherzinger. Lecture notes on database theory. http://www-db.cs.uni-sb.de/teaching/dbth0506/slides/dbth-datalog2.pdf.
• [17] A.Y. Levy and M.-Ch. Rousset. Combining Horn rules and description logics in CARIN. Artificial Intelligence, 104(1-2):165-209, 1998.
• [18] J.W. Lloyd. Foundations of Logic Programming, Second Edition. Springer-Verlag, 1987.
• [19] L.A. Nguyen. Constructing the least models for positive modal logic programs. Fundamenta Informaticae, 42(1):29-60, 2000.
• [20] L.A. Nguyen. The modal query language MDatalog. Fundamenta Informaticae, 46(4):315-342, 2001.
• [21] L.A. Nguyen. A fixpoint semantics and an SLD-resolution calculus for modal logic programs. Fundamenta Informaticae, 55(1):63-100, 2003.
• [22] L.A. Nguyen. The modal logic programming system MProlog. In J.J. Alferes and J.A. Leite, editors, Proceedings of JELIA 2004, LNCS 3229, pages 266-278. Springer, 2004.
• [23] L.A. Nguyen. On modal deductive databases. In J. Eder, H.-M. Haav, A. Kalja, and J. Penjam, editors, Proceedings of ADBIS 2005, LNCS 3631, pages 43-57. Springer, 2005.
• [24] L.A. Nguyen. The data complexity of MDatalog in basic modal logics. In R. Kralovic and P. Urzyczyn, editors, Proceedings of MFCS 2006, LNCS 4162, pages 729-740. Springer-Verlag, 2006.
• [25] L.A. Nguyen. Multimodal logic programming. Theoretical Computer Science, 360:247-288, 2006.
• [26] L.A. Nguyen. Reasoning about epistemic states of agents by modal logic programming. In F. Toni and P. Torroni, editors, Proceedings of CLIMA VI, LNAI 3900, pages 37-56. Springer-Verlag, 2006. A revised version is available at http://www.mimuw.edu.pl/_nguyen/papers.html.
• [27] L.A. Nguyen. Foundations of modal logic programming: The direct approach. Manuscript (served as a technical report), available at http://www.mimuw.edu.pl/_nguyen/papers.html, November 2006 (revised March 2007).
• [28] A. Nonnengart. How to use modalities and sorts in Prolog. In C. MacNish, D. Pearce, and L.M. Pereira, editors, Logics in Artificial Intelligence, European Workshop, JELIA '94, York, UK, September 5-8, 1994, Proceedings, volume 838 of LNCS, pages 365-378. Springer, 1994.
• [29] H.J. Ohlbach. A resolution calculus for modal logics. In Proceedings of CADE-88, LNCS310, pages 500-516. Springer, 1988.
• [30] M.A. Orgun andW.W. Wadge. Towards a unified theory of intensional logic programming. Journal of Logic Programming, 13(4):413-440, 1992.