Bounded Arity Datalog(≠) Queries on Graphs

摘要

We show that there are Datalog(≠) queries on graphs (i.e., the extensional database contains a single binary relation) that require recursively defined predicates of arbitrarily large width. More specifically, we prove that fixed subgraph homeomorphism queries require width of recursively defined predicates which is at least equal to the number of arcs in the pattern graph.