Amalgamating knowledge bases

Abstract

The integration of knowledge for multiple sources is an important aspect of automated reasoning systems. When different knowledge bases are used to store knowledge provided by multiple sources, we are faced with the problem of integrating multiple knowledge bases: Under these circumstances, we are also confronted with the prospect of inconsistency. In this paper we present a uniform theoretical framework, based on annotated logics, for amalgamating multiple knowledge bases when these knowledge bases (possibly) contain inconsistencies, uncertainties, and nonmonotonic modes of negation. We show that annotated logics may be used, with some modifications, to mediate between different knowledge bases. The multiple knowledge bases are amalgamated by a transformation of the individual knowledge bases into new annotated logic programs, together with the addition of a new axiom scheme. We characterize the declarative semantics of such amalgamated knowledge bases and study how the semantics of the amalgam is related to the semantics of the individual knowledge bases being combined.—Author's Abstract

References

1. ADAL1, S., AND SUBRAHMANIAN, V. S. 1993. Integrating multiple knowledge bases. To be published.
2. ANAND, R., AND SUBRAHMANIAN, V. S. 1987. FLOG: A logic programming system based on a six-valued logic. In AAAI/Xerox 2nd International Symposium on Knowledge Engineering- (Madrid, Spain). AAAI, Menlo Park, Calif.
3. BARAL, C., AND SUBRAHMANIAN, V. S. 1993. Dualities between alternative semantics for logSc programming and non-monotonic reasoning. J. Autom. Reasoning 10, 399-420. (Preliminary version in Proceedings of the 1991 International Workshop on Logic Programm~ng and Non-Monoton~c Reasoning, A. Nerode, W. Marek, and V. S. Subrahmanian, Eds. MIT Press, Cambridge, Mass.)
4. BARAL, C., KRAUS, S., AND MINKER, J. 1991.Combining multiple knowledge bases. IEEE Trans. Knowl. Data Eng. 3, 2 (June), 200-220.
5. BARAL, C., KRAUS. S., MINAER, J., AND SUnRAHMANLiN, V. S. 1992. Combining knowledge bases consisting of first order theories. Comput. Intell. 8, I (Mar.), 45-71.
6. BLAIR, H. A., ANa SUaRAHMANIAN, V. S. 1987. Paraconsistent logic programming. Theor. Comput. Sci. 68, 35-54. (Preliminary version in Lecture Notes in Computer Science, vol. 287, Springer- Verlag, New York.)
7. BOWEN, K., AND KOWALSKI, R. 1982. Amalgamating language and metalanguage in logic programming. In Logic Programming, K. L. Clark and S.-A. Tarnlund, Eds., Academic Press, New York, 153-172.
8. DA COSTA, N. C. A., SUBRAHMANIAN, V. S., AND VAGO, C. 1991. The paraconsistent logics ~T. Zeitschr~ft zut Mathemat~sche Logic und Grundlagen der Mathematic 37, 139-148.
9. DUBOIS, D., LANG, J., AND PRADE, S. 1992. Dealing with multi-source information in possibilistic log~c. Proceedings of the lOth European Conference on Artificial Intelligence. Wiley, New York.
10. Dunots, D., LANG, J., AND PRADE, H. 1991a. Towards possibilistic logSc programming. In Proceed~ngs of the 1991 International Conference on Logic Programming, K. Furukawa, Ed. MIT Press, Cambridge, Mass., 581-595.
11. DUBOIS, D., LANG, J., AND PRADE, H. 1991b. Timed possibilistic logic. Fundamenta In/brmaticae XV, 3 4, 211-234.
12. ETHERIN6TON, D. 1988. Reasoning w~th Incomplete Informatwn. Pitman, Marshfield, Mass.
13. FAGIN, R., KUPER, G., ULLMAN, J., AND VARDI, M. 1986. Updating logical databases. In Advances in Computing Research. Vol. 3. JAI Press, Greenwich, Conn., 1-18.
14. FAGIN, R., ULLMAN, J. D., AND VARDI, M. Y. 1983. On the semantics of updates in databases. In Proceed~ngs of the ACM SIGACT/SIGMOD Symposium on Principles of Database Systems. ACM, New York, 352 365.
15. FITTING, M. C. 1993. The family of stable models. J. Logic Program. 17, 197 225.
16. FITTING, M. C. 1991a. Bilattices and the semantics oflogic programming. J. Logic Program. 11, 91-116.
17. FITTINa, M. C. 1991b. Well-founded semantics, generalized. In Proceedings ofthe 1991 Internatlonal Logic Programming Symposzum. MIT Press, Cambridge, Mass., 71 83.
18. FITTING, M. C., 1989. Negation as refutation. In Proceedings of the 4th IEEE Symposium on Logic in Computer Science. IEEE, New York, 63-70.
19. GELFOND, M., AND LIFSCHITZ, V. 1988. The stable model semantics for logic programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming. R. A. Kowalski and K. A. Bowen, Eds. MIT Press, Cambridge, Mass., 1070-1080.
20. GINSBERG, M. L. 1988. Multivalued logics: A uniform approach te reasoning in artificial intelligence. Comput. Intell. 4, 265-316.
21. GRANT, J., LITWIN, W., ROUSSOPOULOS, N., AND SELLIS, T. 1991. An algebra and calculus for relational multidatabase systems. In Proceedings of the 1st International Workshop on Interoperability in Multidatabse Systems. IEEE, New York, 118-124.
22. HENSCHEN, L. J., AND LU, J. J. 1992. The completeness of Gp-resolutmn for annotated logics. Inf. Process. Lett. 44, 135 140.
23. HENSCHEN, L. J., AND LU, J. J. 1991. The paraconsistent closed world assumptlon. Theor. Comput. Sct. To be published.
24. IOANNIDIS, Y., AND SELL1S, T. 1989. Conflict resolution of rules assigning values to virtual attributes. In Proceedings of the ACM SIGMOD Symposium on Management of Data. ACM, New York
25. KIFER, M., AND KRISHNAPRASAD, T. 1993. A theory of non-monotonic inhentance based on annotated logic. Artif. Intell. 60, I (Mar.) 23 50.
26. KJFER, M., AND LI, A. 1988 On the semantics of rule-based expert systems with uncertainty. In 2nd International Conference on Database Theor~, M. Gyssens, J. Parendaens, and D. Van Gucht, Eds. Bruges, Belgium, 102-117.
27. KIFER, M, AND LOZINS~I, E 1992. A logic for reasoning with inconsistency J Autom. Reasonmg 9, 2, 179-215.
28. t~IFEI~, M., AND LOZINS~II, E. 1989 RI: A logic for reasoning with inconsistency. In 4th IEEE Symposzum on Log~c ~n Computer Science (Amlomar, Cahf.) IEEE, New York, 253 262.
29. AEFER, M, AND SUBRAHM^NIAN, V. S. 1989 Theory of generalized annotated logm programming and its applications. J. Log~c Program. 12, 4, 335 368. (Preliminary version in Proceedings of the 1989 North Amertcan Conference on Logzc Programmzng, MIT Press, Cambridge, Mass.).
30. KIFER, M., AND WU, J. 1989 A logSc for object oriented logm programming. In Proceedmgs of the 8th ACM SIGACT/SIGMOD /SIGART Symposium on Princ~ples of Database Systems (Philadelphia, Pa.). ACM, New York, 379-393.
31. KIFE~, M., AE~SHN~^SAD, T., AND WARRE~, D S. 1989. On the declarative semantics of inheritance networks. In Proceedings of the 1989 Internatzonal Joznt Conference on Artlfic~al Intelltgence. Morgan-Kauffman, Los Altos, Calif., 1099-1103.
32. LLOYD, J. W., 1987. Foundat~ons ofLogic Programming. Springer-Verlag, New York.
33. Lu, J. J. 1992. Automated deduction in paraconsistent logics. Ph.D. thesis, Electrical EngSneering and Computer Science, Northwestern Univ., Evanston, Ill., May.
34. MAREK, W., NERODE, A., AND REMMEL, J. 1992. The stable models of a predicate logic program In Proceedmgs of the 1992 International Conference on Logzc Programming, K. R. Apt, Ed. MIT Press, Cambridge, Mass.
35. MAREK, W., NERODE, A., AND REMMEL, J. 1990. A theory of non-monotonic rule systems, I. Ann. Math. Art~f. Intell (Preliminary version in Proceedings of the 1990 Conference on Logic in Computer Sc~ence.)
36. MURRAY, N. V., AND ROSENTHAL, E. 1991. S~gned formulas. A classical approach to multiple-valued log5cs Tech. Rep. TR-91-12, Computer Science Dept., State Univ of New York at Albany.
37. NG, R. T., AND SUBRAHMANIAE, V. S. 1991. A semantical framework for supporting subjective and condltional probabilities in deductive databases. J. Autom. Reasoning 10, 2, 191-235 (Preliminary version in Proceedlngs of the 1991 International Conference on Loglc Programmlng, MIT Press, Cambndge, Mass.)
38. NG, R. T, AND SU~RAHMM~M, V. S. 1990 Probabilistic logSc programming. Inf. Comput. 101, 2, 150-201. (Preliminary version in Proceedmgs of the 1990 Internatzonal Symposium on Methodologies for Intelligent Systems. North-Holland, Amsterdam, The Netherlands )
39. SAKAMA, C. 1992. Extended well-founded semantics for paraconsistent logic programs. In Proceed~ngs of the 1992 International Conference on 5th Generat~on Computer Svstems (Tokyo~ Japan).
40. SILBERSCHATZ, A., STONEBRAKER, M, AND ULLMAN, J. D. 1991. Database systems Achievements and opportunities. Commun. ACM 34, 10 (Oct.), 110 120
41. SUBRAHMANIAN, V. S. 1992. Paraconmstent disjunct~ve deductive databases. Theor. Comput. Sc~ 93, 115 141.
42. SUB~^HMAMM, V. S. 1989. A simple formulation of the theory of metalogSc programming. In Meta-Programrning en Log~c Programm~ng~ H. Abramson and M. Rogers, Eds., MIT Press, Cambridge, Mass, 65 101.
43. SUB~HMM~^N, V. S. 1987 On the unsemantics of quantitative log~c programs. In Proceed~r~gs of the 1987 IEEE OEvmpos~um on Log~c Programmmg. IEEE, New York, 173-182
44. VAN GELDER, A. 1989. The alternating fixpoint of logic programs with negation. In Proceedmgs of the 8th ACM Symposium on Principles of Database Systems. ACM, New York, i 10.
45. VAN GELDER, A., ROSS, K., AND SCHLIPF, J. 1988. Unfounded sets and well-founded semantics for general logic programs. In Proceedings of the 7th ACM Symposium on Principles of Database Systems. ACM, New York, 221-230.
46. WHANG, W. K., NAVATHE, S. B., AND CHAKRAVARTHY, S. 1991. Logic-based approach for realizing a federated information system. In Proceedings ofthe 1st International Workshop on Interoperability in Multidatabase Systems. IEEE, New York, 92-100.
47. ZICARL R., CERL S., AND TANCA, L. 1991. Interoperability between a rule-based database language and an object-oriented language. In Proceedings of the 1st International Workshop on Interoperability in Multidatabase Systems. IEEE, New York, 125-135.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

  • Machine learning

    • Machine learning approaches

      • Rule learning

• Information systems

  • Data management systems

    • Information integration

      • Extraction, transformation and loading

• Software and its engineering

  • Software organization and properties

    • Extra-functional properties

      • Interoperability