Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
