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: he1de6c0da71de64a
Venue: PODS
Year: 1988
Pagerank: 5.1406988e-05
Overall Rank: 9,689 | 34.86%
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,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.6020796e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
352	On the Power of Magic	1987	PODS	0.00020223279
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018227953
2,065	One-Sided Recursions	1987	PODS	9.0940924e-05
4,425	Magic Counting Methods	1987	SIGMOD	6.6039832e-05
4,479	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5811933e-05
4,768	Handling Redundancy in the Processing of Recursive Database Queries	1987	SIGMOD	6.4255719e-05
5,419	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.137651e-05

Semantically Similar Papers

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