- 1.Serge Abiteboul and Catriel Beeri. On the power of languages for the manipulation of complex objects. VLDB Journal, October 1995. Google ScholarDigital Library
- 2.Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases. Addison W~sley Publishhag Co, 1995. Google ScholarDigital Library
- 3.Alfred Aho, Yehoshua Sagiv, and Jeffrey D. Ullman. Equivalence of relational expre&sions. SIAM Journal of Computing, (8)2:218-246, 1979.Google ScholarDigital Library
- 4.N. Bidoit. The Verso algebra or How to ansower queries with fewer joins. Journal of Computer and System Sciences, 35(3):321-364, 1987. Google ScholarDigital Library
- 5.Peter Btmeman, Susan Davidson, Mary Fernandez, and Dan Suciu. Adding structure to unstructured data. In 1CDT, 1997.Google Scholar
- 6.Peter Buneman, Susan Davidson, Gerd Hillebrand, and Dan Suciu. A query language and optimization techniques for unstructured data. In SIGMOD, 1996. Google ScholarDigital Library
- 7.Peter Buneman, Shamim Naqvi, Val Tannen, and Limsoon Wong. Principles of proramming with collection types. Theordic~l Computer Science., 1995. Google ScholarDigital Library
- 8.Peter Buneman, Atst~shi Ohori, and Achim June. Using powerdomains to generalize relational databases. Theoretical Computer Science, 91:23- 55, 1991. Google ScholarDigital Library
- 9.R. G. G. Cattell, editor. The Obja:t Database Standard: ODMG-93. Morgan Kanfmann, San Marco, California, 1994. Google ScholarDigital Library
- 10.Edward P. Chan. Containment and minimization of positive conjunctive queries in oodb's. In ACM PODS, 1992. Google ScholarDigital Library
- 11.A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the Ninth Annual A CM Symposium on Theory of Computing, 1977. Google ScholarDigital Library
- 12.Surajit Chaudhuri, Ravi Kr~shnamurthy, Spyros Potamianos, and Kyuseok Shim. Optimizing queries with materialized views. In Proceedings of ICDE, 1995. Google ScholarDigital Library
- 13.Surajit Chandhuri and Kyuseok Shim. Including group-by in query optimization. In Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994. Google ScholarDigital Library
- 14.Surajit Chandhuri and Moshe Vardi. On the equivalence of recursive and nonrecursive datalog programs. In ACM PODS, 1992. Google ScholarDigital Library
- 15.Surajit Chaudhuri and Moshe Vardi. Optimizing real conjunctive queries. In ACM PODS, 1993. Google ScholarDigital Library
- 16.La~ha S. Colby. Query Languages and a Unify. ing Framework for Non-traditional Data Models. Phi:) thesis, Computer Science Department, Indiana University, Bloomington, indiana 47405-4101, May 1993. Available as Indiana University Computer Science Technical Report 38I. Google ScholarDigital Library
- 17.Umesh Dayal. Of nests and tree~s: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In Proceedings of VLDB-87, pages pages 197-208, 1987. Google ScholarDigital Library
- 18.Jan Van den Bussche. Complex object manipulation through identifiers: An algebraic perspective. Technical Report 92-41, University of Antwerp, Department of Mathematics and Computer Science, Universiteitsplein 1, B-2610 Antwerp, Belgium, September 1992.Google Scholar
- 19.D. Dreben and W. D. Goldfarb. The Decision Problem: Solvable Classes of Quantificational Formulas. AddLson-Wesley, 1979.Google Scholar
- 20.Heinz-Dieter Ebbinghaus and JSrg Flum. Finite Model Theory. Springer, 1995.Google ScholarCross Ref
- 21.Dirk Van Gucht and Patrick C. Fischer. Multilevel n~sted relational structures. Journal of Computer and System Sciences, 36:77-105, 1988. Google ScholarDigital Library
- 22.Carl A. Gunter and Dana S. Scott. Semantic domains. In Formal Models and Semantics, volume B of Handbook of Theoretical Computer Science, Chapter 12, pages 635--674. 1990. Google ScholarDigital Library
- 23.Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, and Jennifer Widom. Constraint checldng with parial information. In ACM PODS, 1994. Google ScholarDigital Library
- 24.Mare Gyasens, Jan Paredaens, and Dirk Van Gucht. On a hierarchy of classes for nested databases. Information Processing Letter~, 36:259- 266, 1990. Google ScholarDigital Library
- 25.Mare Gyssens, Dan Suciu, and Dirk Van Gucht. On polynomially bounded fix-point constructs for nested relations. In Proceedings of DBPL'95, Gubbio, Italy, September 1995.Google Scholar
- 26.A. Klug. On conjunctive queries containing inequalities. Journal of the A CM, pages 35(1): 146- 160, 1988. Google ScholarDigital Library
- 27.Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In ACM PODS, 1995. Google ScholarDigital Library
- 28.Alon Y. Levy and Inderpal Singh Mumick. Reasoning with aggregation constraints. In Proceedings of EDBT-96, March 1996. Google ScholarDigital Library
- 29.Alon Y. Levy, Inderpal Singh Mumick, and Yehoshua Sag-iv. Query optimization by predicate move-around. In Proceedings of the 20th VLDB Conference, Santiago, Chile. pages 96-107, 1994. Google ScholarDigital Library
- 30.Alon Y. Levy and Marie-Christine Rousset. CAR/N: a representation language integrating rules and description logics. In Proceedings of the European Conference on Artificial Intelligence, Budapest, Hungary, 1996.Google Scholar
- 31.Alon Y. Levy and Yehoshua Sagiv. Queries independent of updates, in Proceedings of the 19th VbDB Conference, Dublin, Ireland, 1993. Google ScholarDigital Library
- 32.Leonid Libkin and Limsoon Wong. Semantic representations and query languages for orsets. In Proeeedings of 12th A CM Symposium on Principles of Database Systems, Washington, D. C., 1993. Google ScholarDigital Library
- 33.G. Ozsoyoglu, Z. M. Ozsoyoglu, and V. Matos. Extending relational algebra and relational calculus with set-valued attributes and aggregate hmc- ~ions. A CM Transactions on Database Systems, 12(4):566-592, December 1987. Google ScholarDigital Library
- 34.Jan Paredaens and Dirk Van Gucht. Converting nested relational algebra expressions into fiat algebra expressions. A CM Transaction on Database Systems, 17(1):65-93, March 1992. Google ScholarDigital Library
- 35.Kenneth Ross, Divesh Srivastava, Peter Stuckey, and S. Sudarshan. FoundatiorLs of aggregation constraints. In Alan Boming, editor, Principles and Practice of Constraint Programming. Lecture Notes in Computer Science, 874. Springer Verlag, 1994. Google ScholarDigital Library
- 36.Y. Sagiv and M. Yannakakis. Equivalence among relational expre~siov.s with the union and differenee operators. Journal of the A GM, 27(4):633- 655~ 1981. Google ScholarDigital Library
- 37.Yehoshua Sagiv. Optimizing datalog programs. In Jack Minker, editor, Foundations of Deductive Databases and Logic Programming, pagea 659--698. Morgan Kaufmann, Los Altos, CA, 1988. Google ScholarDigital Library
- 38.Oded Shmueli. Equivalence of datalog querias is undecidable. Journal of Logic Prooramming, 15:231- 241~ 1993. Google ScholarDigital Library
- 39.Dan Sueiu. Fix-points and bounded fixpoint.s for complex objects. In Catriel Beeri, Atsushi Ohori, and Dennis Shasha, editors, Proc~.edings of 4th International Workshop on Database Programming Languages, New York, August 1993, Springer- Verlag, January 1994. Google ScholarDigital Library
- 40.S. J. Thomas and P. C. Fischer. Nested relational structures. In P. C. Kanellalds and F. P. Preparata, editors, Advances in Computing Re.search: The Theory of Databases, pages 269-307, London, England, 1986. JAI Press.Google Scholar
- 41.Jeffrey D. Ullman. Principles of Database and Knowledge.base Systems, Volumes I, II. Computer Science Press, Rockville MD, 1989. Google ScholarDigital Library
- 42.Ron van der Meyden. The complexity of querying indefinite data about linearly ordered domains. In ACM PODS, 1992. Google ScholarDigital Library
- 43.Limsoon Wong. Normal forms and conservative properties for query languagas over collection types. In ACM PODS, 1993. Google ScholarDigital Library
- 44.X. Zhang and M. Z. Ozsoyoglu. On efficient reasoning with implication cov~straints, in Proeee~lings of DOOD, 1993.Google Scholar
Index Terms
- Deciding containment for queries with complex objects (extended abstract)
Recommendations
Decidable containment of recursive queries
Database theoryOne of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Containment of nested XML queries
VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases - Volume 30Query containment is the most fundamental relationship between a pair of database queries: a query Q is said to be contained in a query Q′ if the answer for Q is always a subset of the answer for Q′, independent of the current state of the database. ...
Decidable Containment of Recursive Queries
ICDT '03: Proceedings of the 9th International Conference on Database TheoryOne of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment, is crucial in several contexts, such as query optimization, ...
Comments