Completeness Results for Recursive Data Bases

Summary: Completeness characterizations for computable (infinite recursive) relational databases: quantifier-free first-order logic is complete for the unrestricted class of computable databases. For “highly symmetric” databases (automorphism group of finite index at each tuple-width) a modified Chandra–Harel QL is complete; BP-completeness is also analyzed. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h31322172c6d73a0d
Venue: PODS
Year: 1993
Pagerank: 6.7129946e-05
Overall Rank: 4,230 | 71.58%
DOI: 10.1145/153850.153905

Incoming Non-self Citations Over Time

Authors

1. Tirza Hirst (Weizmann Institute of Science)
2. David Harel (Weizmann Institute of Science)

BibTeX Citation

@inproceedings{hirst_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Completeness Results for Recursive Data Bases}},
        url = {https://dl.acm.org/doi/10.1145/153850.153905},
        doi = {10.1145/153850.153905},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hirst, Tirza and Harel, David},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
915	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013097866
2,296	Finitely Representable Databases	1994	PODS	8.68133e-05
5,659	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	6.0453458e-05
13,270	On Genericity and Parametricity	1996	PODS	4.9769913e-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	11,840	Data Path Queries over Embedded Graph Databases	2022	PODS
2	305	A Graphical Query Language Supporting Recursion	1987	SIGMOD
3	1,921	The Expressiveness of a Family of Finite Set Languages	1991	PODS
4	4,428	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	6,412	Finite Queries do not Have Effective Syntax	1995	PODS
6	5,741	Relative Information Completeness	2009	PODS
7	8,142	On the First-Order Expressibility of Recursive Queries	1989	PODS
8	2,100	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
9	12,701	Completeness of Queries over Incomplete Databases	2011	VLDB
10	1,952	Relational Expressive Power of Constraint Query Languages	1996	PODS