<p>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.</p>

CC BY-SA 3.0
2011-07-22T02:12:51.547Z
2011-07-22T02:12:51.547Z
tjgreen
<p>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.</p>

CC BY-SA 3.0
2011-06-09T10:00:38.803Z
could you give a paper related to your answer?
zfm
CC BY-SA 3.0
2011-06-09T13:38:22.700Z
The example with the automata is from [On the Equivalence of Recursive and Nonrecursive Datalog Programs](http://www.cs.rice.edu/~vardi/papers/pods92rj.pdf) 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
CC BY-SA 3.0
2011-06-09T06:12:10.603Z
2011-06-10T10:16:03.200Z
2011-06-10T10:16:03.200Z
ian
<p>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.</p>

<p>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}$).</p>

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

<p>For more information, see</p>

<p>V. Dalmau. <em>Linear Datalog and Bounded Path Duality of Relational Structures</em>. Available at Logical Methods in Computer Science (<a href="http://www.lmcs-online.org/ojs/viewarticle.php?id=30&amp;layout=CoRR&amp;format=pdf">here</a>), 2005.</p>

<p>Another good survey paper with a section devoted to this would be</p>

<p>A. Bulatov, A. Krokhin, B. Larose. <em>Dualities for Constraint Satisfaction Problems</em>. Lecture Notes in Computer Science, Vol. 5250:93-124, 2008. <a href="http://www.dur.ac.uk/andrei.krokhin/papers/dualsurvey.pdf">Available here</a>.</p>

CC BY-SA 3.0
2011-06-09T18:31:19.643Z
2011-06-09T18:31:19.643Z
Robert Robere
<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2011-06-09T03:23:55.410Z
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
CC BY-SA 3.0
2011-06-09T10:00:05.043Z
@Rob: [link](http://math.stackexchange.com/questions/44237/why-is-linear-datalog-interesting). I believed there's something about the complexity there, but I have no idea where I should find it...
zfm
<lo.logic><terminology><db.databases>
why is Linear Datalog interesting?
zfm
# why is Linear Datalog interesting?

(Asked by: username_0 on 2011-06-09)

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.

**Tags:** lo.logic, terminology, db.databases
> **Comments:**
> **username_1**: 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?  
> **username_0**: @Rob: [link](http://math.stackexchange.com/questions/44237/why-is-linear-datalog-interesting). I believed there's something about the complexity there, but I have no idea where I should find it...  

---

## 3 answers

### Answer by username_4 on 2011-06-09. Score: 12 | Accepted answer

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](http://www.lmcs-online.org/ojs/viewarticle.php?id=30&layout=CoRR&format=pdf)), 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](http://www.dur.ac.uk/andrei.krokhin/papers/dualsurvey.pdf).


---

### Answer by username_2 on 2011-07-22. Score: 2

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.


---

### Answer by username_3 on 2011-06-09. Score: 1

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.

> **Comments:**
> **username_0**: could you give a paper related to your answer?  
> **username_3**: The example with the automata is from [On the Equivalence of Recursive and Nonrecursive Datalog Programs](http://www.cs.rice.edu/~vardi/papers/pods92rj.pdf) 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.  

---

