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.5296268e-05
Overall Rank: 3,196 | 78.58%
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,669	A Graph-Oriented Object Database Model	1990	PODS	8.1313046e-05
3,278	Method Schemas	1990	PODS	7.4526035e-05
4,831	On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values	2005	PODS	6.3838625e-05
5,077	The Expressive Power of Structured Values in Pure OODB's (extended abstract)	1991	PODS	6.2719516e-05
7,948	Reflective programming in the relational algebra (extended abstract)	1993	PODS	5.4045599e-05
8,768	The Power of Methods With Parallel Semantics	1991	VLDB	5.2693231e-05
13,329	Applying an update method to a set of receivers (extended abstract)	1995	PODS	4.9605343e-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.00059778867
225	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.0002391304
720	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.0001447659
763	O2, an Object-Oriented Data Model	1988	SIGMOD	0.00014111102
2,466	Untyped Sets, Invention, and Computable Queries	1989	PODS	8.4057294e-05
2,982	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.7719553e-05

Semantically Similar Papers

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