Tractable Query Languages for Complex Object Databases
Summary: Analyzes calculus-based queries on complex-object databases, proving that usage of higher-order types crucially affects query complexity. Shows fixpoint extensions (with range-restricted variants) capture PTIME under a “full-types” assumption, yielding tractable query languages. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,546 | Towards Tractable Algebras for Bags (Extended Abstract) | 1993 | PODS | 8.5606179e-05 |
| 4,378 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2329359e-05 |
| 4,612 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0428289e-05 |
| 4,782 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS | 5.9233349e-05 |
| 5,980 | A Query Language for NC | 1994 | PODS | 5.241279e-05 |
| 6,537 | On the Power of Algebras with Recursion | 1993 | SIGMOD | 5.0180143e-05 |
| 7,782 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS | 4.6479178e-05 |
| 12,837 | Tutorial: Languages for Collection Types | 1994 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 353 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00026275228 |
| 485 | A New Approach to Database Logic | 1984 | PODS | 0.00022061287 |
| 652 | Logic Programming With Sets | 1987 | PODS | 0.00018643929 |
| 910 | Sets and Negation in a Logic Database Language (LDL1) | 1987 | PODS | 0.00015398775 |
| 2,520 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6044305e-05 |
| 2,560 | Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions | 1988 | PODS | 8.541561e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |
| 4,494 | Non-Deterministic Languages to Express Deterministic Transformations | 1990 | PODS | 6.1363251e-05 |
| 5,102 | On the Expressive Power of Logic Programming Languages with Sets | 1988 | PODS | 5.6936517e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,856 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1905499e-05 |
| 6,548 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS | 5.0123519e-05 |
| 1,833 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS | 0.00010365844 |
| 4,782 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS | 5.9233349e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.6506061e-05 |
| 432 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023349408 |
| 3,195 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD | 7.4052272e-05 |
| 12,691 | Fixed-Point Query Languages for Linear Constraint Databases | 2000 | PODS | 4.1905499e-05 |
| 4,278 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.285241e-05 |
| 2,808 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.0939851e-05 |