Safety and Correct Translation of Relational Calculus Formulas

Summary: Simplifies definitions and proofs for the evaluable and allowed decidable subclasses of domain-independent relational calculus, with treatment of equality. Introduces a relational-algebra normal form and Dom-free transforms evaluable→allowed→RANF for correct translations, arguing evaluable may be the largest efficiently recognizable decidable subclass. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 805
Venue: PODS
Year: 1987
Pagerank: 7.1668598e-05
Overall Rank: 3,730 | 74.42%
DOI: 10.1145/28659.28693

Incoming Non-self Citations Over Time

Authors

1. Allen Van Gelder (Stanford University)
2. Rodney W. Topor (University of Melbourne)

BibTeX Citation

@inproceedings{gelder_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{Safety and Correct Translation of Relational Calculus Formulas}},
        url = {https://dl.acm.org/doi/10.1145/28659.28693},
        doi = {10.1145/28659.28693},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Van Gelder, Allen and Topor, Rodney W.},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,314	Independence of Logic Database Queries and Updates	1990	PODS	0.00011182427
2,474	Logic Programming as Constructivism: A Formalization and its Application to Databases	1989	PODS	8.5305658e-05
3,355	A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract)	1988	SIGMOD	7.4912272e-05
6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.9870797e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS
2	8,970	Understanding Queries by Conditional Instances	2022	SIGMOD
3	174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS
4	13,055	Interpreting a Reconstructed Relational Calculus: Extended Abstract	1993	SIGMOD
5	6,072	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
6	4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB
7	6,286	Finite Queries do not Have Effective Syntax	1995	PODS
8	4,226	Safe Constraint Queries	1998	PODS
9	6,155	Safety and Translation of Calculus Queries with Scalar Functions (Extended Abstract)	1993	PODS
10	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS