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)
Incoming Non-self Citations Over Time
Authors
- 1. Richard Hull
- 2. Jianwen Su
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,799 | A Graph-Oriented Object Database Model | 1990 | PODS | 8.105074e-05 |
| 2,960 | Method Schemas | 1990 | PODS | 7.8135404e-05 |
| 4,611 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0488752e-05 |
| 4,894 | The Expressive Power of Structured Values in Pure OODB's (extended abstract) | 1991 | PODS | 5.8477088e-05 |
| 7,252 | Reflective programming in the relational algebra (extended abstract) | 1993 | PODS | 4.7889007e-05 |
| 8,172 | The Power of Methods With Parallel Semantics | 1991 | VLDB | 4.5684406e-05 |
| 12,798 | Applying an update method to a set of receivers (extended abstract) | 1995 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 12 | The Functional Data Model and the Data Language DAPLEX | 1979 | SIGMOD | 0.0011248121 |
| 175 | Traversal Recursion: A Practical Approach to Supporting Recursive Applications | 1986 | SIGMOD | 0.00038338694 |
| 374 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025286717 |
| 630 | O2, an Object-Oriented Data Model | 1988 | SIGMOD | 0.00018939398 |
| 2,515 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6128871e-05 |
| 2,800 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.1019352e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 12,847 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1945683e-05 |
| 3,040 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6707607e-05 |
| 2,398 | Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) | 1992 | PODS | 8.8973978e-05 |
| 2,768 | Modeling Complex Structures in Object-Oriented Databases | 1989 | PODS | 8.1473167e-05 |
| 4,381 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2389434e-05 |
| 2,800 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.1019352e-05 |
| 4,894 | The Expressive Power of Structured Values in Pure OODB's (extended abstract) | 1991 | PODS | 5.8477088e-05 |
| 12,857 | Database Method Schemas and Object Creation | 1993 | PODS | 4.1945683e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.655071e-05 |