Differentiating Relational Queries Paul Peseux supervised by M.Berar, T.Paquet & V.Nicollet Litis Normandie & Lokad Paris, France paul.peseux@lokad.com ABSTRACT 2 ADSL This work is about performing automatic differentiation of a query [8] [10] [2] [21] [. . . ] proposes to differentiate subsets of common in the context of relational databases and queries. This is done in programming languages. What these initiatives have in common order to perform optimization through gradient descent in these is the purpose of differentiating a pre-existing language. It is an relational databases. This work describes a form of automatic dif- interesting task, while being complicated, as those languages are ferentiation for a subset of relational queries. not crafted for differentiation. This is especially true for relational programming languages. We introduce ADSL1 , which is A Differentiable Sub Language that is intended to lower relational language. It is a simple language where Automatic Differentiation is a first class citizen. This idea is similar to [1] [9] [14]. ADSL is closed by differentiation: the 1 INTRODUCTION adjoint, i.e. the derived program, of an ADSL program is also a Modern Differentiable Programming applied to Deep Learning con- differentiable ADSL program. This closure gives immediate access centrates on dense and regular problems such as images [13] [12] to higher order derivatives, which are sometimes used [15] [5]. and sound [6], or studies ways to project unstructured problems ADSL is a simple SSA language that supports loops and conditional. into this framework [11] (e.g. auto-encoders for text data). Its suc- Its major specificity is its projectors and broadcasts support. cess is partly due to automatic differentiation [21]. Parallel to this According to the definition below, an ADSL program is a list of many business domains have a very well-defined structure, but this Statements < 𝑆 >, whose grammar is defined by: structure is relational. For example supply chain data is organized ⟨S⟩ ::= . in relational databases and experts are used to working with these. | ⟨ v ← π‘’βŸ© Variable assignment A canonical example coming from this domain: items in the prod- | ⟨ Cond ( v Ξ¨ 𝑃𝑇 𝑃𝐸 Ξ¦)⟩ Conditional uct table come from suppliers in the supplier table and are stored | ⟨ For ( πœ’ 𝑃 Ξ)⟩ Loop in warehouses in the warehouse table; the problem’s structure is | ⟨ Return v ⟩ Output of a program completely different from Computer Vision or Natural Language Processing, two hot topics in Machine Learning (ML). As people ⟨e⟩ ::= . that understand the supply chain complexity work with relational | ⟨v⟩ Variable databases, it seems to be the adequate place to let them build their | ⟨f⟩ Scalar own models and optimize them. One of the main ways to optimize | ⟨b⟩ Boolean a model is through gradient-based methods; if the model is written | ⟨v+w⟩ Variable Addition with queries then we need to differentiate them to optimize the | ⟨ Call1 op v ⟩ Function Call model. Letting experts build white box models will help them to | ⟨ Call2 op v w ⟩ Function Call (2 parameters) check the sanity of models, which is very difficult to do on black box | ⟨ Param i ⟩ Parameter access models, such as deep neural networks. It is called Interpretable ML | ⟨ Const i ⟩ Constant access in [19] and directly applies to the supply chain, where thousands of | ⟨v ⊳ 𝛽 ⟩ Broadcast Projector orders are placed everyday for a single company. Furthermore [20] | ⟨v ⊲ 𝛼 ⟩ Aggregation Projector has shown the advantages when performing an optimization in the | ⟨ Pred ⟩ Predicate database system itself, limiting data transfer costs, over pulling the ⟨ Pred ⟩ ::= . data out to an external ML-oriented system. | ⟨ And v w ⟩ Many sub parts of languages have been differentiated: Python [17] | ⟨ Or v w ⟩ [4], C [8], Julia [10], Swift [18], F# [3] . . . A more complete refer- | ⟨ Not v ⟩ ence can be found at [7]. However, there are only a few attempts at | ⟨v