ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On the Equivalence of Database Restructurings Involving Object Identifiers.

Richard Hull, Masatoshi Yoshikawa: On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991: 328-340
@inproceedings{DBLP:conf/pods/HullY91,
  author    = {Richard Hull and
               Masatoshi Yoshikawa},
  title     = {On the Equivalence of Database Restructurings Involving Object
               Identifiers},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {328-340},
  ee        = {db/conf/pods/HullY91.html, http://doi.acm.org/10.1145/113413.113443},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The equivalence problem is studied for programs specifying queries and database restructurings in models using object identity. We use the family of ILOG languages, which captures essential features of several data restructuring languages in the theoretical and applied literature. ILOG uses a mechanism based on Skolem functors for 'inventing" object identifiers (OIDs). Two notions of equivalence are articulated: under exposed equivalence the Skolem terms forming new OIDs are exposed; under obscured equivalence these terms are "replaced" with "new", uninterpreted OIDs. In general, e.g., if either negation or recursion is present, both forms of equivalence are undecidable. In the case of nrecILOG, which can be viewed as unions of conjunctive queries with OID creation, exposed equivalence is decidable. The decidability of obscured equivalence for nrecILOG remains open, but it is shown here to be decidable for a broad class of programs, and for an additional special case.

Copyright © 1991 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.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition

Citation Page BibTeX

References

[Abi90]
...
[ABW86]
...
[AH87]
Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX
[AK89]
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
[Apt88]
...
[AV87]
Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268 BibTeX
[BLN86]
Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986) BibTeX
[Che76]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[CM77]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
[CW89]
Weidong Chen, David Scott Warren: C-Logic of Complex Objects. PODS 1989: 369-378 BibTeX
[Day89]
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 BibTeX
[DH84]
Umeshwar Dayal, Hai-Yann Hwang: View Definition and Generalization for Database Integration in a Multidatabase System. IEEE Trans. Software Eng. 10(6): 628-645(1984) BibTeX
[DiP69]
Robert A. Di Paola: The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas. J. ACM 16(2): 324-327(1969) BibTeX
[HK87]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[HM85]
Dennis Heimbigner, Dennis McLeod: A Federated Architecture for Information Management. ACM Trans. Inf. Syst. 3(3): 253-278(1985) BibTeX
[HY90]
Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468 BibTeX
[KL89]
Michael Kifer, Georg Lausen: F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme. SIGMOD Conference 1989: 134-146 BibTeX
[KLW90]
Michael Kifer, Georg Lausen, James Wu: Logical Foundations of Object-Oriented and Frame-Based Languages. J. ACM 42(4): 741-843(1995) BibTeX
[KP76]
...
[KV84]
Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX
[KW89]
Michael Kifer, James Wu: A Logic for Object-Oriented Logic Programming (Maier's O-Logic Revisited). PODS 1989: 379-393 BibTeX
[Llo87]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[LV87]
Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142 BibTeX
[Mai86]
...
[Mot87]
Amihai Motro: Superviews: Virtual Integration of Multiple Databases. IEEE Trans. Software Eng. 13(7): 785-798(1987) BibTeX
[Sch87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[vG86]
...
[ZM90]
Stanley B. Zdonik, David Maier (Eds.): Readings in Object-Oriented Database Systems. Morgan Kaufmann 1990, ISBN 1-55860-000-0
BibTeX

Referenced by

  1. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
  2. Zoé Lacroix, Claude Delobel, Philippe Brèche: Object Views and Database Restructuring. DBPL 1997: 180-201
  3. Ti-Pin Chang, Richard Hull: Using Witness Generators to Support Bi-directional Update Between Object-Based Databases. PODS 1995: 196-207
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  5. Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211
  6. Jan Van den Bussche, Dirk Van Gucht: Semi-determinism. PODS 1992: 191-201
  7. Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15
  8. Marie Duzi: Semantic Information Connected with Data. ICDT 1992: 376-390
  9. Richard Hull, Surjatini Widjojo, Dave Wile, Masatoshi Yoshikawa: On Data Restructuring and Merging with Object Identity. IEEE Data Eng. Bull. 14(2): 18-22(1991)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:04 2009