Answering queries using views: A KRDB perspective for the semantic Web

ABSTRACT

In this article, we investigate a first step towards the long-term vision of the Semantic Web by studying the problem of answering queries posed through a mediated ontology to multiple information sources whose content is described as views over the ontology relations. The contributions of this paper are twofold. We first offer a uniform logical setting which allows us to encompass and to relate the existing work on answering and rewriting queries using views. In particular, we make clearer the connection between the problem of rewriting queries using views and the problem of answering queries using extensions of views. Then we focus on an instance of the problem of rewriting conjunctive queries using views through an ontology expressed in a description logic, for which we exhibit a complete algorithm.

REFERENCES

• 1: Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275516]
• 2: Franz Baader , Diego Calvanese , Deborah L. McGuinness , Daniele Nardi , Peter F. Patel-Schneider, The description logic handbook: theory, implementation, and applications, Cambridge University Press, New York, NY, 2003
• 3: Baader, F., Küsters, R., and Molitor, R. 2000. Rewriting concepts using terminologies. In Proceedings of the Seventh International Conference on Knowledge Representation and Reasoning (KR2000), A. Cohn, F. Giunchiglia, and B. Selman, Eds. Morgan Kaufmann Publishers, San Francisco, CA, 297--308.
• 4: Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset, Rewriting queries using views in description logics, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.99-108, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263673]
• 5: Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic web. In Scientific American, May.
• 6: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-158, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275504]
• 7: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Answering Queries Using Views over Description Logics Knowledge Bases, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.386-391, July 30-August 03, 2000
• 8: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 9: Diego Calvanese , Giuseppe de Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-Based Query Processing and Constraint Satisfaction, Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, p.361, June 26-29, 2000
• 10: Donini, F. M., Lenzerini, M., Nardi, D., and Schaerf, A. 1994. Deduction in concept languages: From subsumption to instance checking. J. Logic Computation 4, 4.
• 11: Oliver M. Duschka , Michael R. Genesereth, Query planning in infomaster, Proceedings of the 1997 ACM symposium on Applied computing, p.109-111, April 1997, San Jose, California, United States [doi>10.1145/331697.331719]
• 12: Goasdoué, F. 2001. Réécriture de requêtes en termes de vues dans carin et intégration d'informations. Ph.D. thesis, Université Paris Sud XI---Orsay.
• 13: Goasdoué, F., Lattes, V., and Rousset, M.-C. 2000. The use of carin language and algorithms for information integration: the picsel system. Int. J. Coop. Info. Sys. 9, 383--401.
• 14: Goasdoué, F. and Rousset, M.-C. 2002. Compilation and approximation of conjunctive queries by concept descriptions. In ECAI 2002, F. van Harmelen, Ed. 267--271. IOS Press.
• 15: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 16: Levy, A., Rajamaran, A., and Ordille, J. 1996. Query-answering algorithms for information agents. In Proceedings of the thirtenth AAAI conference on Artificial Intelligence: AAAI'96.
• 17: Alon Y. Levy , Marie-Christine Rousset, Combining Horn rules and description logics in CARIN, Artificial Intelligence, v.104 n.1-2, p.165-209, Sept. 1998 [doi>10.1016/S0004-3702(98)00048-4]
• 18: Mkbeem. http://www.mkbeem.com.
• 19: Nardi, D., Donini, F., Lenzerini, M., and Schaerf, A. 1995. Principles of Artificial Intelligence. Springer-Verlag, Chapter Reasoning in description logics.
• 20: Picsel. http://www.lri.fr/∼picsel.
• 21: Chantal Reynaud , Brigitte Safar, Representation of Ontologies for Information Integration, Proceedings of the 13th International Conference on Knowledge Engineering and Knowledge Management. Ontologies and the Semantic Web, p.270-284, October 01-04, 2002
• 22: Rousset, M.-C. 1999. Backward reasoning in aboxes for query answering. In Proceedings of DL'99 and KRDB'99.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: General systems theory

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representation languages

General Terms:
Algorithms, Theory

Keywords:
Information integration, knowledge representation, semantic web