For those doesn't know about linear datalog, linear datalog is a datalog rule in which the number of IDB predicate in each rule is less or equal than one.

My question is, why is this interesting? What differ this with the "normal" datalog program?

NB: I put this question also in math.stackexchange. According to my experience, I am afraid that this question shouldn't be in this site, but I don't see any reason why I should put deductive database question in math section.

• My memory suggests that linear Datalog has certain (potentially desirable) complexity properties relative to full Datalog, however, I don't remember where I got that from. Also: can you link to the crosspost in math.stackexchange? – Rob Simmons Jun 9 '11 at 3:23
• @Rob: link. I believed there's something about the complexity there, but I have no idea where I should find it... – zfm Jun 9 '11 at 10:00

Linear Datalog has a lot of connections with the complexity of constraint satisfaction and logic. Like @ian said, the intuitive way to view a linear Datalog program is a Datalog program who's proof trees are basically paths.

In constraint satisfaction, we are interested in problems of the following form. Let $\mathbf{B} = (B, R_1^{\mathbf{B}}, R_2^{\mathbf{B}}, \ldots, R_n^{\mathbf{B}})$ be a relational structure (that is, a domain $B$ with a family of relations over that domain). We ask, what relational structures $\mathbf{A} = (A, R_1^\mathbf{A}, R_2^\mathbf{A}, \ldots, R_n^\mathbf{A})$ admit a homomorphism to $\mathbf{B}$ (i.e. a function $f: A \rightarrow B$ such that if $(a_1, a_2, \ldots, a_n) \in R_i^{\mathbf{A}}$ then $(f(a_1), f(a_2), \ldots, f(a_n)) \in R_i^\mathbf{B}$)? We will denote this decision problem by CSP($\mathbf{B}$).

It turns out that the complexity of CSP($\mathbf{B}$) can be neatly characterized by linear Datalog. Namely, if co-CSP($\mathbf{B}$) can be expressed in linear Datalog, then CSP($\mathbf{B}$) is in $\mathsf{NL}$. This characterization of the expressibility of the complement problem in linear Datalog is equivalent to a number of different properties, such as $\mathbf{B}$ having bounded pathwidth duality, a winning strategy in a certain kind of pebble game, and expressibility in certain fragments of infinitary logic (logics extended with infinite conjunctions).