×

zbMATH — the first resource for mathematics

Distributed first order logic. (English) Zbl 1423.68491
Summary: Distributed First Order Logic (DFOL) has been introduced more than ten years ago with the purpose of formalising distributed knowledge-based systems, where knowledge about heterogeneous domains is scattered into a set of interconnected modules. DFOL formalises the knowledge contained in each module by means of first-order theories, and the interconnections between modules by means of special inference rules called bridge rules. Despite their restricted form in the original DFOL formulation, bridge rules have influenced several works in the areas of heterogeneous knowledge integration, modular knowledge representation, and schema/ontology matching. This, in turn, has fostered extensions and modifications of the original DFOL that have never been systematically described and published. This paper tackles the lack of a comprehensive description of DFOL by providing a systematic account of a completely revised and extended version of the logic, together with a sound and complete axiomatisation of a general form of bridge rules based on Natural Deduction. The resulting DFOL framework is then proposed as a clear formal tool for the representation of and reasoning about distributed knowledge and bridge rules.
MSC:
68T30 Knowledge representation
68T27 Logic in artificial intelligence
Software:
SchemaSQL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sheth, A. P.; Larson, J. A., Federated database systems for managing distributed, heterogeneous, and autonomous databases, ACM Comput. Surv., 22, 3, 183-236, (1990)
[2] Lakshmanan, L. V.; Sadri, F.; Subramanian, S. N., Schemasql: an extension to SQL for multidatabase interoperability, ACM Trans. Database Syst., 26, 4, 476-519, (2001) · Zbl 1136.68386
[3] Grant, J.; Litwin, W.; Roussopoulos, N.; Sellis, T., Query languages for relational multidatabases, VLDB J., 2, 2, 153-171, (1993)
[4] Hull, R., Managing semantic heterogeneity in databases: a theoretical perspective, (Proceedings of the 1997 ACM Symposium on Principles of Database Systems, PODS’97, (1997)), 51-61
[5] Subrahmanian, V., Amalgamating knowledge bases, ACM Trans. Database Syst., 19, 2, 291-331, (1994)
[6] Catarci, T.; Lenzerini, M., Representing and using interschema knowledge in cooperative information systems, Int. J. Intell. Coop. Inf. Syst., 2, 4, 375-398, (1993)
[7] Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Nardi, D.; Rosati, R., Description logic framework for information integration, (Proceedings of the 6th International Conference on the Principles of Knowledge Representation and Reasoning, KR’98, (1998)), 2-13
[8] Genesereth, M. R.; Keller, A. M.; Duschka, O. M., Infomaster: an information integration system, (Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, (1997), ACM Press), 539-542
[9] Levy, A. Y.; Rajaraman, A.; Ordille, J. J., Querying heterogeneous information sources using source descriptions, (Proceedings of the 22th International Conference on Very Large Data Bases, (1996), Morgan Kaufmann Publishers Inc.), 251-262
[10] Rahm, E.; Bernstein, P. A., A survey of approaches to automatic schema matching, VLDB J., 10, 4, 334-350, (2001) · Zbl 1012.68909
[11] McCarthy, J.; Buvač, S., Formalizing context (expanded notes), (Aliseda, A.; van Glabbeek, R.; Westerståhl, D., Computing Natural Language, CSLI Lecture Notes, vol. 81, (1998), Center for the Study of Language and Information, Stanford University), 13-50 · Zbl 0953.03517
[12] Buvač, S., Quantificational logic of context, (Proceedings of the Thirteenth National Conference on Artificial Intelligence - vol. 1, AAAI’96, (1996), AAAI Press), 600-606
[13] Ghidini, C.; Giunchiglia, F., Local models semantics, or contextual reasoning = locality + compatibility, Artif. Intell., 127, 2, 221-259, (2001) · Zbl 0969.68141
[14] Serafini, L.; Stuckenschmidt, H.; Wache, H., A formal investigation of mapping language for terminological knowledge, (19th Joint Conference on Artificial Intelligence, IJCAI-05, (2005)), 576-581
[15] Euzenat, J.; Shvaiko, P., Ontology matching, (2007), Springer Berlin, Heidelberg · Zbl 1138.68488
[16] Maedche, A.; Motik, B.; Stojanovic, L., Managing multiple and distributed ontologies on the semantic web, VLDB J., 12, 4, 286-302, (2003)
[17] Kutz, O.; Lutz, C.; Wolter, F.; Zakharyaschev, M., ϵ-connections of abstract description systems, Artif. Intell., 156, 1, 1-73, (2004) · Zbl 1085.68162
[18] Serafini, L.; Borgida, A.; Tamilin, A., Aspects of distributed and modular ontology reasoning, (19th Joint Conference on Artificial Intelligence, IJCAI-05, (2005)), 570-575
[19] Mossakowski, T.; Lange, C.; Kutz, O., Three semantics for the core of the distributed ontology language, (Proc. of the 7th International Conference on Formal Ontology in Information Systems, FOIS 2012, (2012), IOS Press Graz, Austria), 337-352
[20] Konev, B.; Lutz, C.; Walther, D.; Wolter, F., Formal properties of modularisation, (Stuckenschmidt, H.; Parent, C.; Spaccapietra, S., Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, Lecture Notes in Computer Science/Theoretical Computer Science and General Issues Series, vol. 5445, (2009), Springer-Verlag Berlin, Heidelberg), 25-66 · Zbl 1242.68315
[21] Bao, J.; Voutsadakis, G.; Slutzki, G.; Honavar, V., Package-based description logics, (Stuckenschmidt, H.; Parent, C.; Spaccapietra, S., Modular Ontologies: Concepts, Theories and Techniques for Knowledge Modularization, Lecture Notes in Computer Science/Theoretical Computer Science and General Issues Series, vol. 5445, (2009), Springer-Verlag Berlin, Heidelberg), 349-371 · Zbl 1237.68202
[22] Bouquet, P.; Ghidini, C.; Serafini, L., Querying the web of data: a formal approach, (4th Asian Semantic Web Conference, ASWC 2009, LNCS, vol. 5926, (2009), Springer Berlin/Heidelberg, Shanghai, China), 291-305
[23] Hartig, O., SPARQL for a web of linked data: semantics and computability, (Proceedings of the 9th Extended Semantic Web Conference, ESWC2012, Lecture Notes in Computer Science, vol. 7295, (2012), Springer Heraklion, Greece), 8-23
[24] Bernstein, P. A.; Giunchiglia, F.; Kementsietsidis, A.; Mylopoulos, J.; Serafini, L.; Zaihrayeu, I., Data management for peer-to-peer computing: a vision, (WebDB 2002: Fifth International Workshop on the Web and Databases, (2002))
[25] Franconi, E.; Kuper, G.; Lopatenko, A.; Zairayeu, I., Queries and updates in the codb peer to peer database systems, (Proceedings of VLDB’04, 30th International Conference on Very Large Databases, (2004), Morgan Kaufmann), 1277-1280
[26] Halevy, A. Y.; Ives, Z. G.; Madhavan, J.; Mork, P.; Suciu, D.; Tatarinov, I., The piazza peer data management system, IEEE Trans. Knowl. Data Eng., 16, 7, 787-798, (2004)
[27] Calvanese, D.; De Giacomo, G.; Lenzerini, M.; Rosati, R., Logical foundations of peer-to-peer data integration, (Proceedings of the 23rd ACM SIGACT SIGMOD SIGART Symposium on Principles of Database Systems, PODS 2004, (2004)), 241-251
[28] Ghidini, C.; Serafini, L., Distributed first order logics, (Gabbay, D. M.; de Rijke, M., Frontiers Of Combining Systems 2, Studies in Logic and Computation, (1998), Research Studies Press), 121-140 · Zbl 1021.03007
[29] Bouquet, P.; Giunchiglia, F.; van Harmelen, F.; Serafini, L.; Stuckenschmidt, H., C-OWL: contextualizing ontologies, (Second International Semantic Web Conference, ISWC-03, Lecture Notes in Computer Science, vol. 2870, (2003), Springer), 164-179
[30] Ullman, J. D., Information integration using logical views, (Proceedings of the 6th International Conference on Database Theory, ICDT ’97, (1997), Springer-Verlag London, UK), 19-40
[31] Gabbay, D. M., Labelled deductive systems; principles and applications, vol. 1: introduction, Oxford Logic Guides, vol. 33, (1996), Oxford University Press Oxford
[32] Dinsmore, J., Partitioned representations, (1991), Kluwer Academic Publishers
[33] Masini, A., 2-sequent calculus: a proof theory of modalities, Ann. Pure Appl. Log., 58, 3, 229-246, (1992) · Zbl 0819.03045
[34] Lewis, D., Counterpart theory in quantified modal logic, J. Philos., 68, 113-124, (1968)
[35] Sciore, E.; Siegel, M.; Rosenthal, A., Using semantic values to facilitate interoperability among heterogeneous information systems, ACM Trans. Database Syst., 19, 2, 254-290, (1994)
[36] Bencivenga, E., Free logics, (Craig, E., Routledge Encyclopedia of Philosophy, vol. 3, (1998), Routledge London, New York), 738-739
[37] Ghidini, C.; Serafini, L., Distributed first order logics, (July 2015), Tech. Rep.
[38] Giunchiglia, F.; Serafini, L., Multilanguage hierarchical logics, or: how we can do without modal logics, Artif. Intell., 65, 1, 29-70, (1994) · Zbl 0787.68093
[39] Serafini, L.; Ghidini, C., Using wrapper agents to answer queries in distributed information systems, (Society, I. C., 4th International Conference on Multi-Agent Systems, ICMAS 2000, Boston, USA, (2000)), 429-430, (Poster Session) · Zbl 1051.68802
[40] Serafini, L.; Tamilin, A., Instance migration in heterogeneous ontology environments, (The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007, Busan, Korea, November 11-15, 2007, (2007)), 452-465
[41] Cuenca Grau, B.; Parsia, B.; Sirin, E., Working with multiple ontologies on the semantic web, (Proceedings of the Third International Semantic Web Conference, ISWC2004, Lecture Notes in Computer Science, vol. 3298, (2004)), 620-634
[42] Ceri, S.; Widom, J., Managing semantic heterogeneity with production rules and persistent queues, (Agrawal, R.; Baker, S.; Bell, D., 19th International Conference on Very Large Data Bases, Dublin, Ireland, Proceedings, August 24-27, 1993, (1993), Morgan Kaufmann), 108-119
[43] Gupta, A.; Widom, J., Local verification of global integrity constraints in distributed databases, (ACM SIGMOD International Conference on Management of Data, (1993)), 49-58
[44] Grefen, P. W.P. J.; Widom, J., Protocols for integrity constraint checking in federated databases, Distrib. Parallel Databases, 5, 4, 327-355, (1997)
[45] Barwise, J.; Seligman, J., Information flow: the logic of distributed systems, (1997), Cambridge University Press · Zbl 0927.03004
[46] Meilicke, C.; Stuckenschmidt, H.; Tamilin, A., Reasoning support for mapping revision, J. Log. Comput., 19, 5, 807-829, (2009) · Zbl 1194.68227
[47] Wang, P.; Xu, B., Debugging ontology mappings: a static approach, Comput. Inform., 27, 1, 21-36, (2008) · Zbl 05270996
[48] Brewka, G.; Eiter, T., Equilibria in heterogeneous nonmonotonic multi-context systems, (Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada, July 22-26, 2007, (2007)), 385-390
[49] Garson, J. W., Quantification in modal logic, Handbook of Philosophical Logic, Vol. II: Extensions of Classical Logic, 249-307, (1984), Springer Netherlands Dordrecht · Zbl 0875.03050
[50] Belardinelli, F., Counterpart semantics for quantified modal logic, (Tomala, O.; Honzik, R., The LOGICA Yearbook 2006, (2006)), 11-21
[51] Schwarz, W., Contingent identity, Philos. Compass, 8, 5, 486-495, (2013)
[52] Kracht, M.; Kutz, O., The semantics of modal predicate logic II: modal individuals revisited, (Intensionality 22, (2000)) · Zbl 1090.03005
[53] Makarios, S., A model theory for a quantified generalized logic of contexts [revision: 1.70], (2006), Knowledge Systems Laboratories, Stanford University, Tech. Rep. KSL-06-08
[54] Gratton, M. J., A strongly-local contextual logic, (Rossi, F., Proceedings of the 23rd International Joint Conference on Artificial Intelligence, (2013), AAAI Press Beijing, People’s Republic of China), 919-925
[55] McCarthy, J., Notes on formalizing context, (Proceedings of the 13th International Joint Conference on Artificial Intelligence, vol. 1, IJCAI’93, (1993), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 555-560
[56] Homola, M.; Serafini, L., Augmenting subsumption propagation in distributed description logics, Appl. Artif. Intell., 24, 1-2, 39-76, (2010)
[57] Santipantakis, G.; Vouros, G. A., Distributed reasoning with coupled ontologies: the E-\(\mathcal{S} H I Q\) representation framework, Knowl. Inf. Syst., 45, 2, 491-534, (2015)
[58] Ghidini, C.; Serafini, L., Mapping properties of heterogeneous ontologies, (Artificial Intelligence: Methodology, Systems, and Applications, (2008), Springer Berlin, Heidelberg), 181-193 · Zbl 1169.68622
[59] Ghidini, C.; Serafini, L.; Tessaris, S., On relating heterogeneous elements from different ontologies, (Kokinov, B.; Richardson, D.; Roth-Berghofer, T.; Vieu, L., Proceedings of the Sixth International and Interdisciplinary Conference on Modeling and Using Context, CONTEXT’07, Roskilde University, Denmark, Lecture Notes in Artificial Intelligence, vol. 4635, (2007), Springer), 234-247
[60] Manuel Atencia, A. B.; Euzenat, J.; Ghidini, C.; Serafini, L., A formal semantics for weighted ontology mappings, (Cudré-Mauroux, P.; Heflin, J.; Sirin, E.; Tudorache, T.; Euzenat, J.; Hauswirth, M.; Parreira, J. X.; Hendler, J.; Schreiber, G.; Bernstein, A.; Blomqvist, E., Proceedings of the 11th International Semantic Web Conference, ISWC2012, Lecture Notes in Computer Science, (2012), Springer Berlin, Heidelberg), 17-33
[61] Meilicke, C.; Stuckenschmidt, H.; Tamilin, A., Improving automatically created mappings using logical reasoning, (Ontology Matching, (2006), Citeseer), 61
[62] Meilicke, C.; Stuckenschmidt, H.; Tamilin, A., Repairing ontology mappings, (Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada, July 22-26, 2007, (2007)), 1408-1413
[63] Roelofsen, F.; Serafini, L., Minimal and absent information in contexts, (IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30-August 5, 2005, (2005)), 558-563
[64] Brewka, G.; Roelofsen, F.; Serafini, L., Contextual default reasoning, (IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, (2007)), 268-273
[65] Criscuolo, G.; Giunchiglia, F.; Serafini, L., A foundation for metareasoning, part I: the proof theory, J. Log. Comput., 12, 1, 167-208, (2002) · Zbl 1005.68149
[66] Criscuolo, G.; Giunchiglia, F.; Serafini, L., A foundation for metareasoning, part II: the model theory, J. Log. Comput., 12, 3, 345-370, (2002) · Zbl 1012.68194
[67] Benerecetti, M.; Giunchiglia, E.; Serafini, L.; Villafiorita, A., Formal specification of beliefs in multi-agent systems, Int. J. Intell. Syst., 14, 10, 1021-1040, (1999) · Zbl 0937.68113
[68] Ghidini, C., Modelling (un)bounded beliefs, (Bouquet, P.; Serafini, L.; Brezillon, P.; Benerecetti, M.; Castellani, F., Modelling and Using Context - Proceedings of the 2nd International and Interdisciplinary Conference, Context’99, Lecture Notes in Artificial Intelligence, vol. 1688, (1999), Springer Verlag Heidelberg), 145-158 · Zbl 0943.03014
[69] Fisher, M.; Ghidini, C., Programming resource-bounded deliberative agents, (Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI’99, (1999), Morgan Kaufmann Publ., Inc. Stockholm), 200-205
[70] Serafini, L.; Giunchiglia, F., ML systems: a proof theory for contexts, J. Log. Lang. Inf., 11, 4, 471-518, (2002) · Zbl 1011.03018
[71] Prawitz, D., Natural deduction - A proof theoretical study, (1965), Almquist and Wiksell Stockholm · Zbl 0173.00205
[72] Lemmon, E., Beginning logic, (1965), Hackett Publishing Company, Inc. · Zbl 0158.24406
[73] Henkin, L., The completeness of the first-order functional calculus, J. Symb. Log., 14, 3, 159-166, (1949) · Zbl 0034.00602
[74] Chang, C.; Keisler, J., Model theory, (1973), North Holland · Zbl 0276.02032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.