Theory of Database Queries (Extended Abstract)

Summary: Surveys foundational theory of query languages: equivalence of first-order logic and relational algebra, and the completeness vs. efficiency trade-off. Emphasizes practically useful restricted classes (SPJ, tableaux, sargable), unique minimal forms for SPJ, and the influence of logic programming on query optimization theory. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1816e2917968a224
Venue: PODS
Year: 1988
Pagerank: 8.953998e-05
Overall Rank: 2,150 | 85.55%
DOI: 10.1145/308386.308396

Incoming Non-self Citations Over Time

Authors

1. Ashok K. Chandra (IBM)

BibTeX Citation

@inproceedings{chandra_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Theory of Database Queries (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/308386.308396},
        doi = {10.1145/308386.308396},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chandra, Ashok K.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
794	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00013941847
2,474	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	8.4106815e-05
8,051	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	5.3992494e-05
8,740	The Power of Methods With Parallel Semantics	1991	VLDB	5.2893082e-05
8,935	Semi-determinism (extended abstract)	1992	PODS	5.2559789e-05
13,276	Combinatorial Games in Database Theory	1995	PODS	4.9793485e-05
13,387	On the power of Rule-Based Languages with Sets	1991	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
635	LDL: A Logic-Based Data-Language	1986	VLDB	0.00015368492
718	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00014530776
828	Logic Programming With Sets	1987	PODS	0.00013614671
1,012	Why Not Negation By Fixpoint?	1988	PODS	0.00012520852
1,049	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.0001229888
1,503	The Complexity of Evaluating Relational Queries	1983	PODS	0.00010455233
1,767	A Transaction Language Complete for Database Update and Specification	1987	PODS	9.6939822e-05
2,968	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.8013847e-05
5,335	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS	6.1748115e-05
5,681	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	6.0401867e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,300	Formal Semantics and Analysis of Object Queries	2003	SIGMOD
2	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
3	1,950	Relational Expressive Power of Constraint Query Languages	1996	PODS
4	9,611	A Theory of Regular Queries	2016	PODS
5	7,337	Typed Query Languages for Databases Containing Queries	1998	PODS
6	2,349	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS
7	3,046	Tractable Query Languages for Complex Object Databases	1991	PODS
8	3,183	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD
9	13,330	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
10	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS