dataesr/scientific-paragraphs-categorization huggingface dataset:
In this work, we introduce BOLDR (Breaking boundaries Of Language and Data Representations), a language-integrated query framework that allows arbitrary expressions from the host language (language from which the query comes from) to occur in queries and be evaluated in a database, thus lifting a key limitation of the existing solutions. Additionally, BOLDR is tied neither to a particular combination of database and programming language, nor to querying only one database at a time: for instance, BOLDR allows a NoSQL query targeting a HBase server to be nested in a SQL query targeting a relational database. BOLDR first translates queries into a Query Intermediate Representation (or QIR for short), an untyped λ-calculus with data-manipulation builtin operators, then applies a normalization process that may perform a partial evaluation of the QIR expression.
This partial evaluation composes distinct queries that may occur separated in the code of the host language into larger queries, thus reducing the communication overhead between the client runtime and the database and allowing databases to perform whole query optimizations. Finally, BOLDR translates and sends the queries to the targeted databases. Consider again our LINQ query containing the call to getRate. In BOLDR, its translation produces a QIR expression according to three different scenarios: (i) if getRate can be translated into the query language of the targeted database, then the whole expression is translated into a single query expressed in the query language of the targeted database; (ii) if getRate cannot be entirely translated but contains one or several queries that can be translated, then BOLDR produces the corresponding translated subqueries and sends them to their respective databases, and combines the results at QIR level; (iii) if getRate cannot be translated at all, then BOLDR creates a query containing the serialized host language abstract syntax tree of getRate to be potentially executed on the database side.
Track: Web Programming WWW 2018, April 23-27, 2018, Lyon, France Our implementation of BOLDR uses Truffle  [23] , a framework developed by Oracle Labs to implement programming languages. Several features make Truffle appealing to BOLDR: first, Truffle implementations of languages must compile to an executable abstract syntax tree that BOLDR can directly manipulate; second, languages implemented with Truffle can be executed on any JVM, making their addition as an external language effortless in databases written in Java (e. g. , Cassandra, HBase,. ), and relatively simple in others such as PostgreSQL. Third, work on one Truffle language can easily be transposed to other Truffle languages. Our implementation currently supports the PostgreSQL, HBase and Hive databases, as well as FastR  [17]  (Truffle implementation of the R language) and Oracle's SimpleLanguage (a dynamic language with syntax and features inspired by JavaScript).
The following R program illustrates the key aspects of BOLDR: 1 # Exchange rate between rfrom and rto 2 getRate = function(rfrom, rto) { 3 # table change has three columns: cfrom, cto, rate This example is a standard R program with two exceptions: the function tableRef (Line 4 and 11) referencing an external source in lieu of creating a data frame (R implementation of tables) from a text file; and the function executeQuery (Line 16 and 17) that evaluates a query. We recall that in R, the c function creates a vector, the subset function filters a table using a predicate, and optionally keeps only the specified columns. The first function getRate takes the code of two currencies and queries a table using subset to get their exchange rate. The second function atLeast takes a minimum salary and a currency code and retrieves the names of the employees earning at least the minimal salary.
Since the salary is stored in dollars in the database, the getRate function is used to perform the conversion. In BOLDR, subset is overloaded to build an intermediate query representation if applied on an external source reference. The first call to atLeast(2000, "USD") builds a query and captures the variables in the local scope. When executeQuery is called, then (i) the intermediate query is normalized, inlining all bound variables with their values; (ii) the normalized query is translated into the target database language (here SQL); and (iii) the resulting query is evaluated in the database and the results are sent back. After normalization and translation, the query generated for the first call on Line 14 is: SELECT name FROM employee WHERE sal >= 2000 * 1 which is optimal, in the sense that a single SQL query is generated.
The code generated for the second call is also optimal thanks to the interplay between lazy building of the query and normalization: Therefore, BOLDR not only supports user-defined functions (UDFs) in queries, it also merges subqueries together to create fewer and larger queries, thus benefiting from database optimizations and avoiding the "query avalanche" phenomenon  [12]. While similar approaches exist (see Section 8 on related work), BOLDR outperforms them on UDFs that cannot be completely translated. For instance, consider: 1 getRate = function(rfrom, rto) { 2 cfrom = c("EUR", "EUR", "USD", "USD", "JPY", "JPY") 3 cto = c("USD", "JPY", "EUR", "JPY", "EUR", "USD") This function builds an in-memory data frame using the builtin function data. frame. BOLDR cannot translate it to QIR since it calls the underlying runtime, so instead it generates the following query: SELECT name FROM employee WHERE sal >= 2000 * R.
eval("@. ", array("USD", "EUR")) where the string "@. " is a reference to a closure for getRate. Mixing different data sources is supported, although less efficiently. For instance, we could refer to an HBase table in the function getRate. BOLDR would still be able to evaluate the query by sending a subquery to both the HBase and PostgreSQL databases, and by executing in main memory what could not be translated. The general flow of query evaluation in BOLDR is described in Figure  1. During the evaluation 1 of a host program, QIR terms are lazily accumulated. Their evaluation, when triggered, is delegated to the QIR runtime 2 that normalizes 3 the QIR terms to defragment them, then translates 4 them to new QIR terms that contain database language queries (e. g. , in SQL). Next, the pieces of these terms are evaluated where they belong, either in mainmemory 5 or in a database 7.
"Frozen" host language expressions occurring in these terms are evaluated either by the runtime of the host language that called the QIR evaluation 6 , or in the runtime embedded in a target database 8. Results are then translated from the database to QIR 9 , then from QIR to the host language 10. Overview and Contributions. In this work, we introduce BOLDR, a multi-language framework for integrated queries with a unique combination of features such as the possibility of executing userdefined functions in databases, of partially evaluating and merging distinct query fragments, and of defining single queries that operate on data from different data sources. Our technical developments are organized as follows. We first give a formal definition of QIR (Section 3). We then present the translation from QIR to query languages and focus on a translation from QIR to SQL, as well as a type system ensuring that well-typed queries translate into SQL and are avalanche-free (Section 4).
We continue by presenting a normalization procedure on the QIR to optimize the translation of a query (Section 5). We next describe the translation from the host language R to QIR (Section 6). Finally, we discuss experimental results (Section 7) of our implementation that supports the languages R and SimpleLanguage and the databases PostgreSQL, HBase and Hive. We show that queries generated by BOLDR perform on a par with hand-written ones, and that UDFs can be efficiently executed in a corresponding runtime embedded in a target database.
is the evaluation function We abstract a host language H by reducing it to its bare components: a syntax given by a set of expressions E H , a set of variables I H , and a set of values V H. Lastly we assume that the semantics of H is given by a partial evaluation function H →. This function takes an evaluation environment (a set of pairs of variables and values, ranged over by σ ) and an expression and returns a new environment and a value resulting from the evaluation of the input expression. To integrate a host language we need to be able to manipulate syntactic expressions of the language, inspect and build environments, and have access to an interpreter for the language. Definition 2. 2 (Database language). A database language D with support for a host language H is a 4-tuple (E D , V D , O D , D →) where: • E D is a set of syntactic expressions • V D is a set of values • O D is a set of supported data operators • D → : 2 I H ×V H × E D → 2 I H ×V H × V D is the evaluation function Similarly to host languages, we abstract a database language D as a syntax E D , a set of values V D , and an evaluation function D → which takes an H environment and a database expression and returns a new H environment and a database value.
Records are deconstructed through field projections. Sequences are deconstructed by the list matching destructor whose four arguments are: the list to destruct, a pattern that binds the head and the tail of the list to variables, the term to evaluate (with the bound variables in scope) when the list is not empty, and the term to return when the list is empty. The new additions to these mundane constructs are database operators and host language expressions. A database operator o⟨q 1. , q n | q ′ 1 ,. , q ′ m ⟩ is similar to the notion of operator in the relational algebra. Its arguments are divided in two groups: the q i expressions are called configurations and influence the behavior of the operator; the q ′ i expressions are the sub-collections that are operated on. Finally, a host expression ■ H (σ , e) is an opaque construct that contains an evaluation environment σ and an expression e of the host language H.
Extended semantics We next define how to interface host languages and databases with QIR. We introduce the notion of driver, a set of functions that translate values from one world to another. Track: Web Programming WWW 2018, April 23-27, 2018, Lyon, France Definition 3. 3 (Language driver). Let H be a host language. A language driver for H is a 3-tuple ( H --→ EXP, --→ VAL H , H --→ VAL) of total functions such that: • H --→ EXP : 2 I H ×V H × E H → E QIR ∪ {Ω} takes an H environment and an H expression and translates the expression into QIR A database driver for D is a 3-tuple ( • --→ VAL H : V QIR → V H ∪ {Ω} translates QIR values to H values • H --→ VAL : V H → V QIR ∪ {Ω} ---→ EXP D , --→ VAL D , D --→ VAL) of total functions such that: • ---→ EXP D : E QIR → E D ∪ {Ω} translates a QIR expression into D • --→ VAL D : V QIR → V D ∪ {Ω} translates QIR values to D values • D --→ VAL : V D → V QIR ∪ {Ω} translates D values to QIR values where the special value Ω denotes a failure to translate.
We are now equipped to define the semantics of QIR terms, extended to host expressions and database operators. Definition 3. 5 (Extended QIR semantics). Let H be a host lan- guage, ( H --→ EXP, --→ VAL H , H --→ VAL) a driver for H , D a database language, and ( ---→ EXP D , --→ VAL D , D --→ VAL) a driver for D. We define the extended semantics σ , q ↠ σ ′ , q ′ of QIR by the following set of rules: q → q ′ σ, q ↠ σ, q ′ σ ∪ σ ′ , e H →σ ′′ , w σ, ■ H (σ ′ , e ) ↠ σ ′′ , H --→ VAL(w ) ---→ EXP D (o⟨q 1 ,. , q n | q ′ 1 ,. , q ′ m ⟩) = e σ, e D →σ ′ , w o ∈ O D e Ω D --→ VAL(w ) Ω σ, o⟨q 1 ,. , q n | q ′ 1 ,. , q ′ m ⟩ ↠ σ ′ , D --→ VAL(w ) Since QIR is an intermediate language from a host language to a database language, the evaluation of QIR terms will always be initiated from the host language runtime.
It is therefore natural for the extended semantics to evaluate a QIR term in a given host language environment. If this QIR term is neither a database operator nor a host language expression, then the simple semantics of Definition 3. 2 is used to evaluate the term, otherwise the extended semantics of Definition 3. 5 is used. Host expressions are evaluated using the evaluation relation of the host language in the environment formed by the union of the current running environment and the captured environment. This allows us to simulate the behavior of most dynamic languages (in particular R, Python, and JavaScript) that allow a function to reference an undefined global variable as long as it is defined when the function is called. Last, but not least, the evaluation of a database operator consists in (i) finding a database language that supports this operator, (ii) use the database driver for that language to translate the QIR term into a native query, (iii) use the evaluation function of the database to evaluate the query, and (iv) translate the results back into QIR.
DATABASE TRANSLATION In this section, we describe how a database driver can define a translation from QIR to a database language. This translation must be able to translate QIR expressions into equivalent efficient queries of a database language, and handle QIR expressions in which subterms target different databases. Additionally, it must be seamlessly extendable with new database drivers. To that end, we separate this translation in two phases: a generic translation that determines the targeted query language for all subterms of a QIR expression, and a specific translation that makes use of database drivers.
Generic translation The goal of the generic translation is to produce a QIR expression where as many subterms as possible have been translated into native database queries. Ideally, we want the whole QIR expression to be translated into a single database query, but this is not always possible and, in that case, parts of the expression have to be evaluated in the client side (where the QIR runtime resides). The QIR evaluator therefore relies on two components. First, a "fallback" implementation of QIR operators using the QIR itself, that we dub MEM for in-memory evaluation. MEM is a trivial database language for which the translations to and from the QIR are the identity function, and that supports the operators Filter, Project, and Join defined as plain QIR recursive functions. The full definition of MEM is straightforward and given in Section A of our appendix  [6].
Second, to allow the QIR evaluator to send queries to a database and translate the results back into QIR values, we assume that for each supported database language D ∈ D, we have a basic QIR operator, eval D defined as: σ , e D →σ ′ , v σ , eval D (e) ↠ σ ′ , D --→ VAL(v) Notice that in the case of the MEM language, the operator eval MEM is simply the reduction of a QIR term. The generic translation is given by the judgment q e, D where q ∈ E QIR and e ∈ E D ∪ {Ω}, which means a QIR expression q can either be rewritten into an expression e of the language E D of the database D, or fail when e = Ω. An excerpt of the set of inference rules used to derive this judgment is given in Figure  2. Rule (db-op) states that given a database operator, if there exists a database D distinct from MEM such that all data arguments can be translated into expressions of E D , then if the specific translation ---→ EXP D called on the operator yields a fully translated E D expression e, then e is returned as a translation in E D.
This rule may fail in two cases: the data arguments of the operator could be translated to more than one database language; or the specific translation for E D could yield an error Ω even if all data arguments of the operator have been successfully translated into expressions of the same language E D , for instance, when the operator is not supported by D, or when the specific translation of a configuration q i fails. If the operator o at issue is one of the supported operators of MEM, then both cases are handled by the rule (mem-op): each translated subexpression e i is wrapped in a call to the eval D i operator and o is evaluated with its MEM semantics. All the other rules are bureaucratic and propagate the translation recursively to subterms. (db-op) q ′ i e i , D, i ∈ 1. m ---→ EXP D (o⟨q 1 ,.
, q n | q ′ 1 ,. , q ′ m ⟩) = e D ∈ D \ MEM e Ω o⟨q 1 ,. , q n | q ′ 1 ,. , q ′ m ⟩ e, D (fun) q e, D fun f (x )→q fun f (x )→eval D (e ), MEM (mem-op) q ′ i e i , D i , ∈ 1. m o ∈ O MEM e i Ω o⟨q 1 ,. , q n | q ′ 1 ,. , q ′ m ⟩ ---→ EXP MEM (o⟨q 1 ,. , q n | eval D 1 (e 1 ),. , eval D m (e m )⟩), MEM (app) q 1 e 1 , D 1 q 2 e 2 , D 2 q 1 q 2 (eval D 1 (e 1 )) (eval D 2 (e 2 )), MEM We document how to define specific translations using SQL as an example of a database language. QIR to SQL is an important translation as it allows BOLDR to target most relational databases and some distributed databases such as Hive or Cassandra. We assume that the set of values for SQL only contains basic constants (strings, numbers, Booleans,. ) and tables. The set of expressions E SQL is the set of syntactically valid SQL queries  [1].
QIR HEURISTIC NORMALIZATION Our guarantees only hold for a QIR query targeting one database supporting SQL. However, a QIR term may mix several databases or use features that escape the hypotheses of Theorem 4. 2. In particular, outside these hypotheses, we cannot guarantee the termination of the normalization. We are therefore stuck between two unsatisfactory options: either (i) trying to normalize the term (to fully reduce all applications) and yield the best possible term w. r. t. query translation but risk diverging, or (ii) translate the term as-is at the risk of introducing query avalanches. We tackle this problem with a heuristic normalization procedure that tries to reduce QIR terms enough to produce a good translation by combining subqueries. To that end, we define a measure of "good" QIR terms, and ask that each reduction step taken yields a term with a smaller measure.
To formally define this measure, we first introduce a few concepts. Definition 5. 1 (Compatible data operator application). Let D be the set of database languages. A QIR data operator o⟨q 1 ,. , q n | q ′ 1 ,. , q ′ m ⟩ is a compatible operator application if and only if: ∃D ∈ D, e 1 ,. , e m ∈ E D s. t. ---→ EXP D (o, q 1 ,. , q n , e 1 ,. , e m ) Ω Intuitively, a compatible data operator application is one where the configuration arguments are in a form that is accepted by the specific translation of the database language D. We now define the related notion of fragment.
Definition 5. 2 (Fragment). A fragment F is a subterm of a QIR term q such that q = C[T (q 1 ,. , q i-1 , F [e 1 ,. , e n ], q i+1 ,. , q j )] where C is a one-hole context made of arbitrary expressions; T is a non-compatible j-ary expression; q 1 ,. , q i-1 , q i+1 ,. , q j and F are the children of T ; F is an n-hole context made only of compatible operators applications of the same database language D; and all e 1 ,. , e n have head expressions that are not compatible. Figure  4  gives a graphical representation of a fragment. We can now define a measure of "good" QIR terms. Let q ∈ E QIR be a QIR expression, we define the measure of q as the pair M (q) = (Op(q) -Comp(q), Frag(q)) where Op(q) is the number of occurrences of data operators in q, Comp(q) is the number of occurrences of compatible data operator applications in q and Frag(q) is the number of fragments in q.
The order associated with M is the lexicographic order on pairs. This measure works as follows. During a step of reduction of a term q into a term q ′ , q ′ is considered a better term either if the number of operators decreases, or if q ′ possesses more occurrences of compatible operator applications, meaning less cycles between QIR and the databases, or lastly, if the number of data operators does not change but the number of fragments decreases, meaning that some data operators were combined into a larger fragment. Γ ⊢ q : {l : B,. } list Γ ⊢ q : B Γ ⊢ q : {l : T ,. } Γ ⊢ q • l : T Our heuristic-based normalization procedure uses this measure as a guide through the reduction of a QIR term: it applies all possible combinations of reduction steps to the term as long as its measure decreases after a number of steps fixed by heuristic.
This allows us to generate a more efficient translation while ensuring termination. Some practical choices impact the effectiveness of the QIR normalization such as choosing which reduction rule to apply at each step (e. g. , choosing those with more arguments), or which maximum number of steps to use. Extensive experiments for both points are detailed in a technical report  [22]. In particular, we measure that the normalization represents a negligible fraction of the execution time of the whole process compared to tasks such as parsing, or exchanges on the network with databases.
g. , as in Python or JavaScript) where identifiers that are not in the current static scope are assumed to be global identifiers even if they are undefined when the scope is created. For instance, the R program: f = function (x) { x + y }; y = 3; z = f(2); is well-defined and stores 5 in z (but calling f before defining y yields an error). We next define the core syntax of R. We recall that, in R, c(e 1 ,. , e n ) builds a vector. Definition 6. 1 only defines expressions that can be translated to QIR. Expressions not listed in the definition are translated into host expression nodes. We now highlight how data frames are manipulated in standard R. As mentioned in Section 1, the subset function filters a data frame: 12 subset(t, sal >= minSalary * getRate("USD", cur), c(name)) This function returns the data frame given as first argument, filtered by the predicate given as second argument, and restricted to the columns listed in the third argument.
Note that before resolving its second and third arguments, and for every row of the first argument, subset binds the values of each column of the row to a variable of the corresponding name. This is why in our example the variables sal and name occur free: they represent columns of the data frame t. The join between two data frames is implemented with the function merge. We recall that the join operation returns the set of all combinations of rows in two tables that satisfy a given predicate. To integrate R with BOLDR, we define two builtin functions: • tableRef takes the name of a table and the name of the database the table belongs to, and returns a reference to the table • executeQuery takes a QIR expression, closes it by binding its free variables to the translation to QIR of their value from the current R environment, sends it to the QIR runtime for evaluation, and translate the results into R values We also extend the set of values V R : v ::=.
| tableRef(v,. , v) | q σ where q σ are QIR closure values representing queries associated with the R environment σ used at their definition. The functions subset and merge are overloaded to call the translation R --→ EXP on themselves if their first argument is a reference to a database table created by tableRef, yielding a QIR term q to which the current scope is affixed, creating a QIR closure q σ. Free variables in q σ that are not in σ are global identifiers whose bindings are to be resolved when q σ is executed using executeQuery. We now illustrate the whole process on the introductory example of Section 1. Evaluation of the query expression: When an expression recognized as a query is evaluated, it is translated to QIR (using Definition C. 2 in Section C of our appendix  [6] ). In the introductory example, the function call in which the function subset (Line 12) is evaluated with a table reference as first argument, and is therefore translated into a QIR expression.