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,800 | A Graph-Oriented Object Database Model | 1990 | PODS | 8.1079752e-05 |
| 2,964 | Method Schemas | 1990 | PODS | 7.8060034e-05 |
| 4,612 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0428289e-05 |
| 4,901 | The Expressive Power of Structured Values in Pure OODB's (extended abstract) | 1991 | PODS | 5.8417589e-05 |
| 7,248 | Reflective programming in the relational algebra (extended abstract) | 1993 | PODS | 4.7843101e-05 |
| 8,173 | The Power of Methods With Parallel Semantics | 1991 | VLDB | 4.5640563e-05 |
| 12,807 | Applying an update method to a set of receivers (extended abstract) | 1995 | PODS | 4.1905499e-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.0011268747 |
| 157 | Traversal Recursion: A Practical Approach to Supporting Recursive Applications | 1986 | SIGMOD | 0.0004048407 |
| 375 | PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract) | 1988 | PODS | 0.00025262028 |
| 631 | O2, an Object-Oriented Data Model | 1988 | SIGMOD | 0.00018904557 |
| 2,520 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6044305e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 432 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023349408 |
| 12,856 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1905499e-05 |
| 3,043 | Tractable Query Languages for Complex Object Databases | 1991 | PODS | 7.6632326e-05 |
| 2,396 | Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract) | 1992 | PODS | 8.8892825e-05 |
| 2,775 | Modeling Complex Structures in Object-Oriented Databases | 1989 | PODS | 8.139455e-05 |
| 4,378 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2329359e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |
| 4,901 | The Expressive Power of Structured Values in Pure OODB's (extended abstract) | 1991 | PODS | 5.8417589e-05 |
| 12,866 | Database Method Schemas and Object Creation | 1993 | PODS | 4.1905499e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.6506061e-05 |