Query languages for bags

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Query languages for bags: expressive power and complexity

Full text

Pdf (557 KB)

Source

ACM SIGACT News archive
Volume 27 , Issue 2 (June 1996) table of contents

Pages: 30 - 44

Year of Publication: 1996

ISSN:0163-5700

Authors

Stéphane Grumbach	INRIA
Leonid Libkin	Bell Labs
Tova Milo	Tel Aviv Univ., Tel Aviv, Israel
Limsoon Wong	ISS, Singapore

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 16, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/235767.235770 What is a DOI?

REFERENCES

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	S. Abiteboul , P. C. Fischer , H. -J. Schek, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
	3	Serge Abiteboul , Gerd G. Hillebrand, Space Usage in Functional Query Languages, Proceedings of the 5th International Conference on Database Theory, p.439-454, January 11-13, 1995
	4	[AHV94] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1994.
	5	Joseph Albert, Algebraic Properties of Bag Data Types, Proceedings of the 17th International Conference on Very Large Data Bases, p.211-219, September 03-06, 1991
	6	Serge Abiteboul , Victor Vianu, Generic Computation and its complexity, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.209-219, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103444]
	7	Val Breazu-Tannen , Peter Buneman , Shamim Naqvi, Structural recursion as a query language, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.9-19, April 1992, Nafplion, Greece
	8	Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France
	9	Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
	10	Val Tannen , Peter Buneman , Limsoon Wong, Naturally Embedded Query Languages, Proceedings of the 4th International Conference on Database Theory, p.140-154, October 14-16, 1992
	11	Luca Cardelli, Types for Data-Oriented Languages, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.1-15, March 14-18, 1988
	12	[FGT93] G. Fayolle, S. Grumbach, and C. Tollu. Asymptotic probabilities of languages with generalized quantifiers. In Proc. IEEE Symp. on Logic in Computer Science, pages 199-207, June 1993.
	13	[Fis87] D.H. Fishman. et al. Iris: An object oriented database management system. In ACM Trans. Office Information Systems, 5:1, 1987.
	14	[FSS84] M. Furst, J.B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical System Theory, 17:13-27, 1984.
	15	Stéphane Grumbach , Tova Milo, Towards tractable algebras for bags, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.49-58, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153855]
	16	Stéphane Grumbach , Tova Milo , Yoram Kornatzky, Calculi for Bags and their Complexity, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.65-79, August 30-September 01, 1993
	17	Erich Grädel , Martin Otto, Inductive Definability with Counting on Finite Structures, Selected Papers from the Workshop on Computer Science Logic, p.231-247, September 28-October 02, 1992
	18	Stéphane Grumbach , Christophe Tollu, On the expressive power of counting, Theoretical Computer Science, v.149 n.1, p.67-99, Sept. 18, 1995
	19	Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
	20	[IL90] N. Immerman and E. Lander. Describing Graphs: A First-Order Approach to Graph Canonization, in Complexity Theory Retrospective, pages 59-81. Springer Verlag, 1990.
	21	Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
	22	[KV92] Ph. Kolaitis and M.Y. Vardi. Fixpoint logic vs. infinitary logic in finite model theory. In Proc. 7th Symp. on Logic in Computer Science, pages 46-57, 1992.
	23	Leonid Libkin, Normalizing incomplete databases, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.219-230, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220217]
	24	Leonid Libkin , Limsoon Wong, Aggregate Functions, Conservative Extensions, and Linear Orders, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.282-294, August 30-September 01, 1993
	25	Leonid Libkin , Limsoon Wong, Some Properties of Query Languages for Bags, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.97-114, August 30-September 01, 1993
	26	Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182609]
	27	Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
	28	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]
	29	Dan Suciu , Jan Paredaens, Any algorithm in the complex object algebra with powerset needs exponential space to compute transitive closure, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.201-209, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182613]
	30	Dan Suciu , Val Breazu-Tannen, A query language for NC, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.167-178, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182610]
	31	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]

CITED BY 4

	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
	David Gross-Amblard, Query-preserving watermarking of relational databases and XML documents, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.191-201, June 09-11, 2003, San Diego, California
	Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1215-1256, December 2006