Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions.

@article{DBLP:journals/tods/OzsoyogluOM87,
  author    = {Gultekin {\"O}zsoyoglu and
               Z. Meral {\"O}zsoyoglu and
               Victor Matos},
  title     = {Extending Relational Algebra and Relational Calculus with Set-Valued
               Attributes and Aggregate Functions},
  journal   = {ACM Trans. Database Syst.},
  volume    = {12},
  number    = {4},
  year      = {1987},
  pages     = {566-592},
  ee        = {http://doi.acm.org/10.1145/32204.32219, db/journals/tods/OzsoyogluOM87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In commercial network database management systems, set-valued fields and aggregate functions are commonly supported. However, the relational database model, as defined by Codd, does not include set-valued attributes or aggregate functions. Recently, Klug extended the relational model by incorporating aggregate functions and by defining relational algebra and calculus languages.

In this paper, relational algebra and relational calculus database query languages (as defined by Klug) are extended to manipulate set-valued attributes and to utilize aggregate functions. The expressive power of the extended languages is shown to be equivalent. We extend the relational algebra with three new operators, namely, pack, unpack, and aggregation-by-template. The extended languages form a theoretical framework for statistical database query languages.

Copyright © 1987 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

References

[1]

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

[2]

...

[3]

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

[4]

...

[5]

...

[6]

...

[7]

...

[8]

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

[9]

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

[10]

...

[11]

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

[12]

Anthony C. Klug: Access Paths in the 'ABE' Statistical Query Facility. SIGMOD Conference 1982: 161-173 BibTeX

[13]

...

[14]

...

[15]

Levent V. Orman: Nested set languages for functional databases. Inf. Syst. 9(3/4): 241-249(1984) BibTeX

[16]

Gultekin Özsoyoglu, Victor Matos: On Optimizing Summary-Table-by-Example Queries. PODS 1985: 38-50 BibTeX

[17]

...

[18]

...

[19]

Z. Meral Özsoyoglu, Gultekin Özsoyoglu: Summary-Table-By-Example: A Database Query Language for Manipulating Summary Data. ICDE 1984: 193-202 BibTeX

[20]

...

[21]

Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Francisco Mata: A Language and a Physical Organization Technique for Summary Tables. SIGMOD Conference 1985: 3-16 BibTeX

[22]

Z. Meral Özsoyoglu, Li-Yan Yuan: A Normal Form for Nested Relations. PODS 1985: 251-260 BibTeX

[22a]

...

[23]

...

[24]

...

[25]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[26]

...

Referenced by

1. Stéphane Grumbach, Leonardo Tininini: On the Content of Materialized Aggregate Views. PODS 2000: 47-57
2. Panos Vassiliadis, Timos K. Sellis: A Survey of Logical Models for OLAP Databases. SIGMOD Record 28(4): 64-69(1999)
3. Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini: Querying Aggregate Data. PODS 1999: 174-184
4. Luca Cabibbo, Riccardo Torlone: A Framework for the Investigation of Aggregate Functions in Database Queries. ICDT 1999: 383-397
5. Lei Sheng, Z. Meral Özsoyoglu, Gultekin Özsoyoglu: A Graph Query Language and Its Query Processing. ICDE 1999: 572-581
6. Panos Vassiliadis: Modeling Multidimensional Databases, Cubes and Cube Operations. SSDBM 1998: 53-62
7. Frank Neven, Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Typed Query Languages for Databases Containing Queries. PODS 1998: 189-196
8. Abdullah Uz Tansel: Temporal Relational Data Model. IEEE Trans. Knowl. Data Eng. 9(3): 464-479(1997)
9. Nikos A. Lorentzos, Yannis G. Mitsopoulos: SQL Extension for Interval Data. IEEE Trans. Knowl. Data Eng. 9(3): 480-499(1997)
10. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
11. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
12. Arbee L. P. Chen, Jui-Shang Chiu, Frank Shou-Cheng Tseng: Evaluating Aggregate Operations Over Imprecise Data. IEEE Trans. Knowl. Data Eng. 8(2): 273-284(1996)
13. Giuseppe De Giacomo, Paolo Naggar: Conceptual Data Model with Structured Objects for Statistical Database. SSDBM 1996: 168-175
14. Antonia Bezenchek, Maurizio Rafanelli, Leonardo Tininini: A Data Structure for Representing Aggregate Data. SSDBM 1996: 22-31
15. Jan Chomicki, Dina Q. Goldin, Gabriel M. Kuper: Variable Independence and Aggregation Closure. PODS 1996: 40-48
16. Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533
17. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
18. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
19. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
20. Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
21. Qi Yang, Chengwen Liu, Jing Wu, Clement T. Yu, Son Dao, Hiroshi Nakajima: Efficient Processing of Nested Fuzzy SQL Queries. ICDE 1995: 131-138
22. Iqbal A. Goralwalla, Abdullah Uz Tansel, M. Tamer Özsu: Experimenting with Temporal Relational Databases. CIKM 1995: 296-303
23. 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
24. Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Kumar V. Vadaparty: A Scientific Database System for Polymers and Materials Engineering Needs. SSDBM 1994: 138-148
25. Rosine Cicchetti, Lotfi Lakhal: Matrix-Relation for Statistical Database Management. EDBT 1994: 31-44
26. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
27. Richard T. Snodgrass, Santiago Gomez, L. Edwin McKenzie: Aggregates in the Temporal Query Language TQuel. IEEE Trans. Knowl. Data Eng. 5(5): 826-842(1993)
28. Maurizio Rafanelli, Fabrizio L. Ricci: Mefisto: A Functional Model for Statistical Entities. IEEE Trans. Knowl. Data Eng. 5(4): 670-681(1993)
29. 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)
30. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
31. Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294
32. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
33. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
34. 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)
35. Z. Meral Özsoyoglu, Jian Wang: A Keying Method for a Nested Relational Database Management System. ICDE 1992: 438-446
36. Carla Basili, Roberto Basili, Leonardo Meo-Evoli: A Knowledge-Based Approach to Statistical Query Processing. EDBT 1992: 437-452
37. Soraya Abad-Mota: Approximate Query Processing with Summary Tables in Statistical Databases. EDBT 1992: 499-515
38. Martin Gogolla, Uwe Hohenstein: Towards a Semantic View of an Extended Entity-Relationship Model. ACM Trans. Database Syst. 16(3): 369-416(1991)
39. Gunter Saake, Ralf Jungclaus, Cristina Sernadas: Abstract Data Type Semantics for Many-Sorted Object Query Algebras. MFDBS 1991: 291-307
40. Francesco M. Malvestuto, Marina Moscarini: Query Evaluability in Statistical Databases. IEEE Trans. Knowl. Data Eng. 2(4): 425-430(1990)
41. Carl S. Hartzman, Carolyn R. Watters: A Relational Approach to Querying Streams. IEEE Trans. Knowl. Data Eng. 2(4): 401-409(1990)
42. Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
43. Tiziana Catarci, Giovanna D'Angiolini, Maurizio Lenzerini: Concept Description Language for Statistical Data Modeling. VLDB 1990: 722-729
44. Maurizio Rafanelli, Fabrizio L. Ricci: A Visual Interface for Browsing and Manipulating Statistical Entities. SSDBM 1990: 163-182
45. Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63
46. Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
47. Gultekin Özsoyoglu, Victor Matos, Z. Meral Özsoyoglu: Query Processing Techniques in the Summary-Table-by-Example Database Query Language. ACM Trans. Database Syst. 14(4): 526-573(1989)
48. Elke A. Rundensteiner, Lubomir Bic: Aggregates in Possibilistic Databases. VLDB 1989: 287-295
49. Francesco M. Malvestuto, Marina Moscarini: Aggregate Evaluability in Statistical Databases. VLDB 1989: 279-286
50. Abdullah Uz Tansel, Lucy Garnett: Nested Historical Relations. SIGMOD Conference 1989: 284-294
51. Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283
52. Uwe Hohenstein: Automatic Transformation of an Entity-Relationship Query Language into SQL. ER 1989: 303-321
53. Maurizio Rafanelli: Research Topics in Statistical and Scientific Database Management: the IV SSDBM. SSDBM 1988: 1-18
54. Alessandro D'Atri, Fabrizio L. Ricci: Interpretation of Statistical Queries to Relational Databases. SSDBM 1988: 246-258
55. 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
56. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
57. Uwe Hohenstein, Martin Gogolla: A Calculus for an Extended Entity-Relationship Model Incorporating Arbitrary Data Operations and Aggregate Functions. ER 1988: 129-148
58. Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987)
59. Z. Meral Özsoyoglu, Gultekin Özsoyoglu: Summary-Table-By-Example: A Database Query Language for Manipulating Summary Data. ICDE 1984: 193-202