On the power of Rule-Based Languages with Sets
Summary: k-level COL/finite LDL/ELPS/IQL languages are data-complexity complete for the k‑th level of hyper‑exponential time and, with domain order, capture all relational generic queries at that level (without order they capture level k−1). Highlights that grouping rules and domain order strictly boost expressivity—grouping can encode certain non‑monotonic queries, positive ELPS gains power with an order, and finite ELPS needs negation for full expressibility. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Kumar Vadaparty (Rutgers University)
BibTeX Citation
@inproceedings{vadaparty_pods91,
address = {New York, NY, USA},
series = {{PODS} '91},
title = {{On the power of Rule-Based Languages with Sets}},
url = {https://dl.acm.org/doi/10.1145/113413.113416},
doi = {10.1145/113413.113416},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Vadaparty, Kumar},
year = {1991}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,239 | Towards a Unified Visual Database Access | 1993 | SIGMOD | 5.9425753e-05 |
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 355 | Object Identity As A Query Language Primitive | 1989 | SIGMOD | 0.00020351749 |
| 475 | A Calculus for Complex Objects | 1986 | PODS | 0.00017864549 |
| 544 | A New Approach to Database Logic | 1984 | PODS | 0.00016792556 |
| 971 | ILOG: Declarative Creation and Manipulation of Object Identifiers | 1990 | VLDB | 0.00012875736 |
| 2,110 | Theory of Database Queries (Extended Abstract) | 1988 | PODS | 9.1532803e-05 |
| 2,897 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS | 7.9790527e-05 |
| 3,564 | The Powerset Algebra As A Result Of Adding Programming Constructs To The Nested Relational Algebra | 1988 | SIGMOD | 7.3058238e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 13,040 | Investigation of Algebraic Query Optimisation for Database Programming Languages | 1994 | VLDB |
| 2 | 7,849 | New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions | 1994 | PODS |
| 3 | 414 | On the Complexity of Database Queries (Extended Abstract) | 1997 | PODS |
| 4 | 2,897 | On the Expressive Power of Database Queries with Intermediate Types | 1988 | PODS |
| 5 | 4,336 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS |
| 6 | 6,184 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS |
| 7 | 1,890 | Relational Expressive Power of Constraint Query Languages | 1996 | PODS |
| 8 | 6,785 | Expressiveness of Guarded Existential Rule Languages | 2014 | PODS |
| 9 | 5,210 | On the Expressive Power of Logic Programming Languages with Sets | 1988 | PODS |
| 10 | 1,864 | The Expressiveness of a Family of Finite Set Languages | 1991 | PODS |