On the Equivalence of Database Restructurings Involving Object Identifiers

Summary: Equivalence of ILOG programs that create OIDs via Skolem functors, distinguishing exposed (Skolem visible) vs obscured (opaque fresh OIDs). Undecidable with negation or recursion; exposed-equivalence decidable for nrec ILOG; obscured-equivalence decidable for a broad class and one special case, full nrec obscured remains open. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h76d1da088335662e
Venue: PODS
Year: 1991
Pagerank: 6.4877004e-05
Overall Rank: 4,646 | 68.77%
DOI: 10.1145/113413.113443

Incoming Non-self Citations Over Time

Authors

1. Richard Hull (University of Southern California)
2. Masatoshi Yoshikawa (Kyoto Sangyo University)

BibTeX Citation

@inproceedings{hull_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{On the Equivalence of Database Restructurings Involving Object Identifiers}},
        url = {https://dl.acm.org/doi/10.1145/113413.113443},
        doi = {10.1145/113413.113443},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hull, Richard and Yoshikawa, Masatoshi},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,127	Query Rewriting for Semistructured Data	1999	SIGMOD	9.0005009e-05
2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.5999717e-05
8,625	Static Analysis of Graph Database Transformations	2023	PODS	5.2999883e-05
8,729	New Data Models and Languages - the Challenge	1992	PODS	5.2905577e-05
8,935	Semi-determinism (extended abstract)	1992	PODS	5.2559789e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
366	Object Identity As A Query Language Primitive	1989	SIGMOD	0.00019923978
559	A New Approach to Database Logic	1984	PODS	0.00016422254
904	F-Logic: A Higher-Order Language for Reasoning about Objects, Inheritance, and Scheme	1989	SIGMOD	0.00013171457
1,003	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012597028
1,767	A Transaction Language Complete for Database Update and Specification	1987	PODS	9.6939822e-05
1,951	A Logic for Object-Oriented Logic Programming (Maier's O-Logic Revisited)	1989	PODS	9.3191736e-05
3,142	C-Logic of Complex Objects	1989	PODS	7.5983724e-05
3,218	Mapping a Semantic Database Model to the Relational Model	1987	SIGMOD	7.5212385e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
2	13,340	Database Method Schemas and Object Creation	1993	PODS
3	8,300	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
4	3,183	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD
5	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
6	13,342	A Logical Semantics for Object-Oriented Databases	1993	SIGMOD
7	13,395	A Non-deterministic Deductive Database Language	1991	SIGMOD
8	8,051	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD
9	366	Object Identity As A Query Language Primitive	1989	SIGMOD
10	1,003	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB