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

Summary: Shows incremental uni-/bi-directional update for object DBs with SPJ+OID-invention ILOG is, without auxiliaries, essentially graph-isomorphism hard. Introduces "witness" auxiliary data to bring uni-directional update to LOGSPACE and gives a limited "witness-generator" procedure enabling bi-directional update in LOGSPACE. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1068
Venue: PODS
Year: 1995
Pagerank: 6.5897093e-05
Overall Rank: 3,959 | 72.46%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ti-Pin Chang
2. Richard Hull

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
294	Using Schema Matching to Simplify Heterogeneous Data Translation	1998	VLDB	0.00028669519
1,384	Managing Semantic Heterogeneity in Databases : A Theoretical Perspective	1997	PODS	0.00012262892

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
352	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00026299604
669	F-Logic: A Higher-Order Language for Reasoning about Objects, Inheritance, and Scheme	1989	SIGMOD	0.00018430212
845	Objects and Views	1991	SIGMOD	0.0001599936
1,018	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00014627963
1,424	Managing Semantic Heterogeneity with Production Rules and Persistent Queues	1993	VLDB	0.00012054309
4,632	Dyn-FO: A Parallel, Dynamic Complexity Class (Preliminary Version)	1994	PODS	6.0342363e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,931	Consistency of Versions in Object-Oriented Databases	1990	VLDB	4.8925595e-05
3,476	Efficient Maintenance of Materialized Mediated Views (Extended Abstract)	1995	SIGMOD	7.0587697e-05
9,540	Object Projection Views In The Dynamic Relational Model	1984	PODS	4.3265281e-05
261	Maintenance Of Views	1984	SIGMOD	0.00030020186
8,188	Integrity Maintenance in an Object-Oriented Database	1992	VLDB	4.5645799e-05
1,093	Incremental Maintenance of Externally Materialized Views	1996	VLDB	0.00014134451
481	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00022167223
4,730	On the Equivalence of Database Restructurings Involving Object Identifiers	1991	PODS	5.967211e-05
1,639	Incremental Maintenance for Materialized Views over Semistructured Data	1998	VLDB	0.00011048834
2,469	Updating Relational Databases through Object-Based Views	1991	SIGMOD	8.7346857e-05