Loading data into description reasoners

ABSTRACT

Knowledge-base management systems (KBMS) based on description logics are being used in a variety of situations where access is needed to large amounts of data stored in existing relational databases. We present the architecture and algorithms of a system that converts most of the inferences made by the KBMS into a collection of SQL queries, thereby relying on the optimization facilities of existing DBMS to gain efficiency, while maintaining an object-centered view of the world with a substantive semantics and significantly different reasoning facilities than those provided by Relational DBMS and their deductive extensions. We address a number of optimization issues that arise in the translation process due to the fact that SQL queries with different syntax (but identical semantics) are not treated uniformly by current database management systems.

REFERENCES

• 1: IntelliCorp, "Bridging the information gap," in A Review of Products, Services, and Research, AAAI-87, Seattle, 1987, pp. 70-71.
• 2: Tarek M. Anwar , Howard W. Beck , Shamkant B. Navathe, Knowledge Mining by Imprecise Querying: A Classification-Based Approach, Proceedings of the Eighth International Conference on Data Engineering, p.622-630, February 03-07, 1992
• 3: Howard W. Beck , Sunit K. Gala , Shamkant B. Navathe, Classification as a Query Processing Technique in the CANDIDE Semantic Data Model, Proceedings of the Fifth International Conference on Data Engineering, p.572-581, February 06-10, 1989
• 4: Beck, H. W., Anwar, T. M., and Navathe, S. B., "Classification through conceptual clustering in database systems," Proc. i st Intl. Conf. on Information and Knowledge Management, Baltimore, MD, November, 1992, pp. 465-472.
• 5: H. W. Beck , T. Anwar , S. B. Navathe, A Conceptual Clustering Algorithm for Database Schema Design, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.396-411, June 1994 [doi>10.1109/69.334862]
• 6: Sonia Bergamaschi , Flavio Bonfatti , Claudio Sartori, Entity-Situation: A Model for the Knowledge Representation Module of a KBMS, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.578-582, March 14-18, 1988
• 7: Sonia Bergamaschi , Claudio Sartori, On taxonomic reasoning in conceptual design, ACM Transactions on Database Systems (TODS), v.17 n.3, p.385-422, Sept. 1992 [doi>10.1145/132271.132272]
• 8: Borgida, A., "A new look at the foundations and utility of Description Logics (or Terminological Logics are not just for the Flightless Birds)," Technical Report, Rutgers University, 1992.
• 9: Alexander Borgida , Ronald J. Brachman , Deborah L. McGuinness , Lori Alperin Resnick, CLASSIC: a structural data model for objects, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.58-67, June 1989, Portland, Oregon, United States
• 10: Borgida, A., and Brachman, R. J., "Intelligence in the interface," Proc. Pnd Intl. Workshop on Intelligent and Cooperative Information Systems: Core Technology for Next Generation Information Systems, Como, Italy, October, 1991, pp. 68-75.
• 11: Brachman, R. J., Selfridge, P. G., Terveen, L. G., Altman, B., Borgida, A., Halper, F., Kirk, T., Lazar, A., McGuinness, D. L., and Resnick, L. A., "Knowledge representation support for data archaeology," Proc. 1st Intl. Conf. on Information and Knowledge Management, Baltimore, MD, November, 1992, pp. 457-464.
• 12: Ceri, S., Gottlob, G., and Wiederhold, G., "interfacing relational databases and Prolog efficiently," Proc. 1st Intl. Conf. on Expert Database Systems, Charleston, SC, April, 1986, pp. 207-223.
• 13: Yih-Farn Chen , Michael Y. Nishimoto , C. V. Ramamoorthy, The C Information Abstraction System, IEEE Transactions on Software Engineering, v.16 n.3, p.325-334, March 1990 [doi>10.1109/32.48940]
• 14: Prem Devanbu , Ron Brachman , Peter G. Selfridge, LaSSIE: a knowledge-based software information system, Communications of the ACM, v.34 n.5, p.34-49, May 1991 [doi>10.1145/103167.103172]
• 15: Devanbu, P., "Translating description logics to information server queries," Technical Report, AT&T Bell Laboratories, May, 1992.
• 16: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• 17: S. Ghosh , C. C. Lin , T. Sellis, Implementation of a Prolog-INGRES interface, ACM SIGMOD Record, v.17 n.2, p.77-88, June 1988 [doi>10.1145/51708.51713]
• 18: Heinsohn, J., Kudenko, D., Nebel, B., and Profitlich, H.-J., "An empirical analysis of terminological representation systems," Proc. AAAI.gP, San Jose, CA, July, 1992, pp. 767-773.
• 19: Illarramendi, A., Blanco, J. M., and Gofii, A., "A uniform approach to design a federated system using BACK," Proc. Terminological Logic Users Workshop, KIT-Report 95, Technische Universit/it Berlin, Berlin, October, 1991, pp. 61-85.
• 20: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 21: William Kent, Limitations of record-based information models, ACM Transactions on Database Systems (TODS), v.4 n.1, p.107-131, March 1979 [doi>10.1145/320064.320070]
• 22: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 23: William Mark , Sherman Tyler , James McGuire , Jon Schlossberg, Commitment-Based Software Development, IEEE Transactions on Software Engineering, v.18 n.10, p.870-885, October 1992 [doi>10.1109/32.163604]
• 24: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• 25: Nebel, B., and Peltason, C., "Terminological reasoning and information management," in Information Systems and Artificial intelligence. D. Karagianis, ed.. Springer-Verlag, 1991, pp. 181-212.
• 26: Patel-Schneider, P. F., Brachman, R. J., and Levesque, H. J., "ARGON: Knowledge representation meets information retrieval," Proc. 1st Conf. on Artificial Intelligence Applications, Denver, December, 1984, pp. 280-286.
• 27: Tou, F. N., Williams, M. D., Fikes, R., Henderson, A., and Malone, T., "RABBIT: An intelligent database assistant," Proc. AAAI'82, Pittsburgh, pp. 314-318.
• 28: Yannis Vassiliou , James Clifford , Matthias Jarke, How Does an Expert System Get its Data? (Extended Abstract), Proceedings of the 9th International Conference on Very Large Data Bases, p.70-72, October 31-November 02, 1983
• 29: Gio Wiederhold, Mediators in the Architecture of Future Information Systems, Computer, v.25 n.3, p.38-49, March 1992 [doi>10.1109/2.121508]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL

General Terms:
Algorithms, Design, Languages, Performance