Extended Algebra and Calculus for Nested Relational Databases.

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)
  author    = {Mark A. Roth and
               Henry F. Korth and
               Abraham Silberschatz},
  title     = {Extended Algebra and Calculus for Nested Relational Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {4},
  year      = {1988},
  pages     = {389-417},
  ee        = {, db/journals/tods/RothKS88.html},
  bibsource = {DBLP,}


Relaxing the assumption that relations are always in First-Normal-Form (1NF) necessitates a reexamination of the fundamentals of relational database theory. In this paper we take a first step towards unifying the various theories of ¬1NF databases. We start by determining an appropriate model to couch our formalisms in. We then define an extended relational calculus as the theoretical basis for our ¬1NF database query language. We define a minimal extended relational algebra and prove its equivalence to the ¬1NF relational calculus. We define a class of ¬1NF relations with certain "good" properties and extend our algebra operators to work within this domain. We prove certain desirable equivalences that hold only if we restrict our language to this domain.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Abdullah Uz Tansel, Lucy Garnett: On Roth, Korth, and Silberschatz's Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 17(2): 374-383(1992) BibTeX


Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200 BibTeX
Hiroshi Arisawa, Kunihiko Moriya, Takao Miura: Operations and the Properties on Non-First-Normal-Form Relational Databases. VLDB 1983: 197-204 BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
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
Patrick C. Fischer, Lawrence V. Saxton, Stan J. Thomas, Dirk Van Gucht: Interactions between Dependencies and Nested Relational Structures. J. Comput. Syst. Sci. 31(3): 343-354(1985) BibTeX
Patrick C. Fischer, Dirk Van Gucht: Weak Multivalued Dependencies. PODS 1984: 266-274 BibTeX
Patrick C. Fischer, Dirk Van Gucht: Structure of Relations Satisfying Certain Families of Dependencies. STACS 1985: 131-142 BibTeX
Antonio L. Furtado: Horizontal Decomposition to Improve a Non-BCNF Scheme. SIGMOD Record 12(1): 26-32(1981) BibTeX
Antonio L. Furtado, Larry Kerschberg: An Algebra of Quotient Relations. SIGMOD Conference 1977: 1-8 BibTeX
Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984) BibTeX
Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX
Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987) BibTeX
Mark A. Roth, Henry F. Korth: The Design of ¬1NF Relational Databases into Nested Normal Form. SIGMOD Conference 1987: 143-159 BibTeX
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
Hans-Jörg Schek: Towards A Basic Relational NF² Algebra Processor. FODO 1985: 549-562 BibTeX
Hans-Jörg Schek, Peter Pistor: Data Structures for an Integrated Data Base Management and Information Retrieval System. VLDB 1982: 197-207 BibTeX
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977) BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

