Recent work has shown how to use non-recursive Datalog as a programming language for view update strategies in relational databases. In this paper, we extend the idea by considering recursions in the Datalog language for more interesting view definitions (forward transformation) and update strategies (backward transformation), especially over relations that store complex data structures such as trees and graphs. Firstly, we present how recursive bidirectional transformations over such relations can be formulated in Datalog and encapsulated in high-order logic predicates. Secondly, we discuss the validation problem for well-behavedness of the recursive Datalog programs.
Recent work [
Datalog without recursion is a suitable and friendly language for implementing data transformations in relational database management systems where views are commonly defined in relational algebra without recursion. However, in deductive databases where relations are used to represent more complex data such as graphs or tree-like data structures, recursion in Datalog plays a central role.
In this paper, we extend the idea proposed in [
Manually writing a recursive view update strategy is an expensive task for programmers and it is even more challenging to automatically validate such a program. The fixed-point semantics
11 12 me Age a
N 13 14 liceA 24 Nil Nil 2 C
3 B o b Nil 4 3 2 Nil 6 5 me Age a N J o h n 7 1 0 Nil Nil edge parent_id 1 2 3 . . .
Employee Manager 1
e8 Ag am e N 9 10 M a r y Nil 2 6 Nil label
Bob . . .
id 2 3 Nil . . . <Employees> <Employee> <Name> Bob </Name> <Age> 32 </Age> <Child> <Name> John </Name> <Age> 10 </Age> </Child> </Employee> <Employee> <Name> Mary </Name> <Age> 26 </Age> </Employee> <Manager> <Expert> <Name> Alice </Name> <Age> 42 </Age> </Expert> </Manager> </Employees> of Datalog makes the well-behavedness property not expressible in first-order logic.
Our key idea to solve the aforementioned challenge is to formulate a Datalog-written view
update strategy into two parts: one for recursive patterns and another for inner update strategies.
On the one hand, the recursive Datalog rules of the first part are predefined and pre-validated
so that their well-behavedness is guaranteed. On the other hand, we allow programmers to
manually write the inner update strategies in Datalog without recursion, which can be validated
automatically. To combine these non-recursive rules with the predefined recursive ones, we
extend Datalog with high-order predicates as in HiLog [
2.1. Shredding tree-structured data into relations
For tree-structured data such as XML or JSON documents, we use the Edge shredding approach
[
Prolog without functions. The recursion in Datalog makes it a suitable language for queries over the edge relation since recursive computation is required for tree traversals. Example 2.1. The following recursive Datalog rules extract from the tree in Figure 1 the subtree (the left subtree, stored in relation subedge) that contains only employees: ( r1 ) ( r2 ) subedge(X, L, Y) :− edge(X, L, Y) , L = ‘ Employee’, ¬ edge(_, _, X) .
subedge(X, L, Y) :− subedge(_, _ , X) , edge(X, L, Y) .
Each Datalog rule represents a first-order logic sentence where the conjunction of all predicates
in the rule body (right-hand side) implies the predicate in the rule head (left-hand side), and all
variables are universally quantified [
The forward direction works as follows. To split the original tree, we use two recursive Datalog rules in Example 2.1 to extract the left subtree subedge (the tree of nodes 1 to 10). Then the right subtree subedge, which is the remaining part, is the one that has all the edges in edge but not in subedge and is computed by a rule in Line 4. Line 6 calculates a view as an identity instance of subedge. Line 7 calculates a view by excluding the edge from the root of subedge. In this rule, the second predicate of the body makes sure that node X has a parent node, i.e., node X is not the root. Lines 9 and 10 merge the two views into one edge by taking the union. If the root nodes of these views have diferent IDs, we write an additional rule to unify them.
In the backward direction, we have similar operations. Lines 12, 13, and 14 split the view edge. Line 16 calculates the first new source subedge for subedge as the same instance. Lines 17 and 18 compute the second new source subedge by taking all the edges of the view subedge and the outgoing edge from the root in the original source subedge. Predicate ¬subedge(_,_,X) in Line 18 is to ensure that node X has no parent node, i.e., X is the root. Lines 20 and 21 merge the two new sources.
The forward and backward transformations in Figure 2 can be considered as program templates for writing more bidirectional transformations over the tree. The Datalog rules of splitting and merging operations can be adjusted by changing the constant ‘Employee’ to another label. The two inner bidirectional transformations (Rules 6, 7, 16, 17, and 18) can be arbitrarily implemented. Since the splitting and merging operations are fixed, the well-behavedness of the program templates is guaranteed if the two inner bidirectional transformations are well-behaved.
Our observation is that an inner bidirectional transformation works on a component that is structurally smaller than the original tree, and thus is easier to manually implement. Meanwhile, writing decomposing operations, e.g., splitting, requires more knowledge about recursion. This suggests a new approach to make bidirectional transformations over tree-structured data programmable in Datalog. The key idea is to predefine a variety of program templates that employ the recursive computation power of Datalog to work on recursive data structures like trees. Programmers can reuse these templates by manually implementing inner bidirectional transformations without recursion.
Our example shows a typical program over a recursive data structure with three operations:
decomposing (splitting) the tree, then processing each component, and merging the results. By
recursively decomposing all components, we obtain structural recursions over the tree. In our
program templates, we predefine recursive Datalog rules to deal with these recursion forms.
We consider only a fixed number of commonly used recursive patterns that always terminate
and are suficiently expressive in practice. To enhance the reusability of program templates, we
shall encapsulate Datalog rules in high-order predicates that can be easily recalled.
2.3. Encapsulating Datalog rules in high-order predicates
We can consider subedge and subedge of the splitting operations (Rules 2, 3, and 4 in Figure 1)
as a pair resulting from a split function over a relation edge and a constant ‘Employee’.
The pair can be represented by a function {‘l’ ↦→ subedge, ‘r’ ↦→ subedge}. Therefore,
we have: subedge = split(edge,‘Employee’)(‘l’) and subedge = split(edge,
‘Employee’)(‘r’). Rules 2, 3, and 4 can be parameterized with src and Label as follows:
split ( src , Label ) ( ‘ l ’ ) (X, L, Y) :− src (X, L, Y) , L = Label , ¬ src(_, _ , X).
split ( src , Label ) ( ‘ l ’ ) (X, L, Y) :− split ( src , Label ) ( ‘ l ’ ) (_ , _ , X), src (X, L, Y) .
split ( src , Label ) ( ‘ r ’ ) (X, L, Y) :− src (X, L, Y) , ¬ split( src , Label ) ( ‘ l ’ ) (X, L, Y) .
Where split can be considered as a high-order logic predicate as in the HiLog syntax [
Similarly, we can have a predicate merge for the merging operation. By encapsulating the two inner backward transformations in two predicates put1 and put2, the whole backward transformation can also be encapsulated in a single predicate: fork(put1, put2, Label)(src, view)(X, L, Y) :− merge( put1(split ( src , Label ) ( ‘ l ’ ) , split (view, Label ) ( ‘ l ’ ) ) , put2(split ( src , Label ) ( ‘ r ’ ) , split (view, Label ) ( ‘ r ’ ) ) ) (X, L, Y) .
More interestingly, the corresponding forward transformations 1, 2, and can be
uniquely determined from their backward transformations 1, 2, and , respectively
[
As presented in Section 2, a Datalog program template consists of predefined Datalog rules and user-written rules. Validating the well-behavedness of bidirectional transformations specified by these rules plays a central role in our approach. While the predefined part can be pre-validated, an automated validator is required for statically checking the inner bidirectional transformation programs, which are arbitrarily written.
Although many properties of Datalog rules can be reduced to the satisfiability of Datalog
queries, it is well known that the satisfiability problem of a Datalog query is undecidable [
Recursive Datalog rules in program templates are predefined to deal with common forms of structural recursion rather than arbitrary recursions. Therefore, to validate a property of these recursive rules, we can apply structural induction on the data structure to construct a proof for the property. The main challenge to applying structural induction is that the data structure is not explicitly described by an inductive type but shredded into an edge relation. The structure is preserved by constraints on the edge relation, e.g., primary/foreign keys on id and so forth.
We have presented our ideas to use Datalog as a programming language for bidirectional transformations over tree-structured data. Although this short paper has demonstrated a simple example, we believe Datalog is expressive enough to cover many interesting recursive view update strategies over trees and even some restricted graphs.