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}
}
BibTeX

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 ... BibTeX

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 BibTeX

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

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)
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:13 2009