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.5701687e-05 |
| 4,381 | Functional and Predicative programming in OODB's | 1992 | PODS | 6.2389434e-05 |
| 4,611 | On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values | 2005 | PODS | 6.0488752e-05 |
| 4,778 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS | 5.9290535e-05 |
| 5,974 | A Query Language for NC | 1994 | PODS | 5.246329e-05 |
| 6,539 | On the Power of Algebras with Recursion | 1993 | SIGMOD | 5.02287e-05 |
| 7,782 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS | 4.6523963e-05 |
| 12,828 | Tutorial: Languages for Collection Types | 1994 | PODS | 4.1945683e-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 |
|---|---|---|---|---|
| 352 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00026299604 |
| 485 | A New Approach to Database Logic | 1984 | PODS | 0.00022085103 |
| 649 | Logic Programming With Sets | 1987 | PODS | 0.00018662857 |
| 912 | Sets and Negation in a Logic Database Language (LDL1) | 1987 | PODS | 0.00015414126 |
| 2,515 | Untyped Sets, Invention, and Computable Queries | 1989 | PODS | 8.6128871e-05 |
| 2,553 | Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions | 1988 | PODS | 8.5500139e-05 |
| 2,800 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.1019352e-05 |
| 4,491 | Non-Deterministic Languages to Express Deterministic Transformations | 1990 | PODS | 6.1422281e-05 |
| 5,102 | On the Expressive Power of Logic Programming Languages with Sets | 1988 | PODS | 5.6992154e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 12,847 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB | 4.1945683e-05 |
| 6,551 | Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract) | 1994 | PODS | 5.0171671e-05 |
| 1,835 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS | 0.00010375854 |
| 4,778 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS | 5.9290535e-05 |
| 7,773 | Formal Semantics and Analysis of Object Queries | 2003 | SIGMOD | 4.655071e-05 |
| 431 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS | 0.00023370207 |
| 3,189 | On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions | 1989 | SIGMOD | 7.4116834e-05 |
| 12,682 | Fixed-Point Query Languages for Linear Constraint Databases | 2000 | PODS | 4.1945683e-05 |
| 4,285 | A Query Language for List-Based Complex Objects | 1994 | PODS | 6.2913523e-05 |
| 2,800 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 8.1019352e-05 |