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.1382653e-05
Overall Rank: 9,695 | 34.84%
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,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
3,021	Graph-Theoretic Methods In Database Theory	1990	PODS	7.741152e-05
7,090	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.5994281e-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.00058997063
353	On the Power of Magic	1987	PODS	0.00020213935
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018219394
2,067	One-Sided Recursions	1987	PODS	9.0898007e-05
4,427	Magic Counting Methods	1987	SIGMOD	6.6008592e-05
4,483	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5780787e-05
4,770	Handling Redundancy in the Processing of Recursive Database Queries	1987	SIGMOD	6.4225302e-05
5,423	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS	6.1347456e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,875	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,439	Magic is Relevant	1990	SIGMOD
4	7,281	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
5	7,090	On the Expected Size of Recursive Datalog Queries	1991	PODS
6	1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
7	5,423	Worst-case Complexity Analysis of Methods for Logic Query Implementation	1987	PODS
8	3,715	Compiling Separable Recursions	1988	SIGMOD
9	440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
10	4,427	Magic Counting Methods	1987	SIGMOD