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: 1003
Venue: PODS
Year: 1993
Pagerank: 6.8701678e-05
Overall Rank: 4,152 | 71.52%
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
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105
2,241	Finitely Representable Databases	1994	PODS	8.8845324e-05
5,523	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	6.1870017e-05
12,974	On Genericity and Parametricity	1996	PODS	5.093636e-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,525	Data Path Queries over Embedded Graph Databases	2022	PODS
2	312	A Graphical Query Language Supporting Recursion	1987	SIGMOD
3	1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS
4	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	6,286	Finite Queries do not Have Effective Syntax	1995	PODS
6	5,617	Relative Information Completeness	2009	PODS
7	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
8	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
9	12,404	Completeness of Queries over Incomplete Databases	2011	VLDB
10	1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS