Horn Clauses and the Fixpoint Query Hierarchy

Summary: Horn-clause logic programs exactly capture YE+ — queries obtained by applying a fixpoint to positive-existential formulas — hence they are not generally first-order nor do they subsume all FO queries. With a proposed negation semantics, clausal queries = FP, i.e., FO closed under fixpoints and negation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 621
Venue: PODS
Year: 1982
Pagerank: 0.00013402577
Overall Rank: 888 | 93.91%
DOI: 10.1145/588111.588137

Incoming Non-self Citations Over Time

Authors

1. Ashok K. Chandra (IBM)
2. David Harel (Weizmann Institute of Science)

BibTeX Citation

@inproceedings{chandra_pods82,
        address = {New York, NY, USA},
        series = {{PODS} '82},
        title = {{Horn Clauses and the Fixpoint Query Hierarchy}},
        url = {https://dl.acm.org/doi/10.1145/588111.588137},
        doi = {10.1145/588111.588137},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chandra, Ashok K. and Harel, David},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
1,864	The Expressiveness of a Family of Finite Set Languages	1991	PODS	9.5928463e-05
1,980	Data Constructors: On the Integration of Rules and Relations	1985	VLDB	9.3613411e-05
2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.2516006e-05
2,897	On the Expressive Power of Database Queries with Intermediate Types	1988	PODS	7.9790527e-05
3,512	Query Processing in Deductive Databases with Incomplete Information	1986	SIGMOD	7.355113e-05
4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.5930956e-05
9,981	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB	5.1845938e-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	4,235	Relational Specifications of Infinite Query Answers	1989	SIGMOD
2	13,167	Computing Facts in Non-Horn Deductive Systems	1988	VLDB
3	5,210	On the Expressive Power of Logic Programming Languages with Sets	1988	PODS
4	5,964	Negation and Minimality in Non-Horn Databases	1993	PODS
5	2,474	Logic Programming as Constructivism: A Formalization and its Application to Databases	1989	PODS
6	4,831	Stable Models and Non-Determinism in Logic Programs with Negation	1990	PODS
7	4,072	Towards a Real Horn Clause Language	1988	VLDB
8	8,566	Negation as Failure for First-Order Queries (Extended Abstract)	1986	PODS
9	1,297	The Alternating Fixpoint of Logic Programs with Negation (Extended Abstract)	1989	PODS
10	174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS