QUERYING LOGICAL DATABASES: Preliminary Report

Summary: Analyzes complexity of query evaluation in Reiter's closed-world logical databases with unknown values, showing first-order queries become co-NP-complete (vs. LOGSPACE for physical DBs). Proposes an approximation algorithm to implement logical databases on top of standard DBMSs. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 719
Venue: PODS
Year: 1985
Pagerank: 5.093636e-05
Overall Rank: 13,207 | 9.39%
DOI: 10.1145/325405.325413

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Moshe Y. Vardi (Center for Study of Language and Information; Stanford University)

BibTeX Citation

@inproceedings{vardi_pods85,
        address = {New York, NY, USA},
        series = {{PODS} '85},
        title = {{QUERYING LOGICAL DATABASES: Preliminary Report}},
        url = {https://dl.acm.org/doi/10.1145/325405.325413},
        doi = {10.1145/325405.325413},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vardi, Moshe Y.},
        year = {1985}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
602	On the Semantics of Updates in Databases	1983	PODS	0.00015856828
613	Database Relations with Null Values (Extended Abstract)	1982	PODS	0.00015723523

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	414	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
2	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
3	2,500	Querying Database Knowledge	1990	SIGMOD
4	13,130	A Sound and Complete Query Evaluation Algorithm for Relational Databases with Disjunctive Information (Extended Abstract)	1989	PODS
5	50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB
6	2,110	Theory of Database Queries (Extended Abstract)	1988	PODS
7	14,462	On Analogical Query Processing in Logic Database	1986	VLDB
8	429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
9	544	A New Approach to Database Logic	1984	PODS
10	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS