Database systems are constantly extending their application area towards more general computing. However, applications that combine database access and general computing still suffer from the conceptual and technical gap between relational algebra and procedural programming. In this paper, we show that procedural programs may be effectively represented in a Datalog-like language with functions and aggregates. Such a language may then be used as a common representation for both relational and procedural part of an application.
embedded-SQL procedural program parser database statistics physical operator metadata library compile time run time physical operator code library
The procedural part meets with its relational elements only at run time – the procedural machine executes the procedural code containing calls to a database interface which in turn invokes the plan interpreter. The interpreter schedules and dispatches calls to procedures implementing individual physical operators of a plan. Although the individual SQL statements extracted from the source program often access the same data, their plans usually interact only at the lowest levels of physical data access; thus, they often repeat the same operations on the same data. bytecode generator relational algebra query rewriting plan generator
The most important reason for the separation of 1.2 Architecture procedural and relational parts is probably the history – the relational (SQL) query engines were usu- The architecture of the proposed system is shown at ally implemented well before the procedural add-on Fig. 2. Instead of separating the procedural and rewas considered and the software-engineering cost of lational part, the parser converts the source code into reimplementing the query engine was considered too a Datalog-like intermediate representation. This interhigh. mediate language and the conversion of procedural
Nevertheless, there is another reason for the sep- code into it form the main subject of this paper. On aration – the nature of procedural code is so distant the other hand, conversion of relational queries to from the algebraic nature of SQL that it is very dif- Datalog is a well-known subject; thus, it is not necesficult to create a meaningful common representation sary to describe the handling of embedded SQL statefor the two parts. ments.
The processing continues with rewriting step which
1.1 Goals optimizes the Datalog-like representation – this phase
corresponds to query rewriting and it may also be
inIn this paper, we suggest using a Datalog-like language fluenced by database statistics. Moreover, several
opas the common intermediate representation for proce- timization algorithms known from compiler
construcdural and relational code. This idea is natural, consid- tion like loop unrolling or variable renaming [
However, there are still many obstacles in the inte- The most important feature of this architecture is gration effort. In particular, there is a risk of loss of the ability to apply rewriting optimization step across efficiency since the procedural code is not evaluated the boundary between procedural and relational code. directly but transformed to logic-programming repre- For instance, repeated invocations of a SQL statement sentation and then evaluated by a procedural hard- may be glued together, offering, for instance, the posware. sibility to cache their partial results.
In our approach, we strive to improve the efficiency The plan generator phase tries to cover the Dataof logic-programming representation by minimizing log-like representation using a predefined set of patthe size of the models – we show that a procedural code terns. Each pattern corresponds to a component which can be encoded in a logic program in such a manner has several inputs and several outputs, each correthat the size of the (minimal) model is proportional sponding to a predicate. A simplest component cover to the execution time of the original program on the one Datalog rule – in this case, the head of the rule same data. Thanks to this proportionality, the logic corresponds to the output and each atom of the body program may be evaluated completely in bottom-up corresponds to an input of the component. More somanner. phisticated components correspond to a pattern cov
Due to the focus on bottom-up evaluation, we pre- ering more than one rule, including recursively depenfer calling our approach Datalog-like over the term dent rules. logic programming, although we certainly must use Some of the components correspond to physical a language stronger than Datalog to achieve gener- operators of a relational engine; for instance, a Dataality. log rule with two body atoms may be implemented
Besides function symbols which are necessary to by a hash-join operator. Other components are implesimulate general procedural programming, our langua- mented with simple procedural code snippets – these ge needs negation and aggregation for the emulation components ensure that the procedural parts of the of both procedural constructs and the embedded re- source code are reverted back to procedural code. Of lational language. Both negation and aggregation re- course, parts of the source code may be changed during quire special handling to ensure well-defined semantics the rewriting phase; consequently, procedural source and there are several approaches to the semantics of code may be eventually covered by relational operators negation in Datalog and logic programming in general. and, conversely, portions of the embedded relational
Thus, defining a particular approach to semantics statements may be converted to procedural snippets.
is a part of our effort – we reuse the concepts of lo- The implementation of physical relational
operacal stratification [
This paper deals with the design of the intermedi- Interaction of procedural and relational code was
reate representation and the translation from procedu- cognized as an important topic a long time ago;
neverral code to it. The subsequent steps – Datalog-based theless, practical applications of the results are very
rewriting and plan generator – are subject of our cur- scarce. In [
Nested relational algebra [
to express while loops. While loops may be added as parser an additional second-order construct atop of relational
algebra, or represented by transitive closure in
powerDatalog-like set algebra [
Flattening nested relations is an important step copsmhnypipsopicneaetlnt rDeawtraitliongg dsatatatibstaicsse taflolaswtotaeprndriesnsgeeffnpetrciitnnivcteipheleevcadoluersaectorioifbnoeuodrf inaneps[p1tre6od]awachlag.seTbdrheaesiagonnrdiegdiitntaiosl library physical flatten an isolated nested-relational algebra expression plan generator cmometpaodnaetant and it was based on the finite height of the expression gbeynteecroadtoer library tree. Since a while loop may generate a calculation of unlimited length, this flattening technique may not bytecode cormupnilteimtieme comtpreoenent tboe uaspeplaiednufmorbperrioncgedtuercahlnpiqruoegr(asmees. SIencs.te3a.d4,) wanedhatdo solve some unwanted consequences of the numbering JIT compiler pmroaccehdiunreal csocmhepdounleenrt appDroaatcahlo.g and its extensions, besides their natural physical applications in many areas of database theory, was component access data already successfully used in areas related to procedural licboradrey interface base programming.
A language derived from logical programming was
designed for programming in distributed
environFig. 2. Proposed processing path of embedded-SQL pro- ment [
The rest of the paper is organized as follows: In the the first decades of its life and it may experience a
reSection 2, we briefly review the related work on the vival fueled by the renewed interest in non-traditional
interaction between procedural and relational code as database architectures.
well as Datalog-related definitions important for our There were attempts to improve the expressive
poapproach. The following section uses a sample pro- wer of Datalog towards procedural programming by
cedural code to illustrate several approaches to the non-traditional extensions of its semantics [
Datalog with temporal features was used to model relational algebra can be simulated with plain
relasequences of data-manipulation statements [
Among the sheer number of approaches to Datalog operations like equality test over sets and it is
diffiextensions, semantics and evaluation strategies, local cult to reduce it to implementable physical operators.
and, in particular, temporal stratification [
3.1
state(M ′, S′) ← state(M, S), stmt3(X, M ), stmt4(S′, S, X), stmt5(M ′, M, X).
embedded SQL statements Require: Relation M(A, B) 1: S := z 2: while exists(M) do 3: X := select min(A) from M where A not in (select B from M) 4: S := f(S, X) 5: delete from M where A = X 6: end while 7: return S
ment the behavior of the statements 3, 4, and 5 of Algorithm 1. This approach creates extremely inefficient representation because any model of this program contains ground atoms for stmt3, stmt4, and stmt5 representing all satisfiable variable assignments for the statements regardless of its reachability during an execution. In addition, statement clauses (not shown here) violate safety rules as some of the variables are bound only by functional symbols. Conse
Algorithm 1 is an example of code written in a pro- quently, this approach is not suitable for bottom-up
cedural language with SQL embedded. It consumes evaluation in Datalog style.
a relation M with schema (A, B) representing edges
of a directed graph and traverses it in a topological
ordering. In the loop, a node X is selected that has 3.2 Using function symbols for relational
no incoming edge in M . The min aggregate is neces- algebra
sary to select from multiple candidates. Later in the
loop, all outgoing edges of X are removed from M . The following, improved representation may be
deThe output of the loop is the variable S which aggre- rived from the previous one using the Magic-sets
transgates the selected values of X using the constant z formation [
Modeling of a while-loop requires an extension to state5(M, S′, X) ← state4(M, S, X), S′ = f (S, X). relational algebra and transitive closure is the most state6(M ′, S) ← state5(M, S, X), obvious candidate. Each iteration of the loop changes M ′ = M \ σA=X M. the state of the program – the variables M and S state7(S) ← state2(M, S), M = ∅. – thus, there is a relation B which models the loop- state7(S) ← state6(M, S), M = ∅. body behavior using tuples hM, S, M ′, S′i. Together The predicate statei indicate the reachability of with the while-head condition H, the transitive clo- a particular variable assignment in the beginning of sure L = σM′=∅(σM6=∅B)∗ models the loop. Unfortu- statement i of Algorithm 1. The relational statements nately, it requires nested relational algebra to repre- are represented as equality statements containing sent the relation-valued attribute M ; although nested function symbols from relational algebra. The rules implement a state machine simulating the execution of the original program; the model expansion and safety problems mentioned above disappeared.
The relational statements are implemented using a non-Datalog mechanism; thus, this approach is far from being a suitable intermediate representation for mixed code. 3.3
Datalog level using the unnest predicate and the nest
aggregate. This approach is equivalent to nested
relational algebra. The predicate unnest(M, A, B)
performs the membership test hA, Bi ∈ M ; the
generalized aggregate nest(A, B) collects all hA, Bi pairs and
combine them into a set (see [
unnest(M, A, B), ¬cond3(M, A). state5(M, S′, X ) ← state4(M, S, X ), S′ = f (S, X ). state6(nest(A, B), S) ← state5(M, S, X ),
unnest(M, A, B), A 6= X. state7(S) ← state2(M, S), ¬cond2(M ). state7(S) ← state6(M, S), ¬cond2(M ).
This approach unifies the means used for procedural and relational fragments. Nevertheless, it suffers from the stratification required by the nest aggregate and the need to incorporate all live variables into single statei atom. 3.4
The following code illustrates the approach we finally used. The argument T representing time (more exactly, the number of iteration) was introduced to almost all rules. It allowed dissolution of the original statei predicates: statei(T ) indicates reachability of the statement i at time T .
m2(1, A, B) ← m0(A, B). s2(1, z). state2(1). state2(T + 1) ← branch23(T ). cond2(T ) ← state2(T ), m2(T , A, B). branch23(T ) ← state2(T ), cond2(T ). cond3(T , B) ← branch23(T ), m2(T , A, B). x4(T , min(A)) ← branch23(T ), m2(T , A, B), ¬cond3(T , A). s2(T + 1, f (S, X )) ← branch23(T ),
s2(T , S), x4(T , X ). m2(T + 1, A, B) ← branch23(T ),
m2(T , A, B), x4(T , X ), A 6= X. branch27(T ) ← state2(T ), ¬cond2(T ). return(S) ← branch27(T ), s2(T , S).
xi(T , V ) determines the value V of the variable X before entering statement i at time T . In the case of relational-valued variable M , the relation is unnested and its tuples are represented by individual instances of the atom mi(T , A, B).
Relational (and in general, complex-valued) Datalog variables and terms are no longer needed – every term is an atomic value.
Note that the dissolution of statei predicates created an opportunity for optimization: Every atomic statement modifies only one variable; therefore, only one clause is required for each statement, specifying the new variable value. For a variable, it is sufficient to have the value specified only at reference points (for S and M , it is the beginning of the statement 2), provided that at least one reference point lies on any path from any definition to any usage of this variable. In our case, the value for the reference point 2 is specified twice because there are two control paths leading to this point.
The execution of rules implementing statements is guarded by trigger predicates branchi,j which signalize passing from the statement i to the statement j. These predicates are controlled by conditions and their negations; in our case, the predicate cond2. 3.5
In our example Algorithm 1, there is a loop-carried dependence from the variable M through X to the next M value which involves negation and aggregation. This is reflected in the presence of negation and aggregation in the mutual recursion between the predicates x4 and s2. Our representation is therefore unstratifiable; the unstratifiability is inherent to Algorithm 1 since the length of the chain of negations generated by the loop is unlimited. Consequently, no stratification may exist for any Datalog-like representation of this example.
This forces us to use the concept of local
stratification. Note that in pure Datalog without function
symbols, local stratification is almost equivalent to
stratification [
In our example Algorithm 1, each iteration of the loop modifies each variable. However, a loop body may contain conditional statements; thus, a variable may become unmodified in some iterations. In this case, there must be a mechanism to pass the unmmodified variable value through the loop body. A simple implementation of such mechanism is the following clause: valueV (T + 1, X ) ← valueV (T , X ), cond(T ).
For every scalar variable V and for every iteration T , a ground atom valueV (T , X ) is present in the model indicating the value X of the variable. Consequently, the model is of the size Ω(τ υ) where τ is the execution time of the procedural program and υ is the number of variables in the program. For nonscalar variables the cost is even larger, because the argument X (or more arguments) encodes an individual element of a relation or an array, therefore there are as many ground atoms as the size of the variable. Evaluating the complete model is thus unacceptably costly.
Fortunately, the cost of unmodified variable passing may be lowered to O(τ log(υ)). The principle is depicted in Fig. 3 – instead of copying the variable value on every iteration, there are several layers of preferred points in time and copying is performed at these preferred points. Preferred points of layer k occur at the distance of 2k iterations and copying is allowed either to a point of higher preference or to a point of access to the variable. The thick lines in Fig. 3 show how a variable is passed when it is accessed in the three points marked at the time axis.
The number of copies done between two accesses is O(logΔ) where Δ is the time distance between the accesses, i.e. the length of the passing range. Since an atomic statement may access only a limited number of variables, the number n of passing ranges is proportional to the execution time, i.e. n = c ∗ τ . Since the ranges may not intersect for the same variable, their sum across of all variables is Pin=1 Δi ≤ τ υ. Consequently, the total cost of copying is proportional to Xn log(Δi) ≤ n log Pin=1 Δi ≤ n log( τ υ i=1 n n ) = τ c log υ c 4
cedural and relational code whose key element is a novel intermediate representation based on logic programming. With respect to the assumed bottom-up evaluation strategy, the intermediate language falls to the Datalog family. Special care was taken for effective evaluation of the intermediate language – our results show only O(log υ) degradation with respect to the native procedural evaluation of a code with υ variables.
In this paper, we presented the principles of the proposed language and its use for the representation of procedural code. For the sake of clarity, we omitted many technical details and tricks that were necessary to achieve the reported effectiveness of the representation.
Whether our approach is viable, it can be shown only by successful implementation of the whole processing chain from Fig. 2. The design of the intermediate representation was only a necessary prerequisite before attempting the implementation.
Our approach was motivated by the lessons learned
from the implementation of a parallel SPARQL
engine [
Thus, using a combined relational/procedural intermediate language may save the tedious and errorprone work associated with reformulating such algorithms in either purely relational (if ever possible) or purely procedural way. In addition, the mixed representation offers new opportunities for optimization.
If successful, the new architecture may become important for areas where database access is tightly coupled with non-trivial computing, including the Semantic Web, computational linguistics or some areas of e-science.