Referenced by

  1. Mengchi Liu: Partial and Complete Tuples and Sets in Deductive Databases. ADBIS (Short Papers) 1999: 200-206
  2. Sridhar Ramaswamy, Sameer Mahajan, Abraham Silberschatz: On the Discovery of Interesting Patterns in Association Rules. VLDB 1998: 368-379
  3. Giansalvatore Mecca, Alberto O. Mendelzon, Paolo Merialdo: Efficient Queries over Web Views. EDBT 1998: 72-86
  4. Zahir Tari, John Stokes, Stefano Spaccapietra: Object Normal Forms and Dependency Constraints for Object-Oriented Schemata. ACM Trans. Database Syst. 22(4): 513-569(1997)
  5. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
  6. Paolo Atzeni, Giansalvatore Mecca, Paolo Merialdo: To Weave the Web. VLDB 1997: 206-215
  7. Debabrata Dey, Terence M. Barron, Veda C. Storey: A Complete Temporal Relational Algebra. VLDB J. 5(3): 167-180(1996)
  8. Wai Yin Mok, Yiu-Kai Ng, David W. Embley: A Normal Form for Precisely Characterizing Redundancy in Nested Relations. ACM Trans. Database Syst. 21(1): 77-106(1996)
  9. Wai Yin Mok, David W. Embley: Transforming Conceptual Models to Object-Oriented Database Designs: Practicalities, Properties, and Peculiarities. ER 1996: 309-324
  10. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
  11. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  12. Ron Sacks-Davis, Alan J. Kent, Kotagiri Ramamohanarao, James A. Thom, Justin Zobel: Atlas: A Nested Relational Database System for Text Applications. IEEE Trans. Knowl. Data Eng. 7(3): 454-470(1995)
  13. Stéphane Grumbach, Jianwen Su: Dense-Order Constraint Databases. PODS 1995: 66-77
  14. Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260
  15. Byung Suk Lee, Gio Wiederhold: Efficiently Instantiating View-Objects From Remote Relational Databases. VLDB J. 3(3): 289-323(1994)
  16. James Clifford, Albert Croker, Alexander Tuzhilin: On Completeness of Historical Relational Query Languages. ACM Trans. Database Syst. 19(1): 64-116(1994)
  17. Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By: From Nested-Loop to Join Queries in OODB. VLDB 1994: 618-629
  18. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  19. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  20. Hiroshi Ishikawa, Fumio Suzuki, Fumihiko Kozakura, Akifumi Makinouchi, Mika Miyagishima, Yoshio Izumida, Masaaki Aoshima, Yasuo Yamane: The Model, Language, and Implementation of an Object-Oriented Multimedia Knowledge Base Management System. ACM Trans. Database Syst. 18(1): 1-50(1993)
  21. Gultekin Özsoyoglu, Aladdin Hafez: Near-Optimum Storage Models for Nested Relations Based on Workload Information. IEEE Trans. Knowl. Data Eng. 5(6): 1018-1038(1993)
  22. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  23. Hiroshi Ishikawa, Kazumi Kubota: An Active Object-Oriented Database: A Multi-Paradigm Approach to Constraint Management. VLDB 1993: 467-478
  24. Reda Alhajj, M. Erol Arkun: A Query Model for Object-Oriented Databases. ICDE 1993: 163-172
  25. Abdullah Uz Tansel, Lucy Garnett: On Roth, Korth, and Silberschatz's Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 17(2): 374-383(1992)
  26. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
  27. Elisa Bertino, Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Object-Oriented Query Languages: The Notion and the Issues. IEEE Trans. Knowl. Data Eng. 4(3): 223-237(1992)
  28. Jiawei Han, Yandong Cai, Nick Cercone: Knowledge Discovery in Databases: An Attribute-Oriented Approach. VLDB 1992: 547-559
  29. Isabel F. Cruz: DOODLE: A Visual Language for Object-Oriented Databases. SIGMOD Conference 1992: 71-80
  30. M. Sh. Tsalenko: Database Theory in Russia (1979-1991) (an overview). ICDT 1992: 51-70
  31. Z. Meral Özsoyoglu, Jian Wang: A Keying Method for a Nested Relational Database Management System. ICDE 1992: 438-446
  32. Justin Zobel, James A. Thom, Ron Sacks-Davis: Efficiency of Nested Relational Document Database Systems. VLDB 1991: 91-102
  33. Thierry Barsalou, Arthur M. Keller, Niki Siambela, Gio Wiederhold: Updating Relational Databases through Object-Based Views. SIGMOD Conference 1991: 248-257
  34. Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327
  35. Ye. P. Yemelchenkov, M. Sh. Tsalenko: Functional Dependencies in Hierarchical Structures of Data. MFDBS 1991: 258-275
  36. Peter Sander: Specifying Operations for Nested Relations by Rules and Partial Orders. MFDBS 1991: 44-58
  37. Gunter Saake, Ralf Jungclaus, Cristina Sernadas: Abstract Data Type Semantics for Many-Sorted Object Query Algebras. MFDBS 1991: 291-307
  38. Jan Van den Bussche: Complex Object Multi-Level Fixpoint Queries. MFDBS 1991: 1-13
  39. Leonid Libkin: A Relational Algebra for Complex Objects Based on Partial Information. MFDBS 1991: 29-43
  40. Mizuho Iwaihara, Tetsuya Furukawa, Yahiko Kambayashi: Navigation and Schema Transformations for Producing Nested Relations form Networks. ICDE 1991: 181-190
  41. Norbert Südkamp, Volker Linnemann: Elimination of View and Redundant Variables in a SQL-like Database Language for Extended NF2 Structures. VLDB 1990: 302-313
  42. Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
  43. Guy Hulin: On Restructuring Nested Relations in Partitioned Normal Form. VLDB 1990: 626-637
  44. Masaaki Aoshima, Yoshio Izumida, Akifumi Makinouchi, Fumio Suzuki, Yasuo Yamane: The C-based Database Programming Language Jasmine/C. VLDB 1990: 539-551
  45. Andreas Heuer, Jürgen Fuchs, U. Wiebking: OSCAR: An Object-Oriented Database System with a Nested Relational Kernel. ER 1990: 95-110
  46. Abdullah Uz Tansel, Lucy Garnett: Nested Historical Relations. SIGMOD Conference 1989: 284-294
  47. Michael Kifer, James Wu: A Logic for Object-Oriented Logic Programming (Maier's O-Logic Revisited). PODS 1989: 379-393
  48. Christine Parent, Hélène Rolin, Kokou Yétongnon, Stefano Spaccapietra: An ER Calculus for the Entity-Relationship Complex Model. ER 1989: 361-384
  49. Uwe Hohenstein: Automatic Transformation of an Entity-Relationship Query Language into SQL. ER 1989: 303-321
  50. Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410
  51. Peter Buneman, Susan B. Davidson, Aaron Watters: A Semantics for Complex Objects and Approximate Queries. PODS 1988: 305-314
  52. Atsushi Ohori: Semantics of Types for Database Objects. ICDT 1988: 239-251
  53. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
  54. Stefano Ceri, Stefano Crespi-Reghizzi, Georg Gottlob, F. Lamperti, Luigi Lavazza, Letizia Tanca, Roberto Zicari: The Algres Project. EDBT 1988: 551-555
  55. Marc H. Scholl, H.-Bernhard Paul, Hans-Jörg Schek: Supporting Flat Relations by a Nested Relational Kernel. VLDB 1987: 137-146
  56. Atsushi Ohori: Orderings and Types in Databases. DBPL 1987: 97-116
  57. Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:05 2008