On the Expressive Power of Database Queries with Intermediate Types.

@inproceedings{DBLP:conf/pods/HullS88,
  author    = {Richard Hull and
               Jianwen Su},
  title     = {On the Expressive Power of Database Queries with Intermediate
               Types},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {39-51},
  ee        = {http://doi.acm.org/10.1145/308386.308409, db/conf/pods/HullS88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The set-height of a complex object type is defined to be its level of nesting of the set construct. In a query of the complex object calculus which maps a database D to an output type T, an intermediate type is a type which is used by some variable of the query, but whch is not present in D or T. For each k, i >= 0 we define CALC_k,i to be the family of calculus queries mapping from and to types with set-height <= k and using intermediate types with set-heigth <= i. In particular, CALC_0,0 is the relational calculus, and CALC_0,1 is equivalent to the family of second-order (relational) queries.

Several results concerning these families of languages are obtained. A primary focus is on the families CALC_0,i, wich map relations to relations. Upper bounds on the complexity of these families are provided, and it is shown that CALC_0,3 has at least the complexity of exponential space. The CALC_o,i hierarchy does not collapse, because for each i, CALC_0,i is strictly less expressive than CALC_0,i+2. The union U_0<=iCALC_0,i is strictly less expressive than the family of 'computable' database queries.

The expressive power of queries from the complex Object calculus interpreted using a semantics based on the use of arbitrarily large finite numbers of invented values is studied. Under this semantics, the expressive power of the relational calculus is not increased, and the CALC_0,i hierarchy collapses at CALC_0,1. We also consider queries which use a bounded number of invented values.

Copyright © 1988 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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Version

References

[AB87]

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

[ABW86]

...

[AG87]

Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. DBPL 1987: 347-374 BibTeX

[AH87]

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

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[AV]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX

[AV87]

Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268 BibTeX

[Ben62]

...

[BK86]

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

[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

[CH82a]

Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX

[CH82b]

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

[FT83]

...

[HK87]

Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX

[HM81]

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

[Hul86]

Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. SIAM J. Comput. 15(3): 856-886(1986) BibTeX

[Hul87]

...

[Jac82]

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

[Kup87]

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

[KV]

...

[KV84]

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

[Mai83]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[MY79]

...

[PvG]

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

[RKS85]

...

[Shi81]

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

[Ull82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Var82]

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

[vG86]

...

Referenced by

1. Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207
2. Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58
3. Karl Denninghoff, Victor Vianu: Database Method Schemas and Object Creation. PODS 1993: 265-275
4. Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281
5. Stéphane Grumbach, Tova Milo, Yoram Kornatzky: Calculi for Bags and their Complexity. DBPL 1993: 65-79
6. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
7. Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52
8. Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327
9. Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19
10. Stéphane Grumbach, Victor Vianu: Expressiveness and Complexity of Restricted Languages for Complex Objects. DBPL 1991: 111-122
11. Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38
12. Catriel Beeri, Yoram Kornatzky: The Many Faces of Query Monotonicity. EDBT 1990: 120-135
13. Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158
14. Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359
15. Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410
16. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
17. 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
18. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
19. Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280
20. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40