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
[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
- Catriel Beeri, Tova Milo:
Schemas for Integration and Translation of Structured and Semi-structured Data.
ICDT 1999: 296-313
- Tova Milo, Sagit Zohar:
Using Schema Matching to Simplify Heterogeneous Data Translation.
VLDB 1998: 122-133
- Richard Hull:
Managing Semantic Heterogeneity in Databases: A Theoretical Perspective.
PODS 1997: 51-61
- Serge Abiteboul, Sophie Cluet, Tova Milo:
Correspondence and Translation for Heterogeneous Data.
ICDT 1997: 351-363
- Zoé Lacroix, Claude Delobel, Philippe Brèche:
Object Views and Database Restructuring.
DBPL 1997: 180-201
- 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