why is Linear Datalog interesting?

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

3 Answers

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).

For more information, see

V. Dalmau. Linear Datalog and Bounded Path Duality of Relational Structures. Available at Logical Methods in Computer Science (here), 2005.

Another good survey paper with a section devoted to this would be

A. Bulatov, A. Krokhin, B. Larose. Dualities for Constraint Satisfaction Problems. Lecture Notes in Computer Science, Vol. 5250:93-124, 2008. Available here.

I think intuitively the main difference is that the proof trees of linear datalog programs are simply paths - hence the name. This often makes life easier (eg whenever you need tree automata for unconstrained datalog, you can use regular word automata for linear datalog). This might be more a comment than a answer.

• could you give a paper related to your answer? – zfm Jun 9 '11 at 10:00
• The example with the automata is from On the Equivalence of Recursive and Nonrecursive Datalog Programs by Surajit Chaudhuri and Moshe Vardi. It's more related to my answer than to your question, but maybe you find something useful in the references. – ian Jun 9 '11 at 13:38

Another answer (from the stackoverflow rather than cstheory perspective) is that it corresponds to what can be done using the SQL99 "with recursive" construct: i.e., it is the fragment of Datalog supported by commercial DBMS implementations.