On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions

Summary: Formal framework for expressive power and complexity of OODB queries; compares three set models—object-based regular schemas, value-based semantics, and algebraic OODBs. Unrestricted queries cover all computable queries; with a restricted operator, PSPACE-complete (object-based) or hyper-exponential (value-based); algebraic OODBs stay PTIME and introduce algebra + pointwise recursion, enabling generalized transitive closure. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h97b7d0c9b3d920c5
Venue: SIGMOD
Year: 1989
Pagerank: 7.5578905e-05
Overall Rank: 3,183 | 78.61%
DOI: 10.1145/67544.66940

Incoming Non-self Citations Over Time

Authors

1. Richard Hull (University of Southern California)
2. Jianwen Su (University of Southern California)

BibTeX Citation

@inproceedings{hull_sigmod89,
        title = {{On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions}},
        author = {Hull, Richard and Su, Jianwen},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66940},
        url = {https://dl.acm.org/doi/10.1145/67544.66940},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,665	A Graph-Oriented Object Database Model	1990	PODS	8.1568013e-05
3,264	Method Schemas	1990	PODS	7.4808695e-05
4,807	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.4079967e-05
5,053	The Expressive Power of Structured Values in Pure OODB's (extended abstract)	1991	PODS	6.2955826e-05
7,929	Reflective programming in the relational algebra (extended abstract)	1993	PODS	5.4248505e-05
8,740	The Power of Methods With Parallel Semantics	1991	VLDB	5.2893082e-05
13,282	Applying an update method to a set of receivers (extended abstract)	1995	PODS	4.9793485e-05

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
16	The Functional Data Model and the Data Language DAPLEX	1979	SIGMOD	0.00059996338
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00023995155
718	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014530776
759	O2, an Object-Oriented Data Model	1988	SIGMOD	0.00014164131
2,457	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4375276e-05
2,968	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.8013847e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
2	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
3	3,046	Tractable Query Languages for Complex Object Databases	1991	PODS
4	2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
5	2,825	Modeling Complex Structures in Object-Oriented Databases	1989	PODS
6	4,523	Functional and Predicative programming in OODB's	1992	PODS
7	2,968	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS
8	5,053	The Expressive Power of Structured Values in Pure OODB's (extended abstract)	1991	PODS
9	13,340	Database Method Schemas and Object Creation	1993	PODS
10	8,300	Formal Semantics and Analysis of Object Queries	2003	SIGMOD