article

Free access

Object identity as a query language primitive

Authors:

Serge Abiteboul,

Paris C. KanellakisAuthors Info & Claims

ACM SIGMOD Record, Volume 18, Issue 2

Pages 159 - 173

https://doi.org/10.1145/66926.66941

Published: 01 June 1989 Publication History

Abstract

We demonstrate the power of object identities (oid's) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. Our main contribution is the operational part of the data model, the query language IQL, which uses oid's for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets and (3) to express any computable database query. IQL can be statically type checked, can be evaluated bottom-up and naturally generalizes most popular rule-based database languages. The model can also be extended to incorporate type inheritance, without changes to IQL. Finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinite trees and whose operational part is IQL.

References

[1]

S. Abiteboul and C. Beeri. On the Manipulation of Complex Objects. INRIA Technical Report, 1987.

[2]

S. Abiteboul and S. Grumbach. COL: a Logicbased Language for Complex Objects. In Proc. EDBT, 271-293, 1988.

Digital Library

[3]

S. Abiteboul, S. Grumbach, A. Voisard, and E. Waller. An Extensible Rule-based Language with Complex Objects and Data-functions. In Proc. DBPL-H Workshop, Oregon, 1989. To appear.

Digital Library

[4]

S. Abiteboul and R. Hull. IFO: A Formal Semantic Database Model. A CM TODS, 12:525-565, 1987.

Digital Library

[5]

S. Abiteboul and R. Hull. Data-functions, Datalog and Negation. In Proc. A CM SIGMOD, 143-153, 1988.

Digital Library

[6]

S. Abiteboul and P. Kanellakis. Object Identity as a Query Language Primitive INRIA Techical Report, March 1989.

[7]

S. Abiteboul and V. Vianu. Procedural and Declarative Database Update Language. In Proc. ACM PODS, 240-250, 1988.

Digital Library

[8]

S. Abiteboul and V. Vianu. A Transaction Language Complete for Database Update and Specification. In Proc. A CM PODS, 260-268, 1987.

Digital Library

[9]

M. Atkinson and P. Buneman. Types and Persistence in Database Programming Languages. A CM Computing Surveys, June 1987.

Digital Library

[10]

F. Bancilhon. Object-Oriented Database Systems. In Proc. A CM PODS, 152-162, 1988.

Digital Library

[11]

F. Bancilhon et al. The Design and Implementation of 02, an Object-Oriented Database System. In Proc. OODBSP Workshop, Badmunster RFA, 1988.

Digital Library

[12]

F. Bancilhon, S. Cluet, and C. Delobel. Query Languages for Object-Oriented Database Systems. In Proc. DBPL-H Workshop, Oregon, 1989. To appear.

Digital Library

[13]

F. Bancilhon and S. Khoshafian. A Calculus for Complex Objects. In Proc. A CM PODS, 53-60, 1986.

Digital Library

[14]

J. Banerjee et al. Data Model Issues for Object- Oriented Applications. ACM TOIS, 5"1:3-26, 1987.

Digital Library

[15]

C. Beeri and al. Sets and Negation in a Logic Database Language (LDL1). In Proc. A CM PODS, 21-37, 1987.

Digital Library

[16]

L. Cardelli. A Semantics of Multiple Inheritance. Information and Computation, 76:138-164, 1988.

Digital Library

[17]

M.J. Carey, D.J. Dewitt, and S.L. Vandenberg. A Data Model and Query Language for EXODUS. In Proc. A CM SIGMOD, 413-423, 1988.

Digital Library

[18]

A. Chandra and D. Harel. Computable Queries for Relational Data Bases. JCSS, 21:2:156-178, 1980.

[19]

E.F. Codd. A Relational Model of Data for Large Shared Data Banks. CA CM, 13:6:377-387, 1970.

Digital Library

[20]

T. Codd. Extending the Database Relational Model to Capture more Meaning. A CM TODS, 4:4:397-434, 1979.

Digital Library

[21]

B. Courcelle. Fundamental Properties of Infinite Trees. TCS, 25, 95-169, 1983.

[22]

E. Dahlaus and J. Makowski. Computable Directory Queries. In Prac. CAAP, 1986. LNCS 214, Springer-Verlag.

Digital Library

[23]

D. Fishman et al. Iris" an Object-Oriented Database Management System. A CM TOIS, 5:1:46-69, 1987.

[24]

P. Fischer and S. Thomas. Operators for Nonfirst-normal-form Relations. In Proc. COMPSAC, Chicago USA,1983.

[25]

A. Goldberg and D. Robson. Smalltalk 80, the Language and Implementation. Addison-Wesley, 1983.

Digital Library

[26]

R. Hull. Relative information Capacity of Simple Relational Schemata. Siam }. of Computing, 15:3, 1986.

Digital Library

[27]

R. Hull and J. Su. Untyped Sets, Invention and Computable Queries. In Proc. A CM PODS 1989. To appear.

Digital Library

[28]

B. :iaeschke and tt.J. Sehek. Remarks on the Algebra of Non-first-normal-form Relations. In Proc. A CM PODS, 124-138, 1982.

Digital Library

[29]

P. Kanellakis. Elements of Relational Database Theory. Brown U. Technical Report, 1988. To appear as a chapter in the Handbook of Theoretical Computer Science.

Digital Library

[30]

S. Khoshafian and G. Copeland. Object Identity. In Proc. OOPSALA, 1986.

Digital Library

[31]

