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

Using Witness Generators to Support Bi-directional Update Between Object-Based Databases.

Ti-Pin Chang, Richard Hull: Using Witness Generators to Support Bi-directional Update Between Object-Based Databases. PODS 1995: 196-207
@inproceedings{DBLP:conf/pods/ChangH95,
  author    = {Ti-Pin Chang and
               Richard Hull},
  title     = {Using Witness Generators to Support Bi-directional Update Between
               Object-Based Databases},
  booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 22-25, 1995, San Jose,
               California},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {196-207},
  ee        = {http://doi.acm.org/10.1145/212433.220213, db/conf/pods/ChangH95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper considers the issue of incrementally maintaining materialized replicated information in the context of object-based databases. "Uni-directional" update concerns propagating updates in one direction, and is closely related to the materialized view update problem. "Bi-directional" update arises when two databases hold overlapping information, and users of either database have the authority to make updates to that information. The focus here is on the impact of object identifiers (OIDs). A restricted form of ILOG is used, that corresponds essentially to select-project-join queries extended to include OID invention.

If auxiliary information is not maintained, then the uni- and bi-directional update problems are shown to be essentially equivalent to the graph isomorphism problem, and thus probably intractable. A form of auxiliary information, called "witnesses", can be used to bring the uni-directional update problem into LOGSPACE. For the bi-directional case a subtlety arises in connection with incremental maintanence of the witnesses. This paper presents a non-trivial procedure that can be used in a limited context for creating programs that maintain witnesses. If such "witness generator" programs are available, then the bi-directional update problem is also in LOGSPACE.

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

Printed Edition

Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1159 KB]

References

[AB91]
Serge Abiteboul, Anthony J. Bonner: Objects and Views. SIGMOD Conference 1991: 238-247 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AH87]
Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AHV94]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AK89]
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cab95]
Luca Cabibbo: On the Power of Stratified Logic Programs with Value Invention for Expressing Database Transformations. ICDT 1995: 208-221 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha94]
...
[CW92]
...
[Day89]
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DS93]
Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EK91]
Frank Eliassen, Randi Karlsen: Interoperability and Object Identity. SIGMOD Record 20(4): 25-29(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HY90]
Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HY91]
Richard Hull, Masatoshi Yoshikawa: On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991: 328-340 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KL89]
Michael Kifer, Georg Lausen: F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme. SIGMOD Conference 1989: 134-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mai86]
...
[PI94]
Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RSK91]
Marek Rusinkiewicz, Amit P. Sheth, George Karabatis: Specifying Interdatabase Dependencies in a Multidatabase Environment. IEEE Computer 24(12): 46-53(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Catriel Beeri, Tova Milo: Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999: 296-313
  2. Tova Milo, Sagit Zohar: Using Schema Matching to Simplify Heterogeneous Data Translation. VLDB 1998: 122-133
  3. Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61
  4. Serge Abiteboul, Sophie Cluet, Tova Milo: Correspondence and Translation for Heterogeneous Data. ICDT 1997: 351-363
  5. Zoé Lacroix, Claude Delobel, Philippe Brèche: Object Views and Database Restructuring. DBPL 1997: 180-201
  6. Gang Zhou, Richard Hull, Roger King, Jean-Claude Franchitti: Data Integration and Warehousing Using H2O. IEEE Data Eng. Bull. 18(2): 29-40(1995)

Copyright © Mon Nov 2 21:04:29 2009 by Michael Ley (ley@uni-trier.de)