Query rewriting using views in the presence of inclusion dependencies

ABSTRACT

Query rewriting using views is an essential issue in data integration. A number of algorithms, e.g., the bucket algorithm, the inverse rules algorithm, the SVB algorithm and the MiniCon algorithm, have been proposed to address this issue. These algorithms can be divided into two categories: bucket-based algorithms and inverse rule-based algorithms. Some inverse rule-based algorithms have considered the problem of query rewriting in the presence of inclusion dependencies. However, there has been no bucket-base algorithm so far for the problem. All the previous bucket-based algorithms may miss query rewritings in the presence of inclusion dependencies. In this paper, we extend the MiniCon algorithm to the presence of inclusion dependencies. In the MiniCon algorithm, a view can be used in a non-redundant rewriting of a query only if at least one subgoal in the query is covered by a subgoal in the view. In the presence of inclusion dependencies, when no subgoal in a view directly covers the query subgoal we can apply the chase procedure and rule to the subgoals of the query or view that contains the chase reachable subgoals to get a revised query or view. The condition required by the MiniCon algorithm is then satisfied. We can therefore avoid the problem of missing rewritings with the previous bucket-based algorithms. We prove that our extended algorithm can find the maximally-contained rewriting of a conjunctive query using a set of conjunctive views in the presence of inclusion dependencies. Our extension of the MiniCon algorithm does not involve a significant increase in computational complexity and our new algorithm remains scalable.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Oliver M. Duschka , Michael R. Genesereth, Answering recursive queries using views, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-116, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263674]
• 3: O. M. Duschka, M. R. Genesereth, A. Y. Levy, Recursive Query Plans for Data Integration. Journal of Logic Programming, special issue on Logic Based Heterogeneous Information Systems, 43(1),49--73, 2000.
• 4: John Grant , Jack Minker, A logic-based approach to data integration, Theory and Practice of Logic Programming, v.2 n.3, p.323-368, May 2002 [doi>10.1017/S1471068401001375]
• 5: J. Gryz, An Algorithm for Query Folding with Inclusion Dependencies. Intelligent Information Systems VII Proceedings of the Workshop, Malbork, Poland, June, 1998.
• 6: Jarek Gryz, Query Folding with Inclusion Dependencies, Proceedings of the Fourteenth International Conference on Data Engineering, p.126-133, February 23-27, 1998
• 7: Jarek Gryz, Query rewriting using views in the presence of functional and inclusion dependencies, Information Systems, v.24 n.7, p.597-612, Nov. 1999 [doi>10.1016/S0306-4379(99)00034-4]
• 8: D. S. Johnson, A. Klug, Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. Journal of Computer and System Sciences, 28:167--189 (1984).
• 9: 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]
• 10: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 11: A. Y. Levy, A. Rajaraman, J. J. Ordille, Query-Answering Algorithms for Information Agents. In Proceedings of AAAI, 1996.
• 12: Prasenjit Mitra, An algorithm for answering queries efficiently using views, Proceedings of the 12th Australasian database conference, p.99-106, January 29-February 01, 2001, Queensland, Australia
• 13: Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
• 14: Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
• 15: Junhu Wang , Michael Maher , Rodney Topor, Rewriting general conjunctive queries using views, Proceedings of the thirteenth Australasian database conference, p.197-206, January 01, 2002, Melbourne, Victoria, Australia

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms

Keywords:
data integration systems, inclusion dependencies, query rewriting using views