M. Kifer and j. Wu. A Logic for Object-Oriented Logic Programming (Mater's O-logic: Revisited). In Proc. A CM PODS, 1989. To appear.

Digital Library

[32]

W. Kim. A Foundation for Object Oriented Databases. Technical Report, MCC, 1988.

[33]

P.G. Kolaitis and C.tt. Papadimitriou. Why not Negation by Fixpoint? In Proc. ACM PODS, 231- 239, 1987.

Digital Library

[34]

H.F. Korth, M.A. Roth, and A. Silbersehatz. Extended Algebra and Calculus for not 1NF Relational Databases. U. Texas Austin Technical Report, 1985.

Digital Library

[35]

G.M. Kuper. Logic Programming with Sets. In Proc. ACM PODS, 11-20, 1987.

Digital Library

[36]

G.M. Kuper. The Logical Data Model: a New Approach to Database Logic. Stanford U., PhD thesis, 1985.

Digital Library

[37]

G.M. Kuper and M.Y. Vardi. A New Approach to Database Logic. In Proc. A CM PODS, 86-96, 1984.

Digital Library

[38]

C. Lecluse and P. Richard. Modeling Complex Structures in Object-Oriented Databases. In Proc. A CM PODS, 1989. To appear.

Digital Library

[39]

C. Lecluse, P. Richard, and F. Velez. 02, an Object-Oriented Data Model. In Proc. ACM SIG- MOD, 424-434, 1988.

Digital Library

[40]

D. Mater. A Logic for Objects. in Proc. of Workshop on Foundations of Deductive Databases and Logic Programming, Washington USA, 1986.

[41]

D. Mater, A. Otis, and A. Purdy. Development of an Object-Oriented Dbms. Quarterly Bulletin of IEEE on Database Engineering, 8, 1985.

[42]

H. Schek and M. Scholl. The Relational Model with Relation-valued Attributes. Information Systems, 1986.

Digital Library

[43]

J.D. Ullman. Database Theory- Past and Future. In Proc. A CM PODS, 1-10, 1987.

Digital Library

[44]

J.D. Ullman. Principles of Database and Knowledge-Base Systems, Volume L Computer Science Press, 1988.

Digital Library

[45]

J. Verso. Verso: a Database Machine Based on non-lNF Relations. To appear in Nested Relations and Complex Objects Springer-Verlag.

Digital Library

[46]

S. Zdonik. Object Management Systems for Design Environments. Quarterly Bulletin of IEEE on Database Engineering, 8, 1985.

Cited By

Gogolla M(2005)A declarative query approach to object identificationOOER '95: Object-Oriented and Entity-Relationship Modeling10.1007/BFb0020521(65-76)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0020521
Bergamaschi S(2005)Extraction of informations from highly heterogeneous source of textual dataCooperative Information Agents10.1007/3-540-62591-7_23(42-63)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-62591-7_23
Grumbach SMilo T(2005)An algebra for pomsetsDatabase Theory — ICDT '9510.1007/3-540-58907-4_16(191-207)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-58907-4_16
Show More Cited By

Index Terms

Object identity as a query language primitive

Recommendations

Object identity as a query language primitive

We demonstrate the power of object identities (oids) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas ...
Object identity as a query language primitive
SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data

We demonstrate the power of object identities (oid's) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas ...
Object Identity As A Query Language Primitive

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 18, Issue 2

June 1989

442 pages

ISSN:0163-5808

DOI:10.1145/66926

Issue’s Table of Contents

SIGMOD '89: Proceedings of the 1989 ACM SIGMOD international conference on Management of data
June 1989
451 pages
ISBN:0897913175
DOI:10.1145/67544
Editors:
James Clifford,
Bruce Lindsay,
David Maier

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Published in SIGMOD Volume 18, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

281
Total Citations
View Citations
699
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)9

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gogolla M(2005)A declarative query approach to object identificationOOER '95: Object-Oriented and Entity-Relationship Modeling10.1007/BFb0020521(65-76)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0020521
Bergamaschi S(2005)Extraction of informations from highly heterogeneous source of textual dataCooperative Information Agents10.1007/3-540-62591-7_23(42-63)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-62591-7_23
Grumbach SMilo T(2005)An algebra for pomsetsDatabase Theory — ICDT '9510.1007/3-540-58907-4_16(191-207)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-58907-4_16
Bugliesi MJamil H(2005)A logic for encapsulation in object oriented languagesProgramming Language Implementation and Logic Programming10.1007/3-540-58402-1_16(215-229)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-58402-1_16
Buchheit MJeusfeld MNutt WStaudt M(2005)Subsumption between queries to object-oriented databasesAdvances in Database Technology — EDBT '9410.1007/3-540-57818-8_37(15-22)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-57818-8_37
Kalinichenko LZadorozhny V(2005)A generalized information resource query language and basic query evaluation techniqueDeductive and Object-Oriented Databases10.1007/3-540-55015-1_29(546-566)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-55015-1_29
Wieringa R(2005)A formalization of objects using equational dynamic logicDeductive and Object-Oriented Databases10.1007/3-540-55015-1_23(431-452)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-55015-1_23
Kalinichenko L(2005)Synthesis: Towards a query facility for generalized information resourcesNext Generation Information System Technology10.1007/3-540-54141-1_20(363-384)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-54141-1_20
Schmidt JMatthes F(2005)Language technology for post-relational data systemsDatabase Systems of the 90s10.1007/3-540-53397-4_33(81-114)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-53397-4_33
Buneman PFan WWeinstein S(2003)Interaction between path and type constraintsACM Transactions on Computational Logic10.1145/937555.9375604:4(530-577)Online publication date: 1-Oct-2003
https://dl.acm.org/doi/10.1145/937555.937560
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents