Theory of answering queries using views

ABSTRACT

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has recently received significant attention because of its relevance to a wide variety of data management problems, such as query optimization, the maintenance of physical data independence, data integration and data warehousing. This article surveys the theoretical issues concerning the problem of answering queries using views.

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: [2] Serge Abiteboul, Peter Buneman, and Dan Suciu. Data on the Web. Morgan Kaufmann, 1999.
• 3: [3] Foto Afrati. Personal communication, 2000.
• 4: Foto N. Afrati , Manolis Gergatsoulis , Theodoros G. Kavalieros, Answering Queries Using Materialized Views with Disjunctions, Proceedings of the 7th International Conference on Database Theory, p.435-452, January 10-12, 1999
• 5: Sanjay Agrawal , Surajit Chaudhuri , Vivek R. Narasayya, Automated Selection of Materialized Views and Indexes in SQL Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.496-505, September 10-14, 2000
• 6: 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]
• 7: Randall G. Bello , Karl Dias , Alan Downing , James J. Feenan, Jr. , James L. Finnerty , William D. Norcott , Harry Sun , Andrew Witkowski , Mohamed Ziauddin, Materialized Views in Oracle, Proceedings of the 24rd International Conference on Very Large Data Bases, p.659-664, August 24-27, 1998
• 8: Alexander Borgida, Description Logics in Data Management, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.671-682, October 1995 [doi>10.1109/69.469829]
• 9: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, Rewriting of regular expressions and regular path queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.194-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303996]
• 10: Answering Regular Path Queries Using Views, Proceedings of the 16th International Conference on Data Engineering, p.389, February 28-March 03, 2000
• 11: Diego Calvanese , Moshe Y. Vardi , Giuseppe de Giacomo , Maurizio Lenzerini, View-based query processing for regular path queries with inverse, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.58-66, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335207]
• 12: [12] Diego Calvanese, Giuseppe De Giacorno, and Maurizio Lenzerini. Answering queries using views in description logics. In Working notes of the KRDB Workshop, 1999.
• 13: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 14: Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
• 15: [15] Rada Chirkova and Michael Genesereth. Linearly bounded reformulations of conjunctive databases. In Proc. of DOOD, 2000.
• 16: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 17: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 18: [18] Jan Van den Bussche. Two remarks on the complexity of answering queries using views. To appear in Information Processing Letters, 2000.
• 19: Alin Deutsch , Lucian Popa , Val Tannen, Physical Data Independence, Constraints, and Optimization with Universal Plans, Proceedings of the 25th International Conference on Very Large Data Bases, p.459-470, September 07-10, 1999
• 20: [20] Oliver Duschka, Michael Genesereth, and Alon Levy. Recursive query plans for data integration, newblock Journal of Logic Programming, 43(1):49-73, 2000.
• 21: Oliver Michael Duschka , Michael R. Genesereth, Query planning and optimization in information integration, Stanford University, Stanford, CA, 1998
• 22: 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]
• 23: Daniela Florescu , Alon Y. Levy , Dan Suciu , Khaled Yagoub, Optimization of Run-time Management of Data Intensive Web-sites, Proceedings of the 25th International Conference on Very Large Data Bases, p.627-638, September 07-10, 1999
• 24: [24] Daniela D. Florescu. Search Spaces for Object-Oriented Query Optimization. PhD thesis, Univerisity of Paris VI, France, 1996.
• 25: [25] M. Friedman and D. Weld. Efficient execution of information gathering plans. In Proceedings of the International Joint Conference on Artificial Intelligence, Nagoya, Japan, 1997.
• 26: Gösta Grahne , Alberto O. Mendelzon, Tableau Techniques for Querying Information Sources through Global Schemas, Proceedings of the 7th International Conference on Database Theory, p.332-347, January 10-12, 1999
• 27: Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303994]
• 28: Stéphane Grumbach , Leonardo Tininini, On the content of materialized aggregate views, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.47-57, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335174]
• 29: Jarek Gryz, Query Folding with Inclusion Dependencies, Proceedings of the Fourteenth International Conference on Data Engineering, p.126-133, February 23-27, 1998
• 30: 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]
• 31: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 32: Zachary Ives , Alon Levy , Jayant Madhavan , Rachel Pottinger , Stefan Saroiu , Igor Tatarinov , Shiori Betzler , Qiong Chen , Ewa Jaslikowska , Jing Su , Wai Tak Theodora Yeung, Self-organizing data sharing communities with SAGRES, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.582, May 15-18, 2000, Dallas, Texas, United States
• 33: [33] Chung T. Kwok and Daniel S. Weld. Planning to gather information. In Proceedings of the AAAI Thirteenth National Conference on Artificial Intelligence, 1996.
• 34: Eric Lambrecht , Subbarao Kambhampati , Senthil Gnanaprakasam, Optimizing Recursive Information-Gathering Plans, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1204-1211, July 31-August 06, 1999
• 35: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 36: 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
• 37: Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
• 38: Reée J. Miller, Using schematically heterogeneous structures, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.189-200, June 01-04, 1998, Seattle, Washington, United States
• 39: Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335208]
• 40: Yannis Papakonstantinou , Vasilis Vassalos, Query rewriting for semistructured data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.455-466, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 41: 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
• 42: Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
• 43: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]
• 44: Vasilis Vassalos , Yannis Papakonstantinou, Describing and Using Query Capabilities of Heterogeneous Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.256-265, August 25-29, 1997
• 45: H. Z. Yang , Per-Åke Larson, Query Transformation for PSJ-Queries, Proceedings of the 13th International Conference on Very Large Data Bases, p.245-254, September 01-04, 1987
• 46: Markos Zaharioudakis , Roberta Cochrane , George Lapis , Hamid Pirahesh , Monica Urata, Answering complex SQL queries using automatic summary tables, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.105-116, May 15-18, 2000, Dallas, Texas, United States

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.3 Languages
          Subjects: Query languages

General Terms:
Design, Languages, Management, Performance, Theory