Counting Methods for Cyclic Relations

Summary: Handles counting-based evaluation for linear, two-rule Datalog selection queries (column=constant), overcoming failures of standard counting methods on cyclic databases. Presents a counting-style algorithm that reduces evaluation to intersections of semi-linear sets and constructs them efficiently, matching traditional counting methods' asymptotic runtime. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 843
Venue: PODS
Year: 1988
Pagerank: 5.2586367e-05
Overall Rank: 9,503 | 34.81%
DOI: 10.1145/308386.308469

Incoming Non-self Citations Over Time

Authors

1. Ramsey W. Haddad (Stanford University)
2. Jeffrey F. Naughton (Princeton University)

BibTeX Citation

@inproceedings{haddad_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{Counting Methods for Cyclic Relations}},
        url = {https://dl.acm.org/doi/10.1145/308386.308469},
        doi = {10.1145/308386.308469},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Haddad, Ramsey W. and Naughton, Jeffrey F.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
6,948	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.7306589e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
344	On the Power of Magic	1987	PODS	0.00020659405
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
4,337	Magic Counting Methods	1987	SIGMOD	6.7554367e-05
4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.7101609e-05
4,673	Handling Redundancy in the Processing of Recursive Database Queries	1987	SIGMOD	6.573022e-05
5,295	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.2784683e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,729	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB
2	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
3	1,410	Magic is Relevant	1990	SIGMOD
4	7,131	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
5	6,948	On the Expected Size of Recursive Datalog Queries	1991	PODS
6	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
7	5,295	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS
8	3,629	Compiling Separable Recursions	1988	SIGMOD
9	429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
10	4,337	Magic Counting Methods	1987	SIGMOD