ACM SIGMOD Anthology TODS dblp.uni-trier.de

Converting Nested Algebra Expressions into Flat Algebra Expressions.

Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
@article{DBLP:journals/tods/ParedaensG92,
  author    = {Jan Paredaens and
               Dirk Van Gucht},
  title     = {Converting Nested Algebra Expressions into Flat Algebra Expressions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {17},
  number    = {1},
  year      = {1992},
  pages     = {65-93},
  ee        = {http://doi.acm.org/10.1145/128765.128768, db/journals/tods/ParedaensG92.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Nested relations generalize ordinary flat relations by allowing tuple values to be either atomic or set valued. The nested algebra is a generalization of the flat relational algebra to manipulate nested relations. In this paper we study the expressive power of the nested algebra relative to its operation on flat relational databases. We show that the flat relational algebra is rich enough to extract the same "flat information" from a flat database as the nested algebra does. Theoretically, this result implies that recursive queries such as the transitive closure of a binary relation cannot be expressed in the nested algebra. Practically, this result is relevant to (flat) relational query optimization.

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


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 1491 KB]

Conference Version

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

References

[1]
...
[2]
Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX
[3]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[4]
Hiroshi Arisawa, Kunihiko Moriya, Takao Miura: Operations and the Properties on Non-First-Normal-Form Relational Databases. VLDB 1983: 197-204 BibTeX
[5]
François Bancilhon: A Logic-Programming/Object-Oriented Cocktail. SIGMOD Record 15(3): 11-21(1986) BibTeX
[6]
François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX
[7]
François Bancilhon, Philippe Richard, Michel Scholl: On Line Processing of Compacted Relations. VLDB 1982: 263-269 BibTeX
[8]
Catriel Beeri, Yoram Kornatzky: The Many Faces of Query Monotonicity. EDBT 1990: 120-135 BibTeX
[9]
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
[10]
Nicole Bidoit: The Verso Algebra or How to Answer Queries with Fewer Joins. J. Comput. Syst. Sci. 35(3): 321-364(1987) BibTeX
[11]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[12]
Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX
[13]
Peter Dadam: Advanved Information Management (AIM): Research in Extended Nested Relations. IEEE Data Eng. Bull. 11(3): 4-14(1988) BibTeX
[14]
Peter Dadam, Klaus Küspert, F. Andersen, Henk M. Blanken, R. Erbe, Jürgen Günauer, Vincent Y. Lum, Peter Pistor, Georg Walch: A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies. SIGMOD Conference 1986: 356-367 BibTeX
[15]
Uwe Deppisch, H.-Bernhard Paul, Hans-Jörg Schek: A Storage System for Complex Objects. OODBS 1986: 183-195 BibTeX
[16]
Anand Deshpande, Dirk Van Gucht: A Storage Structure for Unnormalized Relational Databases. BTW 1987: 481-486 BibTeX
[17]
Anand Deshpande, Dirk Van Gucht: An Implementation for Nested Relational Databases. VLDB 1988: 76-87 BibTeX
[18]
...
[19]
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 BibTeX
[20]
Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Natural Tool to Handle Nested Database Relations. J. Comput. Syst. Sci. 45(1): 76-103(1992) BibTeX
[21]
Marc Gyssens, Jan Paredaens, Dirk Van Gucht: A uniform approach toward handling atomic and structured information in the nested relational database model. J. ACM 36(4): 790-825(1989) BibTeX
[22]
...
[23]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX
[24]
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
[25]
Gabriel M. Kuper: Logic Programming with Sets. J. Comput. Syst. Sci. 41(1): 44-64(1990) BibTeX
[26]
Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280 BibTeX
[27]
Per-Åke Larson: The Data Model and Query Language of LauRel. IEEE Data Eng. Bull. 11(3): 23-30(1988) BibTeX
[28]
Volker Linnemann: Non First Normal Form Relations and Recursive Queries: An SQL-Based Approach. ICDE 1987: 591-598 BibTeX
[29]
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
[30]
Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
[31]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX
[32]
...
[33]
H.-Bernhard Paul, Hans-Jörg Schek, Marc H. Scholl, Gerhard Weikum, Uwe Deppisch: Architecture and Implementation of the Darmstadt Database Kernel System. SIGMOD Conference 1987: 196-207 BibTeX
[34]
Peter Pistor, F. Andersen: Designing A Generalized NF2 Model with an SQL-Type Language Interface. VLDB 1986: 278-285 BibTeX
[35]
Peter Pistor, Roland Traunmüller: A database language for sets, lists and tables. Inf. Syst. 11(4): 323-336(1986) BibTeX
[36]
Mark A. Roth, Henry F. Korth, Don S. Batory: SQL/NF: a query language for ¬1 NF relational databases. Inf. Syst. 12(1): 99-114(1987) BibTeX
[37]
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
[38]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[39]
Hans-Jörg Schek, H.-Bernhard Paul, Marc H. Scholl, Gerhard Weikum: The DASDBS Project: Objectives, Experiences, and Future Prospects. IEEE Trans. Knowl. Data Eng. 2(1): 25-43(1990) BibTeX
[40]
Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX
[41]
Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146 BibTeX
[42]
Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX
[43]
Stan J. Thomas, Patrick C. Fischer: Nested Relational Structures. Advances in Computing Research 3: 269-307(1986) BibTeX
[44]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

  1. Frank Neven, Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Typed Query Languages for Databases Containing Queries. PODS 1998: 189-196
  2. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  3. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
  4. Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238
  5. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  6. Marc Gyssens, Dan Suciu, Dirk Van Gucht: The Restricted and Bounded Fixpoint Closures of the Nested Relational Algebra are Equivalent. DBPL 1995: 5
  7. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  8. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
  9. Dan Suciu, Jan Paredaens: Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure. PODS 1994: 201-209
  10. Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
  11. Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36
  12. Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281
  13. Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294
  14. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:12 2008