ACM SIGMOD Anthology TKDE dblp.uni-trier.de

Association Algebra: A Mathematical Foundation for Object-Oriented Databases.

Stanley Y. W. Su, Mingsen Guo, Herman Lam: Association Algebra: A Mathematical Foundation for Object-Oriented Databases. IEEE Trans. Knowl. Data Eng. 5(5): 775-798(1993)
@article{DBLP:journals/tkde/SuGL93,
  author    = {Stanley Y. W. Su and
               Mingsen Guo and
               Herman Lam},
  title     = {Association Algebra: A Mathematical Foundation for Object-Oriented
               Databases},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {5},
  number    = {5},
  year      = {1993},
  pages     = {775-798},
  ee        = {db/journals/tkde/SuGL93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The application of the object-oriented (O-O) paradigm in the database management field has gained much attention in recent years. Several experimental and commercial O-O database management systems have become available; however, the existing O-O DBMS's still lack a solid mathematical foundation for the manipulation of O-O databases, the optimization of queries, and the design and selection of storage structures for supporting O-O database manipulations. This paper presents an association algebra (A-algebra) to serve as a mathematical foundation for processing O-O databases, which is analogous to the relational algebra used for processing relational databases. In this algebra, objects and their associations in an O-O database are uniformly represented by association patterns which are manipulated by a number of operators to produce other association patterns. Different from the relational algebra, in which set operations operate on relations with union-compatible structures, the A-algebra operators can operate on association patterns of homogeneous and heterogeneous structures. Different from the traditional record-based relational processing, the A-algebra allows very complex patterns of object associations to be directly manipulated. In this paper, the pattern-based query formulation and the A-algebra operators are described. Some mathematical properties of the algebraic operators are presented together with their application in query decomposition and optimization. The completeness of the A-algebra is also defined and proven. The A-algebra has been used as the basis for the design and implementation of an object-oriented query language, OQL, which is the query language used in a prototype Knowledge Base Management System OSAM*.KBMS.

Copyright © 1993 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

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

References

[1]
...
[2]
A. M. Alashqur, Stanley Y. W. Su, Herman Lam: OQL: A Query Language for Manipulating Object-oriented Databases. VLDB 1989: 433-442 BibTeX
[3]
A. M. Alashqur, Stanley Y. W. Su, Herman Lam: A Rule-based Language for Deductive Object-Oriented Databases. ICDE 1990: 58-67 BibTeX
[4]
François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 BibTeX
[5]
Jay Banerjee, Won Kim, Kyung-Chang Kim: Queries in Object-Oriented Databases. ICDE 1988: 31-38 BibTeX
[6]
Don S. Batory, Alejandro P. Buchmann: Molecular Objects, Abstract Data Types, and Data Models: A Framework. VLDB 1984: 172-184 BibTeX
[7]
Don S. Batory, Won Kim: Modeling Concepts for VLSI CAD Objects (Abstract). SIGMOD Conference 1985: 446 BibTeX
[8]
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 BibTeX
[9]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[10]
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
[11]
Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX
[12]
...
[13]
...
[14]
Daniel H. Fishman, David Beech, H. P. Cate, E. C. Chow, Tim Connors, J. W. Davis, Nigel Derrett, C. G. Hoch, William Kent, Peter Lyngbæk, Brom Mahbod, Marie-Anne Neimat, T. A. Ryan, Ming-Chien Shan: Iris: An Object-Oriented Database Management System. ACM Trans. Inf. Syst. 5(1): 48-69(1987) BibTeX
[15]
...
[16]
Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX
[17]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[18]
...
[19]
Won Kim, Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Darrell Woelk: Composite Object Support in an Object-Oriented Database System. OOPSLA 1987: 118-125 BibTeX
[20]
...
[21]
...
[22]
Christophe Lécluse, Philippe Richard, Fernando Vélez: O2, an Object-Oriented Data Model. SIGMOD Conference 1988: 424-433 BibTeX
[23]
Robert M. MacGregor: ARIEL - A Semantic Front-End to Relational DBMSs. VLDB 1985: 305-315 BibTeX
[24]
David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482 BibTeX
[25]
Frank Manola, Umeshwar Dayal: PDM: An Object-Oriented Data Model. OODBS 1986: 18-25 BibTeX
[26]
Lawrence A. Rowe, Michael Stonebraker: The POSTGRES Data Model. VLDB 1987: 83-96 BibTeX
[27]
...
[28]
Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX
[29]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[30]
Stanley Y. W. Su: Modeling Integrated Manufacturing Data with SAM*. IEEE Computer 19(1): 34-49(1986) BibTeX
[31]
...
[32]
...
[33]
Shalom Tsur, Carlo Zaniolo: An Implementation of GEM - Supporting a Semantic Data Model on a Relational Back-End. SIGMOD Conference 1984: 286-295 BibTeX
[34]
Darrell Woelk, Won Kim, Willis Luther: An Object-Oriented Approach to Multimedia Databases. SIGMOD Conference 1986: 311-325 BibTeX
[35]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX
[36]
Rahim Yaseen, Stanley Y. W. Su, Herman Lam: An Extensible Kernel Object Management System. OOPSLA 1991: 247-263 BibTeX
[37]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 BibTeX
[38]
Carlo Zaniolo, Hassan Aït-Kaci, David Beech, Stephanie J. Cammarata, David Maier: Object Oriented Database Systems and Knowledge Systems. Expert Database Workshop 1984: 49-65 BibTeX
[39]
Andrea H. Skarra, Stanley B. Zdonik, Steven P. Reiss: An Object Server for an Object-Oriented Database System. OODBS 1986: 196-204 BibTeX
[40]
...

Referenced by

  1. Stanley Y. W. Su, Soon J. Hyun, Hsin-Hsing M. Chen: Temporal Association Algebra: A Mathematical Foundation for Processing Object-Oriented Temporal Databases. IEEE Trans. Knowl. Data Eng. 10(3): 389-408(1998)
  2. George Semeczko, Stanley Y. W. Su, Tsae-Feng Yu, Fang Wang: Supporting Distributed Query Processing in a Heterogeneous Environment. DASFAA 1997: 107-116
  3. George Semeczko, Stanley Y. W. Su: Supporting Object Migration in Distributed Systems. DASFAA 1997: 59-66
  4. Carlos A. Tau, Clara Smith, Claudia Pons, Ana María Monteiro: Formally Speaking About Schemata, Bases, Classes and Objects. DASFAA 1995: 308-317
  5. Nabil Kamel, Ping Wu, Stanley Y. W. Su: A Pattern-Based Object Calculus. VLDB J. 3(1): 53-76(1994)
  6. Stanley Y. W. Su, Herman Lam, Srinivasa Eddula, Javier Arroyo, Neeta Prasad, Ronghao Zhuang: OSAM*KBMS: An Object-Oriented Knowledge Base Management System for Supporting Advanced Applications. SIGMOD Conference 1993: 540-541
  7. Mingsen Guo, Stanley Y. W. Su, Herman Lam: An Association Algebra For Processing Object-Oriented Databases. ICDE 1991: 23-32
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:27:51 2009