This work is about performing automatic diferentiation of a query in the context of relational databases and queries. This is done in order to perform optimization through gradient descent in these relational databases. This work describes a form of automatic differentiation for a subset of relational queries.
Modern Diferentiable Programming applied to Deep Learning
concentrates on dense and regular problems such as images [
Many sub parts of languages have been diferentiated: Python [
ADSL
[
We introduce ADSL1, which is A Diferentiable Sub Language
that is intended to lower relational language. It is a simple language
where Automatic Diferentiation is a first class citizen. This idea
is similar to [
According to the definition below, an ADSL program is a list of Statements < >, whose grammar is defined by: Ψ Ξ)⟩ Φ)⟩ ⟨ S ⟩ ⟨ e ⟩ ::= . | ⟨ v ← ⟩ | ⟨ Cond ( v | ⟨ For ( | ⟨ Return v ⟩ ::= . | ⟨ v ⟩ | ⟨ f ⟩ | ⟨ b ⟩ | ⟨ v + w ⟩ | ⟨ Call1 op v ⟩ | ⟨ Call2 op v w ⟩ | ⟨ Param i ⟩ | ⟨ Const i ⟩ | ⟨ v ⊳ ⟩ | ⟨ v ⊲ ⟩ | ⟨ Pred ⟩
⟨ Pred ⟩ ::= .
| ⟨ And v w ⟩ | ⟨ Or v w ⟩ | ⟨ Not v ⟩ | ⟨ v < w ⟩ | ⟨ v ≤ ⟩
ADSL is tight but it is enough to tackle many real business problems, such as those encountered in the supply chain. Its main characteristic is to be easily and fully diferentiable. Projectors 1Adsl library can be found at https://github.com/Lokad/Adsl R′ ( , →) × ( , →) × ′ In this section we describe our approach to derive relational query. This approach is based on compilation.
Let R be a relational query that creates the float column in the table . We assume that R involves a float column in the table . In optimization or Machine Learning, such an objective function is often called loss. stands for Observation Table and for Parameter Table. It is possible that = .
Our main goal is to minimize the scalar:
Diferentiating a relational query means that we want to create the column ′ in that is the derivative of . with respect to . . Doing so will unlock optimization through gradient-based methods. As it appears hard to diferentiate arbitrary query, we reduce our scope to a subset of queries that should be wide enough to cover many industrial cases. First we do not consider a query that involves a Common Table Expression: these have to be inlined in the query. It drastically helps query compilation to ADSL. Second . should appear once and only once.
Let be the set of tables used in R. Then { , } ⊂ .
Let’s introduce the relation" −→ " when the primary key of is a foreign key in . It is said that broadcasts into .
Here is a simple way to create such and in SQL:
SELECT f o r e i g n K e y AS p r i m a r y K e y FROM TB
GROUP BY f o r e i g n K e y ( , −→) naturally forms a graph. Then we can compile the query R to the pair ( , −→) × where is an ADSL program. Evaluation of ( , −→) × gives ..
As is an ADSL program it is possible to diferentiate it with respect to the input associated to . as ′.
We state that with
R ′ = ( , −→) × ′ evaluation of R ′ gives the expected . ′, which is represented in Figure 1.
We believe that this schema is a good way to diferentiate relational queries: if the output is a relational query then we can use all the optimizations and parallelizations developed for regular ones. 4
In this section we introduce notations on graphs that will be applied to the SQL Table tree in order to simplify it and facilitate its compilation to ADSL.
Definition 4.1 (Polytree). A Polytree is a directed acyclic graph whose underlying undirected graph is a tree.
For example, any tree structure of a website is a Polytree.
Definition 4.2 (Cross Edge). A cross-edge is a pair of edges in a graph ( −→ , −→ ) which indicates that comes from a cross operation between and .
Here is a simple way to create such an edge in SQL:
Let be a Polytree with cross-edges: ( , , (, )) Definition 4.3 (PolyStar). Let’s define a PolyStar ★ as ★ = { (, ) | a Polytree with cross-edges & n a node of } (1)
A PolyStar is a PolyTree with a special focus on a specific node of the graph.
Let (, ) ∈ ★. We call • an upstream node a node of such that −→ . • an upstream cross node a cross node of such that one of its parents is an upstream node. • an observation-cross a cross node of such that one of its parents is . • a downstream node a node of such that is not an observationcross node and that −→ .
• We call a full node the remaining nodes of .
By construction, there is no path between a full node and . 4.1
A relational query in SQL creates many tables, even though some could be grouped. For example,
creates another table with a bijection from its index to index. Thus we introduce a novel join operator that helps us to simplify the table tree: TOTAL JOIN. 1 TOTAL JOIN 2 ON ⟨ ⟩ is the same semantic as 1 INNER JOIN 2 ON ⟨ ⟩ with the additional constraint that for each line of 1, there is exactly one line of 2 that corresponds. To make a successful 1 TOTAL JOIN 2 ON ⟨ ⟩ it is suficient that columns are a primary key in 2 and a foreign key in 2, but it is not necessary.
Thanks to this join operator that is reminiscent of [
TOTAL JOIN 2 5 an aggregator). If a TOTAL JOIN is used then operations can be performed line by line thus we can compile it to a scalar operation such as +, Call1, Call2 . . .
Remark 2 (Sufficient condition). If the query is written without any Common Table Expression and involves . only once, then , ∈ ★ where are the used tables in R.
In this section we take a real case from the supply chain industry to illustrate our previous formalization.
Let’s consider that our database contains information on products that a company sells. It has the Product table recording the products. These products are organized by categories. The Orders table records products orders. Assuming that we also have a Week table whose primary is the week number, we would write:
SELECT c a t e g o r y FROM P r o d u c t GROUP BY c a t e g o r y
All these notations help us to compile the query as easily as possible. While computing a line of . ′ from ( , −→) × ′, an input coming from • the observation table gives a scalar • an upstream table gives a scalar • a full table gives a vector of the size of the full table itself. • an upstream-cross table gives a vector of the size of the left table used in the cross operation • a downstream table gives a vector of certain size.
In summary, we introduce the TOTAL JOIN operator to turn the SQL Table tree into a PolyStar. Once it is a PolyStar, its lowering, i.e. compilation, to ADSL is simplified.
We used the Chicago taxi rides dataset that can be found here 2.
We chose this dataset because it has also been used by [
For each ride, we use the taxi identifier, distance (in miles) and the tips (in dollar). In this example, the Observation table is the Trips table and the Taxis table is an upstream table:
SELECT t a x i I d , 1 AS a FROM T r i p s GROUP BY t a x i I d
We use linear regression to predict the tip based on the trip distance.
= × + It is an interesting example to perform a benchmark but according to us, it does not illustrate the relational aspect of the dataset. Thus we also used an augmented version of this model where the slope depends on the taxi identifier, the intercept remains shared among taxis:
taxiId = taxiId × +
This example illustrates how the relational information between the Trips table and the Taxis table has to be used. (2) (3) thus the derived query (with respect to the slope ) should be: SELECT
t r i p I d , t a x i I d ,
SELECT
∗ , 2 ∗ a ∗ ( E s t i m a t e d − T i p s ) AS G r a d i e n t , T a x i s . a ∗ T r i p s . d i s t a n c e +
AS E s t i m a t e d
WHERE T r i p s . t a x i I d = T a x i s . t a x i I d ) ; For the sake of notation, slopes are initialized at 1 and intercept at 0.
Such a model has a straight forward explanation; the model can
be white boxed. Taxi’s slope shows its ability to get tips. It is called
Interpretable ML [
In Table 1, Shared Slope is the implementation relative to
equation 2 and Taxi’s Slope is relative to equation 3. We’ve not
reproduced all experiments from [
In this work we’ve presented a concrete approach to perform
diferentiation on relational query. Our claim is that derived query should
also be a query. Thus we have introduced a dedicated programming
language ADSL that is closed by diferentiation. Thanks to the
introduced operator TOTAL JOIN and PolyStar, we can clarify the roles
of diferent tables in the relational query to diferentiate. Our
implementation allows us to eficiently tackle real world problems such
as those encountered in a supply chain, for example. We hope that
relational programming language will consider Automatic
Diferentiation as first class citizens in the future, this would strengthen
"Query 2.0" [
This work was supported by ANRT French program and Lokad.