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: 2498
Venue: SIGMOD
Year: 1989
Pagerank: 7.7292081e-05
Overall Rank: 3,128 | 78.55%
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,637	A Graph-Oriented Object Database Model	1990	PODS	8.3154765e-05
3,191	Method Schemas	1990	PODS	7.6525725e-05
4,702	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.5549225e-05
4,934	The Expressive Power of Structured Values in Pure OODB's (extended abstract)	1991	PODS	6.4357823e-05
7,793	Reflective programming in the relational algebra (extended abstract)	1993	PODS	5.5430288e-05
8,569	The Power of Methods With Parallel Semantics	1991	VLDB	5.4107086e-05
12,992	Applying an update method to a set of receivers (extended abstract)	1995	PODS	5.093636e-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
15	The Functional Data Model and the Data Language DAPLEX	1979	SIGMOD	0.00061144858
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
702	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014855299
740	O2, an Object-Oriented Data Model	1988	SIGMOD	0.00014482241
2,400	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.6299917e-05
2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.9790527e-05

Semantically Similar Papers

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