Deciding containment for queries with complex objects (extended abstract)

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Catriel Beeri, The power of languages for the manipulation of complex values, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.4, p.727-794, October 1995 [doi>10.1007/BF01354881]
	2	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	3	Alfred Aho, Yehoshua Sagiv, and Jeffrey D. Ullman. Equivalence of relational expre&sions. SIAM Journal of Computing, (8)2:218-246, 1979.
	4	N. Bidoit, The Verso algebra or how to answer queries with fewer joins, Journal of Computer and System Sciences, v.35 n.3, p.321-364, Dec. 1987 [doi>10.1016/0022-0000(87)90019-5]
	5	Peter Btmeman, Susan Davidson, Mary Fernandez, and Dan Suciu. Adding structure to unstructured data. In 1CDT, 1997.
	6	Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
	7	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
	8	Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
	9	R. G. G. Cattell , Douglas K. Barry , Dirk Bartels , Mark Berler , Jeff Eastman , Sophie Gamerman , David Jordan , Adam Springer , Henry Strickland , Drew Wade, The object database standard: ODMG 2.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
	10	Edward P. F. Chan, Containment and minimization of positive conjunctive queries in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.202-211, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137869]
	11	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]
	12	Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
	13	Surajit Chaudhuri , Kyuseok Shim, Including Group-By in Query Optimization, Proceedings of the 20th International Conference on Very Large Data Bases, p.354-366, September 12-15, 1994
	14	Surajit Chaudhuri , Moshe Y. Vardi, On the equivalence of recursive and nonrecursive datalog programs, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.55-66, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137109]
	15	Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
	16	Latha S. Colby, Query languages and a unifying framework for non-traditional data models, Indiana University, Bloomington, IN, 1993
	17	Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
	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.
	19	D. Dreben and W. D. Goldfarb. The Decision Problem: Solvable Classes of Quantificational Formulas. AddLson-Wesley, 1979.
	20	Heinz-Dieter Ebbinghaus and JSrg Flum. Finite Model Theory. Springer, 1995.
	21	Dirk van Gucht , Patrick C. Fischer, Multilevel nested relational structures, Journal of Computer and System Sciences, v.36 n.1, p.77-105, February 1988 [doi>10.1016/0022-0000(88)90021-9]
	22	C. A. Gunter , D. S. Scott, Semantic domains, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	23	Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182597]
	24	Marc Gyssens , Jan Paredaens , Dirk Van Gucht, On a hierarchy of classes for nested databases, Information Processing Letters, v.36 n.5, p.259-266, Dec. 1, 1990 [doi>10.1016/0020-0190(90)90152-N]
	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.
	26	Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
	27	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]
	28	Alon Y. Levy , Inderpal Singh Mumick, Reasoning with Aggregation Constraints, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.514-534, March 25-29, 1996
	29	Alon Y. Levy , Inderpal Singh Mumick , Yehoshua Sagiv, Query Optimization by Predicate Move-Around, Proceedings of the 20th International Conference on Very Large Data Bases, p.96-107, September 12-15, 1994
	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.
	31	Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
	32	Leonid Libkin , Limsoon Wong, Semantic representations and query languages for or-sets, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-48, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153854]
	33	G. Özsoyoğlu , Z. M. Özsoyoğlu , V. Matos, Extending relational algebra and relational calculus with set-valued attributes and aggregate functions, ACM Transactions on Database Systems (TODS), v.12 n.4, p.566-592, Dec. 1987 [doi>10.1145/32204.32219]
	34	Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
	35	Kenneth A. Ross , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Foundations of Aggregation Constraints, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.193-204, May 02-04, 1994
	36	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	37	Y. Sagiv, Optimizing datalog programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	38	Oded Shmueli, Equivalence of datalog queries is undecidable, Journal of Logic Programming, v.15 n.3, p.231-241, Feb. 1993 [doi>10.1016/0743-1066(93)90040-N]
	39	Dan Suciu, Bounded Fixpoints for Complex Objects, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.263-281, August 30-September 01, 1993
	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.
	41	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	42	R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
	43	Limsoon Wong, Normal forms and conservative properties for query languages over collection types, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.26-36, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153853]
	44	X. Zhang and M. Z. Ozsoyoglu. On efficient reasoning with implication cov~straints, in Proeee~lings of DOOD, 1993.