DBScholar

Back to papers

Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)

Summary: Establishes lower bounds on the width (arity) of recursively defined predicates in Datalog(!=) even when the extensional DB is a single binary relation (graphs): there exist queries requiring arbitrarily large width. In particular, any fixed subgraph homeomorphism query needs width ≥ number of arcs in the pattern graph. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h9a5c599a58876382
Venue
PODS
Year
1994
Pagerank
4.9793485e-05
Overall Rank
13,310 | 10.52%
DOI
10.1145/182591.182603

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@inproceedings{afrati_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/182591.182603},
        doi = {10.1145/182591.182603},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Afrati, Foto N.},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank Cited Paper Year Venue Pagerank
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038009523
177 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.000266613
979 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012729663
1,682 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8850863e-05
1,830 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.5498891e-05
3,876 On the Expressive Power of Datalog: Tools and a Case Study 1990 PODS 6.9534856e-05
6,370 On Datalog vs. Polynomial Time 1991 PODS 5.8092399e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,266 Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] 2006 PODS
2 7,347 Containment of Graph Queries Modulo Schema 2024 PODS
3 14,734 Expressibility of Bounded-Arity Fixed-Point Query Hierarchies 1989 PODS
4 4,326 Relational Specifications of Infinite Query Answers 1989 SIGMOD
5 10,365 Size Bound-Adorned Datalog 2026 PODS
6 7,064 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS
7 1,660 On the Decidability of Query Containment under Constraints 1998 PODS
8 6,741 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS
9 4,712 Tools for Datalog Boundedness 1991 PODS
10 8,136 On the First-Order Expressibility of Recursive Queries 1989 PODS