On the Complexity of Queries in the Logical Data Model (Extended Abstract).

@inproceedings{DBLP:conf/icdt/KuperV88,
  author    = {Gabriel M. Kuper and
               Moshe Y. Vardi},
  editor    = {Marc Gyssens and
               Jan Paredaens and
               Dirk Van Gucht},
  title     = {On the Complexity of Queries in the Logical Data Model (Extended
               Abstract)},
  booktitle = {ICDT'88, 2nd International Conference on Database Theory, Bruges,
               Belgium, August 31 - September 2, 1988, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {326},
  year      = {1988},
  isbn      = {3-540-50171-1},
  pages     = {267-280},
  ee        = {db/conf/icdt/KuperV88.html},
  crossref  = {DBLP:conf/icdt/88},
  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-2 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

Journal Version

References

[AH87]

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

[Be62]

...

[BK86]

François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CKS81]

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133(1981) BibTeX

[Co70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Co79]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[FT83]

...

[HM81]

Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX

[HS88]

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

[HU79]

John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX

[HY82]

Richard Hull, Chee-Keng Yap: The Format Model: A Theory of Database Organization. PODS 1982: 205-211 BibTeX

[Ja82]

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

[JS82]

Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX

[Ku85]

...

[KV84]

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

[KV85]

Gabriel M. Kuper, Moshe Y. Vardi: On the Expressive Power of the Logical Data Model (Preliminary Report). SIGMOD Conference 1985: 180-187 BibTeX

[Sh81]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

[SS77]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) BibTeX

[St74]

...

[St76]

Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX

[Va82]

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

[Vo83]

Hugo Volger: Turing Machines with Linear Alternation, Theories of Bounded Concatenation and the Decision Problem of First Order Theories. Theor. Comput. Sci. 23: 333-337(1983) BibTeX

Referenced by

1. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
2. Karl Denninghoff, Victor Vianu: Database Method Schemas and Object Creation. PODS 1993: 265-275
3. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
4. Kumar V. Vadaparty: On the Power of Rule-Based Languages with Sets. PODS 1991: 26-36
5. Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327
6. Stéphane Grumbach, Victor Vianu: Expressiveness and Complexity of Restricted Languages for Complex Objects. DBPL 1991: 111-122
7. Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38
8. Catriel Beeri, Yoram Kornatzky: The Many Faces of Query Monotonicity. EDBT 1990: 120-135
9. Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158
10. Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359
11. Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410