Tractable Query Languages for Complex Object Databases.

@inproceedings{DBLP:conf/pods/GrumbachV91,
  author    = {St{\'e}phane Grumbach and
               Victor Vianu},
  title     = {Tractable Query Languages for Complex Object Databases},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {315-327},
  ee        = {http://doi.acm.org/10.1145/113413.113442, db/conf/pods/GrumbachV91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Printed Edition

Online Edition: ACM Digital Library

References

[AB86]

Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX

[AB87]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[AG88]

Serge Abiteboul, Stéphane Grumbach: A Rule-Based Language with Functions and Sets. ACM Trans. Database Syst. 16(1): 1-30(1991) BibTeX

[AH87]

Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX

[AK89]

Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX

[ASV90]

Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX

[AV89]

Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX

[AV90]

...

[Ben62]

...

[BNR*87]

Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37 BibTeX

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[FT83]

...

[GS85]

Yuri Gurevich, Saharon Shelah: Fixed-Point Extensions of First-Order Logic. FOCS 1985: 346-353 BibTeX

[GV90]

Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38 BibTeX

[HS88]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX

[HS89]

Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX

[Imm86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Jac82]

Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX

[KRS85]

Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX

[Kup87]

Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20 BibTeX

[Kup88]

Gabriel M. Kuper: On the Expressive Power of Logic Programming Languages with Sets. PODS 1988: 10-14 BibTeX

[KV84]

Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX

[KV88]

Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280 BibTeX

[PvG88]

Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX

[SS86]

Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX

[Var82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Ver86]

Michel Scholl, Serge Abiteboul, François Bancilhon, Nicole Bidoit, Sophie Gamerman, Didier Plateau, Philippe Richard, Anne Verroust: VERSO: A Database Machine Based On Nested Relations. NF² 1987: 27-49 BibTeX

Referenced by

1. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
2. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
3. Vladimir Yu. Sazonov, Alexei Lisitsa: Delta-Languages for Sets and sub-PTIME Graphs Transformers. ICDT 1995: 125-138
4. Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207
5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
6. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
7. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
8. Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
9. Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58
10. Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281
11. Stéphane Grumbach, Tova Milo, Yoram Kornatzky: Calculi for Bags and their Complexity. DBPL 1993: 65-79
12. Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190
13. Stéphane Grumbach, Victor Vianu: Expressiveness and Complexity of Restricted Languages for Complex Objects. DBPL 1991: 111-122
14. Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38