Worst-case Complexity Analysis of Methods for Logic Query Implementation
Summary: Graph-based worst-case complexity analysis of three implementation methods (Eager, Counting, Magic Set) for canonical strongly linear (CSL) queries via a directed query-graph model with three arc types. Establishes Counting yields the best upper bound for non-cyclic queries and presents an extension of Counting to handle cyclic queries. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,474 | Graph-Theoretic Methods In Database Theory | 1990 | PODS | 8.7135761e-05 |
| 4,555 | Magic Counting Methods | 1987 | SIGMOD | 6.0891017e-05 |
| 6,365 | On the Expected Size of Recursive Datalog Queries | 1991 | PODS | 5.0945408e-05 |
| 7,156 | Counting Methods for Cyclic Relations | 1988 | PODS | 4.8145046e-05 |
| 12,984 | Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy | 1987 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 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.0010066783 |
| 77 | An Amateur's Introduction to Recursive Query Processing Strategies | 1986 | SIGMOD | 0.00057043861 |
| 296 | On the Implementation of a Simple Class of Logic Queries for Databases | 1986 | PODS | 0.00028644922 |
| 4,555 | Magic Counting Methods | 1987 | SIGMOD | 6.0891017e-05 |
Previous
Page 1 / 1
Next