Expressiveness and Complexity of Restricted Languages for Complex Objects.

@inproceedings{DBLP:conf/dbpl/GrumbachV91,
  author    = {St{\'e}phane Grumbach and
               Victor Vianu},
  editor    = {Paris C. Kanellakis and
               Joachim W. Schmidt},
  title     = {Expressiveness and Complexity of Restricted Languages for Complex
               Objects},
  booktitle = {Database Programming Languages: Bulk Types and Persistent Data.
               3rd International Workshop, August 27-30, 1991, Nafplion, Greece,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-242-9},
  pages     = {111-122},
  ee        = {db/conf/dbpl/GrumbachV91.html},
  crossref  = {DBLP:conf/dbpl/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-5 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

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)

[AB87]

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

[AG88]

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

[AH87]

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

[AK89]

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

[AV88]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991)

[AV89]

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

[ABW88]

Krzysztof R. Apt, Howard A. Blair, Adrian Walker: Towards a Theory of Declarative Knowledge. Foundations of Deductive Databases and Logic Programming. 1988: 89-148

[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

[CH85]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985)

[Ch88]

Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9

[CH80]

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

[FT83]

...

[GV90]

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

[GV91]

Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327

[GS85]

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

[GG88]

Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232

[HS88]

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

[HS89]

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

[Imm86]

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

[Jac82]

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

[K87]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991)

[KP88]

Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239

[KRS85]

...

[Kup87]

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

[Kup88]

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

[KV84]

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

[KV88]

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

[PvG88]

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

[SS86]

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

[Var82]

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

[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