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
1020
Venue
PODS
Year
1994
Pagerank
5.0723324e-05
Overall Rank
13,073 | 10.62%
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
64 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038625198
176 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00027121017
958 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS 0.00012944899
1,656 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.0001006652
1,792 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.7249022e-05
3,814 On the Expressive Power of Datalog: Tools and a Case Study 1990 PODS 7.0833338e-05
6,273 On Datalog vs. Polynomial Time 1991 PODS 5.9177212e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,130 Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] 2006 PODS
2 7,239 Containment of Graph Queries Modulo Schema 2024 PODS
3 4,250 Relational Specifications of Infinite Query Answers 1989 SIGMOD
4 14,474 Expressibility of Bounded-Arity Fixed-Point Query Hierarchies 1989 PODS
5 10,190 Size Bound-Adorned Datalog 2026 PODS
6 6,958 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS
7 1,634 On the Decidability of Query Containment under Constraints 1998 PODS
8 6,641 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS
9 4,628 Tools for Datalog Boundedness 1991 PODS
10 8,012 On the First-Order Expressibility of Recursive Queries 1989 PODS