Extended Algebra and Calculus for Nested Relational Databases.

@article{DBLP:journals/tods/RothKS88,
  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        = {http://doi.acm.org/10.1145/49346.49347, db/journals/tods/RothKS88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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

• 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/An3-1 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/aDVD2 or /dvd

Discussion

References

[1]

Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations to Represent Hierarchical Organized Data. PODS 1984: 191-200 BibTeX

[2]

Hiroshi Arisawa, Kunihiko Moriya, Takao Miura: Operations and the Properties on Non-First-Normal-Form Relational Databases. VLDB 1983: 197-204 BibTeX

[3]

...

[4]

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

[5]

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

[6]

...

[7]

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

[8]

...

[9]

Patrick C. Fischer, Dirk Van Gucht: Weak Multivalued Dependencies. PODS 1984: 266-274 BibTeX

[10]

Patrick C. Fischer, Dirk Van Gucht: Structure of Relations Satisfying Certain Families of Dependencies. STACS 1985: 131-142 BibTeX

[11]

Antonio L. Furtado: Horizontal Decomposition to Improve a Non-BCNF Scheme. SIGMOD Record 12(1): 26-32(1981) BibTeX

[12]

Antonio L. Furtado, Larry Kerschberg: An Algebra of Quotient Relations. SIGMOD Conference 1977: 1-8 BibTeX

[13]

Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984) BibTeX

[14]

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

[15]

...

[16]

...

[17]

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

[18]

...

[19]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX

[20]

...

[21]

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

[22]

Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX

[23]

...

[24]

...

[25]

Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987) BibTeX

[26]

...

[27]

Mark A. Roth, Henry F. Korth: The Design of ¬1NF Relational Databases into Nested Normal Form. SIGMOD Conference 1987: 143-159 BibTeX

[28]

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

[29]

...

[30]

Hans-Jörg Schek: Towards A Basic Relational NF² Algebra Processor. FODO 1985: 549-562 BibTeX

[31]

Hans-Jörg Schek, Peter Pistor: Data Structures for an Integrated Data Base Management and Information Retrieval System. VLDB 1982: 197-207 BibTeX

[32]

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

[33]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977) BibTeX

[34]

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

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