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: 810
Venue: PODS
Year: 1988
Pagerank: 0.00011926567
Overall Rank: 1,450 | 89.93%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ashok K. Chandra

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
603	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019334592
2,288	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	9.093171e-05
7,363	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	4.7461604e-05
8,173	The Power of Methods With Parallel Semantics	1991	VLDB	4.5640563e-05
8,448	On the power of Rule-Based Languages with Sets	1991	PODS	4.5039113e-05
8,567	Semi-determinism (extended abstract)	1992	PODS	4.4893996e-05
12,801	Combinatorial Games in Database Theory	1995	PODS	4.1905499e-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.0040465394
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
173	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038731283
375	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025262028
520	LDL: A Logic-Based Data-Language	1986	VLDB	0.00021145923
552	Why Not Negation By Fixpoint?	1988	PODS	0.00020309855
652	Logic Programming With Sets	1987	PODS	0.00018643929
910	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00015398775
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
1,920	A Transaction Language Complete for Database Update and Specification	1987	PODS	0.00010092077
2,808	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.0939851e-05
5,102	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS	5.6936517e-05
5,241	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	5.6057795e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,773	Formal Semantics and Analysis of Object Queries	2003	SIGMOD	4.6506061e-05
4,343	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2665123e-05
1,738	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010704219
6,667	Typed Query Languages for Databases Containing Queries	1998	PODS	4.9651817e-05
9,285	A Theory of Regular Queries	2016	PODS	4.3594818e-05
2,396	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.8892825e-05
3,043	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6632326e-05
3,195	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4052272e-05
12,856	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1905499e-05
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408