Query reformulation with constraints

ABSTRACT

Let Σ1, Σ2 be two schemas, which may overlap, C be a set of constraints on the joint schema Σ1 ∪ Σ2, and q1 be a Σ1-query. An (equivalent) reformulation of q1 in the presence of C is a Σ2-query, q2, such that q2 gives the same answers as q1 on any Σ1 ∪ Σ2-database instance that satisfies C. In general, there may exist multiple such reformulations and choosing among them may require, for example, a cost model.

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: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: S. Adali , K. S. Candan , Y. Papakonstantinou , V. S. Subrahmanian, Query caching and optimization in distributed mediator systems, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.137-146, June 04-06, 1996, Montreal, Quebec, Canada
• 4: Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Theoretical Computer Science, v.116 n.1, p.59-94, Aug. 2, 1993
• 5: Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984 [doi>10.1145/1634.1636]
• 6: Peter Buneman , Shamim Naqvi , Val Tannen , Limsoon Wong, Principles of programming with complex objects and collection types, Theoretical Computer Science, v.149 n.1, p.3-48, Sept. 18, 1995
• 7: Andrea Calì , Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Data Integration under Integrity Constraints, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.262-279, May 27-31, 2002
• 8: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 9: 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]
• 10: Alin Bernard Deutsch , Val Tannen, Xml query reformulation over mixed and redundant storage, 2002
• 11: 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
• 12: A. Deutsch and V. Tannen. MARS: A System for Publishing XML from Mixed and Redundant Storage. In VLDB, pages 201--212, 2003.
• 13: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 14: Alin Deutsch , Val Tannen, XML Queries and constraints, containment and reformulation, Theoretical Computer Science, v.336 n.1, p.57-87, 25 May 2005 [doi>10.1016/j.tcs.2004.10.032]
• 15: 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]
• 16: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 17: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 18: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 19: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 20: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065187]
• 21: 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]
• 22: Christoph Koch, Query Rewriting with Symmetric Constraints, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.130-147, February 20-23, 2002
• 23: S. Kazem Lellahi , Val Tannen, A Calculus for Collections and Aggregates, Proceedings of the 7th International Conference on Category Theory and Computer Science, p.261-280, September 04-06, 1997
• 24: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 25: 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]
• 26: 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
• 27: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 28: Lucian Popa , Val Tannen, Object/relational query optimization with chase and backchase, 2000
• 29: Lucian Popa , Alin Deutsch , Arnaud Sahuguet , Val Tannen, A chase too far?, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.273-284, May 15-18, 2000, Dallas, Texas, United States
• 30: Lucian Popa , Val Tannen, An Equational Chase for Path-Conjunctive Queries, Constraints, and Views, Proceeding of the 7th International Conference on Database Theory, p.39-57, January 10-12, 1999
• 31: L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating Web Data. In VLDB, pages 598--609, 2002.
• 32: Jayavel Shanmugasundaram , Jerry Kiernan , Eugene J. Shekita , Catalina Fan , John Funderburk, Querying XML Views of Relational Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.261-270, September 11-14, 2001
• 33: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design