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.00011938045
Overall Rank: 1,448 | 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
602	On the Complexity of Bounded-Variable Queries	1995	PODS	0.00019352415
2,285	Local Verification of Global Integrity Constraints in Distributed Databases	1993	SIGMOD	9.0985926e-05
7,368	IDLOG: Extending the Expressive Power of Deductive Database Languages	1990	SIGMOD	4.7507411e-05
8,172	The Power of Methods With Parallel Semantics	1991	VLDB	4.5684406e-05
8,454	On the power of Rule-Based Languages with Sets	1991	PODS	4.5082358e-05
8,570	Semi-determinism (extended abstract)	1992	PODS	4.4937074e-05
12,792	Combinatorial Games in Database Theory	1995	PODS	4.1945683e-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.0040449103
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
374	PROCEDURAL AND DECLARATIVE DATABASE UPDATE LANGUAGES (Extended Abstract)	1988	PODS	0.00025286717
519	LDL: A Logic-Based Data-Language	1986	VLDB	0.00021154077
551	Why Not Negation By Fixpoint?	1988	PODS	0.00020329959
649	Logic Programming With Sets	1987	PODS	0.00018662857
912	Sets and Negation in a Logic Database Language (LDL1)	1987	PODS	0.00015414126
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
1,916	A Transaction Language Complete for Database Update and Specification	1987	PODS	0.00010101977
2,800	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	8.1019352e-05
5,102	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS	5.6992154e-05
5,238	On The Expressive Power Of The Extended Relational Algebra For The Unnormalized Relational Model	1987	PODS	5.6109061e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,773	Formal Semantics and Analysis of Object Queries	2003	SIGMOD	4.655071e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
9,280	A Theory of Regular Queries	2016	PODS	4.3636639e-05
6,664	Typed Query Languages for Databases Containing Queries	1998	PODS	4.9699875e-05
2,398	Containment and Minimization of Positive Conjunctive Queries in OODB's (Extended Abstract)	1992	PODS	8.8973978e-05
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
3,189	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4116834e-05
12,847	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1945683e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207