Alin Deutsch
Val Tannen
Skip Abstract Section
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.
- S. Abiteboul and O. M. Duschka. Complexity of Answering Queries Using Materialized Views. In PODS, pages 254--263, 1998.]] Google Scholar
Digital Library
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]] Google ScholarDigital Library
- S. Adali, K. S. Candan, Y. Papakonstantinou, and V. Subrahmanian. Query Caching and Optimization in Distributed Mediator Systems. In SIGMOD, pages 137--148, 1996.]] Google ScholarDigital Library
- C. Beeri and Y. Kornatzky. Algebraic Optimisation of Object Oriented Query Languages. TCS, 116(1):59--94, 1993.]] Google ScholarDigital Library
- C. Beeri and M. Y. Vardi. A Proof Procedure for Data Dependencies. JACM, 31(4):718--741, 1984.]] Google ScholarDigital Library
- P. Buneman, S. Naqvi, V. Tannen, and L. Wong. Principles of Programming with Collection Types. TCS, 149(1):3--48, 1995.]] Google ScholarDigital Library
- A. Calì, D. Calvanese, G. D. Giacomo, and M. Lenzerini. Data Integration under Integrity Constraints. In CAiSE, pages 262--279, 2002.]] Google ScholarDigital Library
- R. G. G. Cattell, D. K. Barry, M. Berler, J. Eastman, D. Jordan, C. Russell, O. Schadow, T. Stanienda, and F. Velez, editors. The Object Data Standard: ODMG 3.0. Morgan Kaufmann, 2000.]] Google ScholarDigital Library
- A. K. Chandra and P. M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In STOC, pages 77--90, 1977.]] Google ScholarDigital Library
- A. Deutsch. XML Query Reformulation Over Mixed and Redundant Storage. PhD thesis, Dept. of Computer and Information Sciences, University of Pennsylvania, 2002.]] Google ScholarDigital Library
- A. Deutsch, L. Popa, and V. Tannen. Physical Data Independence, Constraints and Optimization with Universal Plans. In VLDB, pages 459--470, 1999.]] Google ScholarDigital Library
- A. Deutsch and V. Tannen. MARS: A System for Publishing XML from Mixed and Redundant Storage. In VLDB, pages 201--212, 2003.]]Google ScholarDigital Library
- A. Deutsch and V. Tannen. Reformulation of XML Queries and Constraints. In ICDT, pages 225--241, 2003.]] Google ScholarDigital Library
- A. Deutsch and V. Tannen. XML Queries and Constraints, Containment and Reformulation. TCS, 336(1):57--87, 2005.]] Google ScholarDigital Library
- O. M. Duschka and M. R. Genesereth. Answering recursive queries using views. In PODS, pages 109--116, 1997.]] Google ScholarDigital Library
- R. Fagin. Horn Clauses and Database Dependencies. JACM, 29(4):952--985, Oct. 1982.]] Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. In ICDT, pages 207--224, 2003.]] Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. TCS, 336(1):89--124, 2005.]] Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, and L. Popa. Data Exchange: Getting to the Core. ACM TODS, 30(1):174--210, 2005.]] Google ScholarDigital Library
- G. Gottlob. Computing Cores for Data Exchange: New Algorithms and Practical Solutions. In PODS, 2005.]] Google ScholarDigital Library
- A. Halevy. Answering Queries Using Views: A Survey. VLDB Journal, pages 270--294, 2001.]] Google ScholarDigital Library
- C. Koch. Query Rewriting with Symmetric Constraints. In Proceedings of FoIKS (LNCS 2284), pages 130--147, 2002.]] Google ScholarDigital Library
- K. Lellahi and V. Tannen. A calculus for collections and aggregates. In E. Moggi and G. Rosolini, editors, LNCS 1290: Category Theory and Computer Science (Proceedings of CTCS'97), pages 261--280, 1997.]] Google ScholarDigital Library
- M. Lenzerini. Data Integration: A Theoretical Perspective. In PODS, pages 233--246, 2002.]] Google ScholarDigital Library
- A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering Queries Using Views. In PODS, pages 95--104, 1995.]] Google ScholarDigital Library
- A. Y. Levy, A. Rajamaran, and J. J. Ordille. Querying Heterogeneous Information Sources Using Source Descriptions. In VLDB, pages 251--262, 1996.]] Google ScholarDigital Library
- D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing Implications of Data Dependencies. ACM TODS, 4(4):455--469, 1979.]] Google ScholarDigital Library
- L. Popa. Object/Relational Query Optimization with Chase and Backchase. PhD thesis, Dept. of Computer and Information Sciences, University of Pennsylvania, 2000.]] Google ScholarDigital Library
- L. Popa, A. Deutsch, A. Sahuguet, and V. Tannen. A Chase Too Far? In SIGMOD, pages 273--284, 2000.]] Google ScholarDigital Library
- L. Popa and V. Tannen. An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. In ICDT, pages 39--57, 1999.]] Google ScholarDigital Library
- L. Popa, Y. Velegrakis, R. J. Miller, M. A. Hernandez, and R. Fagin. Translating Web Data. In VLDB, pages 598--609, 2002.]]Google ScholarDigital Library
- J. Shanmugasundaram, J. Kiernan, E. Shekita, C. Fan, and J. Funderburk. Querying XML Views of Relational Data. In VLDB, pages 261--270, 2001.]] Google ScholarDigital Library
- O. Tsatalos, M. Solomon, and Y. Ioannidis. The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal, 5(2):101--118, 1996.]] Google ScholarDigital Library
Index Terms
- Query reformulation with constraints
Recommendations
Examining collaborative query reformulation: a case of travel information searching
SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrievalUsers often reformulate or modify their queries when they engage in searching information particularly when the search task is complex and exploratory. This paper investigates query reformulation behavior in collaborative tourism information searching ...
Comments