# Correlation and Substitution in SPARQL

Daniel Hernández  Claudio Gutierrez  Renzo Angles

###### Abstract

In the current sparql specification the notion of correlation and substitution
are not well defined. This problem triggers several ambiguities in the
semantics. In fact, implementations as Fuseki, Blazegraph, Virtuoso and rdf4j
assume different semantics.

In this technical report, we provide a semantics of correlation and
substitution following the classic philosophy of substitution and correlation
in logic, programming languages and sql. We think this proposal not only gives
a solution to the current ambiguities and problems, but helps to set a safe
formal base to further extensions of the language.

This work is part of an ongoing work of Daniel Hernandez. These anomalies in
the W3C Specification of SPARQL 1.1 were detected early and reported no later
than 2014, when two erratas were registered (cf.
https://www.w3.org/2013/sparql-errata#errata-query-8 and
https://www.w3.org/2013/sparql-errata#errata-query-10).

Version

##  1 Introduction

The first version of this technical report served as a starting point to
restart the discussion about the substitution and correlation in SPARQL. This
issue was discussed in several threads on the W3C public-sparql-dev mailing
list (see messages of Jun, 2016 in the mailing list
archives111https://lists.w3.org/Archives/Public/public-sparql-dev/2016AprJun/)
and a W3C Community Group222https://www.w3.org/community/sparql-exists/ was
created to discuss and address problems with the specification of the EXISTS
clause in SPARQL.

This new version of the report fixes errors of the previous one and includes a
formalization of two alternative semantics that are currently implemented: The
first by Blazegraph and Fuseki, a semantics where substitution is never
applied because variables that are not projected to resulting solutions are
not visible from outside. The second, by Virtuoso and rdf4j, where every
variable that is not projected to resulting solution are visible from outside,
so they can be substituted. Within the same formal framework, we show the
semantics presented in the previous technical report, where some variables are
visible and other are not.

The main idea of the formal framewok work as follows. Given a graph pattern P
and a solution mapping $\mu$, the Standard Spec. of SPARQL introduces the
notion of substitute$(\mathtt{P},\mu)$, that is used to evaluate nested
patterns. However, as we show in this report, this function substitute is not
well defined and is contradictory with other parts of the specification. In
this tech report, we define a similar function, which we call bind (to avoid
clash names), that solves the problems found. It basically normalizes the
pattern $\mathtt{P}$ before applying the mapping $\mu$, giving a new structure
$\operatorname{norm}(P)$ that essentially renames variables so that each one
plays the same role in every occurrence.

#### Structure of this technical report

Section 2 presents an example of correlation using substitution to exemplify
ambiguities of the current specification and differences of implementations.
Section 3 describes the problem with current notion of substitution. In
Section 4 we propose three alternative ways to define
$\operatorname{bind}(\mathtt{P},\mu)$ based in alternative definitions for
$\operatorname{norm}(\mathtt{P})$. Section 5 discuss how the proposed
semantics are safe regarding with the use of blank nodes. Finally, in Section
6 we present several examples that illustrated how correlation is evaluated in
each semantics and how implementations match them.

##  2 Evaluation of correlated variables

Consider the following simple sparql query that selects people of country $j$
that have children, and consider as data the rdf graph depicted in Figure 1
below.

Listing 1 1SELECT ?parent2WHERE { ?parent :country :j3 FILTER ( EXISTS {
SELECT ?child4 WHERE { ?child :parent ?parent }})}

:a:j:b:c:k:d:parent:parent:parent:country:country:country Figure 1: RDF graph.

The engines Fuseki and Blazegraph give as solution two mappings: $\mu_{a}$ and
$\mu_{b}$, where $\mu_{a}$ is $\\{\text{\tt?parent}\mapsto\text{\tt:a}\\}$ and
$\mu_{b}$ is $\\{\text{\tt?parent}\mapsto\text{\tt:b}\\}$. Virtuoso and rdf4j
(formerly Sesame), on the other hand, give a different result, only $\mu_{b}$.
Why these differences?

What does the W3C Spec. tell? The query has the form SELECT ?parent WHERE {P
FILTER (EXISTS {Q})}, where we will call P and Q respectively the outer and
the inner graph patterns. How to evaluate this query? The W3C Spec. gives
these two definitions that are relevant for this:

######  Definition 1 (Standard substitution, W3C Spec., §18.6).

Let $\mu$ be a solution mapping an P be a graph pattern. Then,
$\mathrm{substitute}(\mathtt{P},\mu)$ is the graph pattern formed by
replacing, for each $x$ in $\mathrm{dom}(\mu)$, every occurrence of a variable
$x$ in P by $\mu(x)$.

######  Definition 2 (Evaluation of Exists, W3C Spec. §18.6).

Let $\mu$ be the current solution mapping for a filter and P a graph pattern:
The value $\mathrm{exists}(\mathtt{P})$, given $D(G)$, is true if and only if
$\mathrm{eval}(D(G),\mathrm{substitute}(\mathtt{P},\mu))$ is a non-empty
sequence.

In definition 2 above, the argument $D(G)$ denotes that the evaluation is done
against the dataset $D$ using the graph $G$. For the sake of the readability,
in that follows we use the notation $\llbracket\mathtt{P}\rrbracket_{D}$
instead of $\mathrm{eval}(D(G),\mathtt{P})$.

The result of the P FILTER (EXISTS {Q}) clause, according to the W3C Spec.,
should be the set $\Omega$ such that:333 We will avoid the multiplicities in
this report because the problems we report are independent of having set or
multiset semantics.

$\displaystyle\Omega$
$\displaystyle=\\{\mu\in\llbracket\mathtt{P}\rrbracket_{D}\mid\llbracket\mathrm{substitute}(\mathtt{Q},\mu)\rrbracket_{D}\text{
is not empty}\\}.$

So, it seems that Virtuoso and rdf4j follow the standard here: First, evaluate
the pattern P, which give mappings $\mu_{a}$ and $\mu_{b}$, and for each of
them, perform the replacement in Q. As
$\llbracket\mathrm{substitute}(\mathtt{Q},\mu_{a})\rrbracket_{D}=\varnothing$
and
$\llbracket\mathrm{substitute}(\mathtt{Q},\mu_{b})\rrbracket\neq\varnothing$,
the final solution is the mapping $\mu_{b}$.

In defense of Fuseki and Blazegraph, let us say that the W3C Spec. says in
other place (§12. Subqueries): “Note that only variables projected out of the
subquery will be visible, or in scope, to the outer query.” That is, the
variable :parent inside the WHERE clause is not visible from outside, and
thus, Q cannot be changed by any mapping $\mu$ (in the sense of Defn. 1). Thus
the `FILTER (EXISTS {Q})` is true, and thus the two mappings $\mu_{a}$ and
$\mu_{b}$ qualify as final solutions.

The situation becomes even more involved when one considers another way of
writing the previous query. Consider now the query in listing 2.

Listing 2 1SELECT ?parent2WHERE { ?parent :country :j3 FILTER ( EXISTS {
SELECT ?child4 WHERE { ?child :parent ?chparent5 FILTER (?chparent = ?parent)
}})}

The listings 2 and 2 present the queries resulting of applying the
substitution on the inner graph pattern with the mappings $\mu_{a}$ and
$\mu_{b}$, respectively.

Listing 3

1SELECT ?child

2WHERE {

3 ?child :parent ?chparent

4 FILTER (?chparent = :a)

5}

Listing 4

SELECT ?child

WHERE {

?child :parent ?chparent

FILTER (?chparent = :b)

}

Only the second listing has solutions, so the evaluation of whole query
returns $\\{\mu_{b}\\}$. Actually, in Virtuoso this query outputs the expected
result, that is, $\\{\mu_{b}\\}$. On the contrary, in Fuseki and Blazegraph
this query outputs no solutions. These systems are following another part of
the W3C Spec. (12. Subqueries): “Due to the bottom-up nature of SPARQL query
evaluation, the subqueries are evaluated logically first, and the results are
projected up to the outer query.” Thus, they probably consider that the inner
query returns error because there is a non-bound variable ?parent.

#### Engines

Examples presented in this report where tested in Fuseki
2.4.0444https://jena.apache.org, Blazegraph Community Edition
2.1.0555https://www.blazegraph.com, Virtuoso Open Source Edition
7666https://github.com/openlink/virtuoso-opensource/tree/stable/7 and rdf4j
2.0 Milestone Builds777http://rdf4j.org.

##  3 Problems with the current notion of substitution

The previous examples show that problems arise when is not clear if
occurrences of a variable are correlated888We use “correlated variables” and
“correlation” to indicate the occurrence of a variable $x$ in and expression
$E$ whose value depends on the value of the occurrence of same variable $x$ in
an expression containing $E$. The paradigmatic occurrence of correlation in
SPARQL is the expression Q EXIST FILTER (P). and, in particular, if
substitution has to be applied in a variable. In this section we will show
that one of the main problems with nested queries in sparql is that the notion
of substitution is not well defined. We will present a solution to this issue,
which in turns helps to fix the whole semantics of nesting.

First, consider the simple graph pattern Q:

SELECT ?x WHERE {:a :p ?x}

and let $\mu$ be the solution mapping $\\{\text{\tt?x}\mapsto 1\\}$. Then,
$\mathrm{substitute}(\mathtt{Q},\mu)$, understood literally from the standard,
means replacing every occurrence of ?x with 1, that gives:

SELECT 1 WHERE {:a :p 1}

Thus, the substitution method of the W3C Spec. is not well defined because it
breaks the grammar of the SELECT clause.999 This and more subtle problems that
a naive notion of substitution brings are well know in logic and algebra long
ago. For example, a variable $x$ cannot be substituted by a constant in all
its occurrences in the first order formula $\forall x\,p(x)$ or in an
expression like $\sum_{x\in A}(x+a)$. .

The notion of substitution was already present in SPARQL 1.0 in patterns of
the form P FILTER (C). In SPARQL 1.0 C is a Boolean clause, and here the
substitution works fine because every occurrence of a variable could be
replaced without breaking the grammar. The only case that required a special
treatment was the function bound(?x) where ?x was not substituted, but checked
if it was in the domain of the current solution.

On the contrary, in SPARQL 1.1, the clauses EXISTS {Q} and NOT EXISTS {Q} are
filter constraints, thus allow nesting a graph pattern Q instead of the
Boolean clause in a filter. And a graph pattern may contain variables with
occurrences that are not replaceable (as we previously discussed) and
variables with occurrences that are not “visible from outside” Q. Thus, the
naive substitution, consisting on just replacing all occurrences of a
variable, cannot be directly applied in SPARQL 1.1 as was in SPARQL 1.0.

##  4 Semantics of nested expressions with correlated variables

In this section we propose three alternatives for the function
$\operatorname{bind}$, that is defined as alternative to the function
$\mathrm{substitute}$ for evaluating nested queries with correlated variables,
two of which represent approaches existing in current implementations and the
other the approach that was proposed in the previous version of this report.

###  4.1 The domain of a graph pattern

Given a graph pattern P, we denote as $\mathrm{var}(\mathtt{P})$ to the set of
variables that occur in P.

An interesting subset of $\mathrm{var}(\mathtt{P})$ is the one that includes
the variables that occur in the solutions of P, that we call the domain of P
and denote as $\mathrm{dom}(\mathtt{P})$, that is formally defined as
follows101010Recall that $\operatorname{dom}(\mu)$ is the domain of variables
of $\mu$ (those where $\mu$ is defined) when $\mu$ is considered as a partial
function over the set of all variables of the universe.:

$\mathrm{dom}(\mathtt{P})=\\{x\in\operatorname{dom}(\mu)\;|\text{ exists
dataset $D$ with }\mu\in\llbracket\mathtt{P}\rrbracket_{D}.\\}$

This definition of dataset cannot be used directly to compute the domain of a
graph pattern, because requires the verification in all possible datasets. The
following lemma shows that it is possible to give a method to compute the
domain of a graph pattern using only its syntax.

######  Lemma 1 (In-domain variables).

Given a graph pattern P and a variable ?x occurring in P, then
$\text{\tt?x}\in\mathrm{dom}(\mathtt{P})$ if and only if:

  1. 1.

P is a basic graph pattern and ?x occurs in P.

  2. 2.

If P is Q$\circ$R where $\circ$ is ‘.’, UNION or OPTIONAL and
$\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})\cup\mathrm{dom}(\mathtt{R})$.

  3. 3.

If P is Q MINUS R where $\circ$ is ‘.’, and
$\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})$.

  4. 4.

If P is GRAPH ?x {Q}.

  5. 5.

If P is GRAPH u {Q} and $\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})$.

  6. 6.

If P is VALUES (X) {B} and ?x occurs in the list of variables X.

  7. 7.

If P is Q BIND (E AS ?x).

  8. 8.

If P is Q BIND (E AS ?y) and $\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})$.

  9. 9.

If P is Q FILTER (C) and $\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})$.

  10. 10.

If P is SERVICE u {Q} and $\text{\tt?x}\in\mathrm{dom}(\mathtt{Q})$.

  11. 11.

If P is SELECT X WHERE {Q} if X is a list such that one of its elements is ?x
or has the form (E AS ?x).

Note that in the SPARQL specification variables that are in the domain of
graph pattern are called in-scope and also defined using the syntax (see
18.2.1 in the W3C Spec.). In this report we call them in-domain to stress the
idea that they define the domain of the output.

###  4.2 Syntax and variables roles

A variable in the syntax can play several roles. Two relevant ones are the
role of representing the the output of a computation (output role) and the one
representing the output of a previous computation (input role). For example,
in the expression let x be f(y) in { g(x,y) } in a functional language, the
variable x is playing the output role in the outermost occurrence and the
input role in the innermost occurrence. On the other hand, y plays the input
role in both occurrences.

These roles are crucial to understand how the substitution of variables by
values work. Indeed, when a variable is in the input role, we can substitute
it without breaking the syntax of the language. On the contrary, a variable in
the output role cannot be substituted, because values cannot be used to name
results of computations.

The question that arises is if we can distinguish the role of a variable
occurrence in SPARQL. To answer this question, let us to consider the
following types of syntactic constructs in which variables occur:

Expression.

In a comparison (e.g., ?x < 2), an scalar operation (e.g., 1+x) or an scalar
function (e.g., substr(?x, 4)).

Pattern.

In a basic graph pattern (e.g., ?x :p ?y).

Naming.

In any place that only variables are allowed (e.g., E AS ?x), except when they
occur in the bound($\cdot$) function (e.g., bound(?x)), that is an special
case.

The ocurrence of variables in the three types of constructs are associated
with the output or input roles as shown in Table 1.

| Input | Output
---|---|---
Expression | $\times$ |
Pattern | $\times$ | $\times$
Naming |  | $\times$
Table 1: Possible variable roles in types of syntactic constructs.

In occurrences in expressions, it is clear that the variable can be
substituted, because it refers to a value to be used inside the expression.
Similarly, in naming occurrences, it is clear that the variable cannot be
substituted, because breaks the grammar. Moreover, the variable will be used
to refer the value in a future computation so its name cannot be forgotten nor
changed.

In the case of occurrences in patterns the variable could have both roles.
Indeed, we can substitute the variable with a value without breaking the
semantics, so the variable is playing the input role. On the other hand, if
the variable is not substituted, then it will bind a value from the data that
will be available for future computations, so it is playing an output role.

The substitution of variables that are in syntactic constructs of type pattern
(i.e., in a basic graph pattern) has another issue: A variable ?x that is
replaced by a value in a basic graph pattern P does not appear in the
solutions of evaluating P. Thus, the domain of P will be reduced after the
substitution.

This, reduction in the domain of a graph pattern after a substitution, may
produce odd results. Indeed, let P and Q be respectively the basic graph
patterns {?x :p ?y} and {?y :p ?z}. Let $\mathtt{P}^{\prime}$ and
$\mathtt{Q}^{\prime}$ be the results of substituting ?y by :b in P and Q,
respectively. Let $\mu$ be the solution
$\\{\text{\tt?y}\mapsto\text{\tt:b}\\}$. Then, the graph pattern P.Q has less
solutions than P′.Q′ over the dataset
$\\{(\text{\tt:a},\text{\tt:p},\text{\tt:b}),(\text{\tt:b},\text{\tt:p},\text{\tt:c})\\}$.
This contradicts, the intuition that substituting variables with values
restrict the results.

###  4.3 Normalization

The normalization of a graph pattern or expression P is defined to avoid
variables with role ambiguity (i.e., that has simultaneously input and output
roles) by changing the structure of P and replacing every variable occurring
in P with a different fresh variable for each scope that can be determined for
the variable. After the normalization process, variables that can be
substituted will occur only in syntactical constructs of type expression, so
solving the issue described at the end of the previous section.

######  Definition 3 (Normalization).

The normalization of the pattern $\mathtt{P}$, that we denote as
$\mathrm{norm}(\mathtt{P})$, is a triple $(\mathtt{P}^{\prime},d,g)$, where
$\mathtt{P}^{\prime}$ is a pattern whose variables must be all fresh and $d$
and $g$ are partial functions whose domain and ranges are as follows:

$\displaystyle d$
$\displaystyle:\mathrm{var}(\mathtt{P}^{\prime})\rightarrow\mathrm{dom}(\mathtt{P}),$
$\displaystyle g$
$\displaystyle:\mathrm{var}(\mathtt{P}^{\prime})\rightarrow\mathrm{var}(\mathtt{P}),$

$d$ is surjective and the domains of $d$ and $g$ are disjoint.

Intuitively, $d$ and $g$ are functions that associate (record) the
correspondence of the fresh variables of $\mathtt{P}^{\prime}$ with the
corresponding original variables $\mathtt{P}$. The function $d$ represents
occurrences of variables that are in the solutions of P and $g$ represents
occurrences of variables that can be substituted by values that $\mu$ maps.
The sets $\mathrm{range}(d)$ and $\mathrm{range}(g)$ could have elements in
common. For example, if P is the graph pattern Q.R then a variable can be in
the domain of Q and simultaneously be a global variable in R,

To give an intuition, here there is an illustration of a normalization in a
simple case. Let P be:

{:a :p ?x} . {:b :q ?y FILTER (?y < ?x)}.

The result of normalizing P is $(\mathtt{P}^{\prime},d,g)$ where
$\mathtt{P}^{\prime}$ is

{:a :p $x_{1}$} . {:b :q $y_{1}$ FILTER ($y_{1}$ < $x_{2}$)}

and $d$ and $g$ are respectively the functions

$\displaystyle d$
$\displaystyle:=\\{x_{1}\mapsto\text{\tt?x},\,y_{1}\mapsto\text{\tt?y}\\},$
$\displaystyle g$ $\displaystyle:=\\{x_{2}\mapsto\text{\tt?x}\\}.$

(We use a different notation for variables $\mathtt{P}^{\prime}$ to stress the
idea that they are fresh.) Note that in the pattern $\mathtt{P}^{\prime}$ in
$(\mathtt{P}^{\prime},d,g)$ each variable plays a unique role, and the
functions $d,g$ “tell” what is the role of each variable and their
relationships.

Note that this example uses a particular normalization according with a
specific semantics. An alternative semantics may produce a different
normalization (which is only designed to make the role of each variable
independent of its occurrence).

###  4.4 Substitution and correlated evaluation

We need a pair of notations before introducing the main notions. Given a
partial function $f$ that maps variables to variables and an structure of
expression $A$ where some of this variables occur, then $f(A)$ denotes the
result of renaming consistently in $A$ every variable $x\in\mathrm{dom}(f)$ by
$f(x)$. Functions can be viewed a set of ordered pairs. We will use the
notation $x\mapsto f(x)$ instead of $(x,f(x))$ to stress the notion of
mapping. Thus, the symbol $\varnothing$ (used commonly to denote empty sets)
also denotes empty functions.

Now we are ready to present our main notion:

######  Definition 4 (Mapping substitution).

Let P be a graph pattern, $\mu$ a solution mapping and $d$ and $g$ be
functions that map variables to variables. Then $\mu(\mathtt{P},d,g)$ is the
graph pattern $d(\mathtt{P}^{\prime})$, where $\mathtt{P}^{\prime}$ is the
graph pattern resulting of the following substitutions in $\mathtt{P}$:

  1. 1.

For each binding $x\mapsto\texttt{?x}$ in $g$ substitute every occurrence of
bound($x$) by TRUE if $\text{\tt?x}\in\mathrm{dom}(\mu)$ or by FALSE if
$\text{\tt?x}\not\in\mathrm{dom}(\mu)$.

  2. 2.

Then, for each binding $x\mapsto\texttt{?x}$ in $g$ substitute every
occurrence of $x$ by $\mu(\text{\tt?x})$ if $\text{\tt?x}\in\mathrm{dom}(\mu)$
or by ?x if $\text{\tt?x}\not\in\mathrm{dom}(\mu)$.

######  Definition 5 (Main: Correlated graph pattern or expression).

Let P be a graph pattern or expression, $\mu$ be a solution and
$\mathrm{norm}$ be a function that receives a graph pattern and returns triple
$(\mathtt{P}^{\prime},d,g)$ where $\mathtt{P}^{\prime}$ is a graph pattern and
$d$ and $g$ are functions that map variables to variables. Then:

$\displaystyle\operatorname{bind}(\mathtt{P},\mu)=\left\\{\begin{array}[]{ll}\mu(\operatorname{norm}(\mathtt{P}))\,.\,\mu|_{\mathrm{dom}(\mathtt{P})}&\text{if
}\mathtt{P}\text{ if a graph pattern},\\\
\mu(\operatorname{norm}(\mathtt{P}))&\text{if }\mathtt{P}\text{ if an
expression}.\end{array}\right.$

Note that $\mu|_{\mathrm{dom}(\mathtt{P})}$ denotes the inline data that
codify exactly the multiset containing the solution
$\mu|_{\mathrm{dom}(\mathtt{P})}$ with multiplicity 1\. For example, if
$\mu|_{\mathrm{dom}(\mathtt{P})}$ is the solution $\\{\text{\tt?x}\mapsto
1,\text{\tt?y}\mapsto 2\\}$ then it is codified as VALUES (?x ?y) {(1 2)}.

The function $\operatorname{bind}$ can be used in any place where the function
$\mathrm{substitute}$ is used by the Standard Spec. For example, given a
dataset $D$, the graph patterns P and Q and the expression E, then:

$\displaystyle\llbracket\text{\tt P FILTER (EXISTS {Q})}\rrbracket_{D}$
$\displaystyle=\\{\mu\in\llbracket\mathtt{P}\rrbracket_{D}\mid\llbracket\operatorname{bind}(\mathtt{Q},\mu)\rrbracket_{D}\text{
is not empty}\\}$ $\displaystyle\llbracket\text{\tt P BIND (E AS
?x)}\rrbracket_{D}$ $\displaystyle=\llbracket
P\rrbracket_{D}\Join\\{\\{\text{\tt?x}\mapsto\llbracket\operatorname{bind}(\mathtt{E},\mu)\rrbracket_{D}\\}\\}$

In what follows, we present three variants of the normalization function. Each
one, according to Definition 5 will give a particular semantics. Given a graph
pattern P and its normalization $(\mathtt{P}^{\prime},d,g)$, these variants
differ essentially in the variables occurring in P that are included in the
range of the function $g$. Intuitively, variables that are excluded of the
ranges of $d$ and $g$ can be considered local, because the normalization
renames them to fresh variables and does not record the original names.

###  4.5 Semantics S1

According S1 all variables that are not in the domain of a graph pattern are
considered local. Thus, the normalization in S1 is defined as follows:

######  Definition 6 (Normalization in S1).

Given a graph pattern P, then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d,\varnothing)$ where:

  1. 1.

$d$ is a surjective function that maps fresh variables to variables in
$\mathrm{dom}(\mathtt{P})$.

  2. 2.

$\mathtt{P}^{\prime}$ is $h(d^{-1}(\mathtt{P}))$ where $h$ is a function that
maps variables in $\mathrm{var}(\mathtt{P})\setminus\mathrm{dom}(\mathtt{P})$
to fresh variables.

At the end of this procedure is ensure that all local variables in P are
substituted $\mathtt{P}^{\prime}$ with fresh variables that will be not
substituted again because the third component of the normalization is empty.
This is summarized in the following result.

######  Lemma 2.

According the semantics S1, given a graph pattern P, a solution mapping $\mu$
and a dataset $D$, then:

$\llbracket\operatorname{bind}(\mathtt{P},\mu)\rrbracket_{D}=\llbracket\mathtt{P}\rrbracket_{D}\Join\\{\mu_{|\mathrm{dom}(\mathtt{P})}\\}$

###  4.6 Semantics S2

Before defining this semantics we need some definitions that will help us in
the notation.

######  Definition 7 (The filter clause).

Given two variables ?y and ?y then $F_{\text{\tt?x?y}}$ is the operator FILTER
(!(bound(?x) && bound(?y)) || ?x = ?y).

The operator $F_{\text{\tt?x?y}}$ help us to rewrite a variable that is in the
domain of a graph pattern as a variable whose visibility is global according
S2 and S3. For example, let P and Q be the graph patterns {a :p ?x} and {:x :p
?y} $F_{\tt?x?y}$, respectively. Then, intuitively
$\llbracket\mathtt{P}\rrbracket_{\mu}=\llbracket\mathtt{Q}\rrbracket_{\mu}$
for every mapping $\mu$.

######  Definition 8 (Consequently renaming).

Let be $f$ and $g$ be two functions that map variables to variables where $g$
is injective. Then, $\mathrm{cr}(f,g)$ is the function $g^{-1}|_{A}\cdot
f|_{A}$ where $A$ is $\mathrm{range}(f)\cap\mathrm{range}(g)$ and “$\cdot$”
denotes the composition of functions111111 Note that that is if
$x\in\mathrm{dom}(f)$ and $f(x)\in\operatorname{dom}(g)$ then $(f\cdot
g)(x)=g(f(x))$. .

If a graph pattern P is composed of the graph patterns Q and R, then results
natural defining the normalization of P as a composition of the respective
normalizations $\mathtt{Q}^{\prime}$ and $\mathtt{R}^{\prime}$ of its
components. Because the normalization of these components are performed
independently, the variables in the domain may be different, thus it is needed
to rename variables in one of the components to make both renaming consequent
in the outputs of both components. The following lemma show that given to
renamings $f$ and $g$ where $g$ is injective, then $\mathrm{cr}(f,g)$ can be
used to generate a function $g^{\prime}$ that is compatible with $f$, that is
$(\mathrm{cr}(f,g))(g)$.

######  Lemma 3.

Given two functions $f$ and $g$ that map variables to variables where $g$ is
injective, then $(\mathrm{cr}(f,g))(g|_{A})=f|_{A}$.

At this point we are ready to proceed with the formalization of the
normalization in the semantics S2.

######  Definition 9 (Normalization in S2).

Given a graph pattern or expression P, then:

  1. 1.

If P is a basic graph pattern, then $\mathrm{norm}(\mathtt{P})$ is
$(d^{-1}(\mathtt{P}),d,\varnothing)$, where $d$ is a function that contains a
binding $x\mapsto\text{\tt?x}$ for every variable ?x in
$\mathrm{var}(\mathtt{P})$.

  2. 2.

If P is SELECT X WHERE {Q} (where X is a list of variables), then
$\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$, where:

$\displaystyle\mathtt{P}^{\prime}$ $\displaystyle=\text{\tt SELECT
X${}^{\prime}$ WHERE {Q${}^{\prime}$}}$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}}|_{d_{\mathtt{Q}}^{-1}(\mathrm{dom}(\mathtt{P}))}$
$\displaystyle g_{\mathtt{P}}$ $\displaystyle=g_{\mathtt{Q}}$
$\displaystyle\mathtt{X}^{\prime}$
$\displaystyle=d_{\mathtt{P}}^{-1}(\mathtt{X})$

Note that $d_{\mathtt{Q}}^{-1}(\mathrm{dom}(\mathtt{P}))$ is the preimage in
$d_{\mathtt{Q}}$ of $\mathrm{dom}(\mathtt{P})$. That is, the set of variables
used in Q to rename variables that are projected in the solution of P. Thus,
$d_{\mathtt{Q}|d_{\mathtt{Q}}^{-1}(\mathrm{dom}(\mathtt{P}))}$ is the renaming
of variables used in Q, restricted to the domain of P. Similarly,
$d_{\mathtt{P}}^{-1}(\mathtt{X})$ is renaming of variables in X that is
consecuent with the renaming done in Q.

Bindings $x\mapsto\text{\tt?x}$ in $d_{\mathtt{Q}}$ such that ?x is not in the
domain of P are not included in $d_{\mathtt{P}}$ nor in $g_{\mathtt{Q}}$.
This, is interpreted as that the cocurrences of ?x associated to this bindings
are assumed local.

  3. 3.

If P is $\mathtt{Q}\circ\mathtt{R}$ where $\circ$ is ‘.’, OPTIONAL or UNION,
then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$, where:

$\displaystyle\mathtt{P}^{\prime}$ $\displaystyle=\mathtt{Q}^{\prime}\circ
f(\mathtt{R}^{\prime})$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$
$\displaystyle(\mathtt{R}^{\prime},d_{\mathtt{R}},g_{\mathtt{R}})$
$\displaystyle=\mathrm{norm}(\mathtt{R})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}}\cup f(d_{\mathtt{R}})$ $\displaystyle
g_{\mathtt{P}}$ $\displaystyle=g_{\mathtt{Q}}\cup g_{\mathtt{R}}$
$\displaystyle f$ $\displaystyle=\mathrm{cr}(d_{\mathtt{Q}},d_{\mathtt{R}})$

Note that $f$ is a renaming that ensure that the normalizations of Q and R use
the same common domain variables when they are combained.

  4. 4.

If P is Q MINUS R, then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{Q^{\prime}\;MINUS}\;f(\mathtt{R}^{\prime}),d_{\mathtt{P}},g_{\mathtt{P}})$,
where:

$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$
$\displaystyle(\mathtt{R}^{\prime},d_{\mathtt{R}},g_{\mathtt{R}})$
$\displaystyle=\mathrm{norm}(\mathtt{R})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}}$ $\displaystyle g_{\mathtt{P}}$
$\displaystyle=g_{\mathtt{Q}}\cup g_{\mathtt{R}}$ $\displaystyle f$
$\displaystyle=\mathrm{cr}(d_{\mathtt{Q}},d_{\mathtt{R}}).$

The function $f$ is a renaming that ensures that the variables used in the
variables that are common in domains of the normalizations of Q and R are
renamed to the the same fresh variables.

Note that variables that are in
$\mathrm{dom}(\mathtt{R})\setminus\mathrm{dom}(\mathtt{Q})$ are replaced with
fresh variables that are not included in the domains of $d_{\mathtt{P}}$ and
$g_{\mathtt{P}}$. Thus, they are assumed local.

  5. 5.

If P is GRAPH u {Q} where u is an IRI, then $\mathrm{norm}(\mathtt{P})$ is
$(\text{\tt GRAPH u {Q${}^{\prime}$}},d,g)$, where
$\mathrm{norm}(\mathtt{Q})=(\mathtt{Q}^{\prime},d,g)$.

  6. 6.

If P is GRAPH ?x {Q}, then $\mathrm{norm}(\mathtt{P})$ is $(\text{\tt GRAPH
$x$ {Q${}^{\prime}$}},d_{\mathtt{P}},g_{\mathtt{P}})$, where:

$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=\left\\{\begin{array}[]{ll}d_{\mathtt{Q}}&\text{if
\tt?x}\in\mathrm{range}(d)\\\
d_{\mathtt{Q}}\cup\\{x\mapsto\text{\tt?x}\\}&\text{otherwise ($x$ is
fresh)}\end{array}\right.$ $\displaystyle g_{\mathtt{P}}$
$\displaystyle=g_{\mathtt{Q}}.$

  7. 7.

If P is SERVICE u {Q} where u is an IRI, then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d,g)$, where
$\mathrm{norm}(\mathtt{Q})=(\mathtt{Q}^{\prime},d,g)$ and
$\mathtt{P}^{\prime}=\text{\tt SERVICE u {Q${}^{\prime}$}}$.

  8. 8.

If P is Q FILTER (C), then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$ where:

$\displaystyle\mathrm{P}^{\prime}$ $\displaystyle=\text{\tt Q${}^{\prime}$
FILTER ($f(\mathtt{C}^{\prime})$)},$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q}),$
$\displaystyle(\mathtt{C}^{\prime},\varnothing,g_{\mathtt{C}})$
$\displaystyle=\mathrm{norm}(\mathtt{C}),$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}},$ $\displaystyle g_{\mathtt{P}}$
$\displaystyle=g_{\mathtt{Q}}\cup f(g_{\mathtt{C}}),$ $\displaystyle f$
$\displaystyle=\mathrm{cr}(d_{\mathtt{Q}},d_{\mathtt{C}}).$

  9. 9.

If P is VALUES (X) {B} where X is a list of variables and B is a list of
bindings to the variables, then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d,\varnothing)$, where $d$ has a binding
$x\mapsto\text{\tt?x}$ for each variable ?x in X and
$\mathtt{P^{\prime}}=d^{-1}(\mathtt{P})$.

  10. 10.

If P is Q BIND (E AS ?x) then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$ where:

$\displaystyle\mathrm{P}^{\prime}$ $\displaystyle=\text{\tt Q${}^{\prime}$
BIND ($f(\mathtt{E}^{\prime})$ AS $x$)}$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$
$\displaystyle(\mathtt{E}^{\prime},\varnothing,g_{\mathtt{E}})$
$\displaystyle=\mathrm{norm}(\mathtt{E})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}}\cup\\{x\mapsto\text{\tt?x}\\},$ $\displaystyle
g_{\mathtt{P}}$ $\displaystyle=g_{\mathtt{Q}}\cup f(g_{\mathtt{E}}),$
$\displaystyle f$ $\displaystyle=\mathrm{cr}(d_{\mathtt{Q}},d_{\mathtt{E}}).$

  11. 11.

If P is an expression and $\\{\mathtt{Q}_{1},\dots\mathtt{Q}_{n}\\}$ is the
set of graph patterns that are directely contained into maximal occurrences of
EXITS clauses in P (we say that an EXITS clause occurrence $i$ is maximal in P
if does not occur another EXITS clause $j$ containing $i$ in P). Then
$\mathrm{norm}(\mathtt{P})$ is $(\mathtt{P}_{n},\varnothing,g_{n})$ computed
recursively as follows:

    1. (a)

Let $\mathtt{P}_{0}$ be P and $g_{0}$ be the function that include a binding
$x\mapsto\text{\tt?x}$ for every variable ?x in P that does not occur in any
of the graph patterns $\\{\mathtt{Q}_{1},\dots\mathtt{Q}_{n}\\}$.

    2. (b)

For each $\mathtt{Q}_{k}$ of the graph patterns in the maximal EXISTS clauses,
let $(\mathtt{Q}^{\prime}_{k},d^{\prime}_{k},g^{\prime}_{k})$ be
$\mathrm{norm}(\mathtt{Q}_{k})$. Then, let $\mathtt{P}_{k}$ the result of
replacing in $\mathtt{P}_{k-1}$ the occurrence of $\mathtt{Q}_{k}$ by
$f(\mathtt{Q}_{k})\,F_{x_{1}y_{1}}\dots F_{x_{m}y_{m}}$ where:

$\displaystyle f$ $\displaystyle=\mathrm{cr}(g_{0},g^{\prime}_{k}),$
$\displaystyle g_{k}$ $\displaystyle=g_{k-1}\cup f(g^{\prime}_{k})\cup
h(d^{\prime}_{k})$

and $h$ be a function $\\{y_{1}\mapsto x_{1},\dots,y_{m}\mapsto x_{m}\\}$ that
has a binding $y\mapsto x$ for each binding $x\mapsto\text{\tt?x}$ in
$d^{\prime}_{k}$.

###  4.7 Semantics S3

In the rules 2 and 4, the semantics S2 assumes that pattern occurrences that
are not in the domain of a graph pattern are local, so they are not included
in the global bindings. On the contrary, S3 assumes that they are global, so
the query is modified to move variables from graph occurrences to expression
occurrences using operations $F_{xy}$. After this transformation, substitution
can be applied in the same way that in semantics S2.

######  Definition 10 (Normalization in S3).

Given a graph pattern or expression P, then the normalization of P is computed
using the same rules enumerated in the definition of the normalization of S3,
except the rules 2 and 4, that are replaced with the following rules:

  1. 2.

If P is SELECT X WHERE {Q} (where X is a list of variables), then
$\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$, where:

$\displaystyle\mathtt{P}^{\prime}$ $\displaystyle=\text{\tt SELECT
X${}^{\prime}$ WHERE {Q${}^{\prime}\,F_{x_{1}y_{1}}\dots F_{x_{m}y_{m}}$}}$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}|\mathrm{dom}(\mathtt{P})}$ $\displaystyle
g_{\mathtt{P}}$ $\displaystyle=g_{\mathtt{Q}}\cup
h(d_{\mathtt{Q}|\mathrm{dom}(\mathtt{Q})\setminus\mathrm{dom}(\mathtt{P})})$
$\displaystyle\mathtt{X}^{\prime}$
$\displaystyle=d_{\mathtt{P}}^{-1}(\mathtt{X})$

and $h$ is a function $\\{y_{1}\mapsto x_{1},\dots,y_{m}\mapsto x_{m}\\}$ that
has a binding $y\mapsto x$ for each binding $x\mapsto\text{\tt?x}$ in
$d_{\mathtt{Q}|\mathrm{dom}(\mathtt{Q})\setminus\mathrm{dom}(\mathtt{P})}$.

  2. 4.

If P is Q MINUS R, then $\mathrm{norm}(\mathtt{P})$ is
$(\mathtt{P}^{\prime},d_{\mathtt{P}},g_{\mathtt{P}})$ where:

$\displaystyle\mathtt{P}^{\prime}$ $\displaystyle=\text{\tt Q${}^{\prime}$
MINUS {$f(\mathtt{R}^{\prime})$ $F_{x_{1}y_{1}}\dots F_{x_{m}y_{m}}$)}}$
$\displaystyle(\mathtt{Q}^{\prime},d_{\mathtt{Q}},g_{\mathtt{Q}})$
$\displaystyle=\mathrm{norm}(\mathtt{Q})$
$\displaystyle(\mathtt{R}^{\prime},d_{\mathtt{R}},g_{\mathtt{R}})$
$\displaystyle=\mathrm{norm}(\mathtt{R})$ $\displaystyle d_{\mathtt{P}}$
$\displaystyle=d_{\mathtt{Q}}$ $\displaystyle g_{\mathtt{P}}$
$\displaystyle=g_{\mathtt{Q}}\cup g_{\mathtt{R}}\cup
h(d_{\mathtt{R}|\mathrm{dom}(\mathtt{R})\setminus\mathrm{dom}(\mathtt{P})})$
$\displaystyle f$ $\displaystyle=\mathrm{cr}(d_{\mathtt{Q}},d_{\mathtt{R}})$

and $h$ is a function $\\{y_{1}\mapsto x_{1},\dots,y_{m}\mapsto x_{m}\\}$ that
has a binding $y\mapsto x$ for each binding $x\mapsto\text{\tt?x}$ in
$d_{\mathtt{R}|\mathrm{dom}(\mathtt{R})\setminus\mathrm{dom}(\mathtt{P})}$.

##  5 Substitution and blank nodes

Peter F. Patel-Schneider noticed in the W3C mailing list of SPARQL that
substitution has problems with blank nodes and a semantics where every
variable can be substituted. Let P be the inner graph pattern of a query and
?x be a variable that can be substituted in P, in particular with a blank node
_:b. Then, there are the following options:

  1. 1.

?x occurs in a basic graph pattern and is substituted by _:b. Then, according
the specification _:b is interpreted as an existential variable and scoped to
the basic graph pattern. Thus, _:b may represent any element on the graph, not
only _:b.

  2. 2.

?x is in an expression occurrence. Then, the substitution of ?x by _:b
restricts the resulting bindings to whose where ?x is bound to _:b.

  3. 3.

?x is in the domain of P. Then, results of P that are not compatible with
$\\{\text{\tt?x}\mapsto\text{\tt\\_:b}\\}$ are discarded.

The first case results contradictory with the other two. In fact, it does not
restrict the variable ?x as the other do (and as it is expected for
substitution).

In the semantics S3 proposed in this technical report a variable ?x occurring
in a pattern occurrence is considered replaceable with values that come from
the current solution mapping. However, before this substitution the
normalization process moves ?x from the pattern occurrence to an expression
occurrence using a renaming of ?x to ?y and then using an operator
$F_{\text{\tt?x?y}}$. Thus, we can conclude the following lemma:

######  Lemma 4.

The semantics S1, S2 and S3 are safe respect with the blank nodes substitution
issue.

##  6 Correlation in implementations

This section presents examples of how the proposed semantics work and how
different implementations match them. Queries presented in this section are
run against the RDF graph depicted in Figure 1.

For each query, the actual results given by each implementation is shown at
the end of the section.

### Example 1

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { ?child :parent
?parent })}This query gets people of country :j having children. That is,
select people that has solutions for the inner query. The variable ?people is
in-domain in the inner graph pattern for all semantics. Thus, the results of
inner graph pattern are filtered to be compatible with solutions of the outer
query $\mu_{a}$ and $\mu_{b}$. The only solution that has results for the
inner graph pattern is $\mu_{b}$ in each of the three semantics S1, S2 and S3.

### Example 2

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?parent }})}This query is similar to the presented in
Example 1. However, in this case the variable ?parent in the inner query is in
local according with S1 and S2, and global according with S3. Thus, the
solutions are $\\{\mu_{a},\mu_{b}\\}$ for S1 and S2. On the other hand, the
result is $\\{\mu_{b}\\}$ for S3.

### Example 3

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?chparent FILTER (?chparent = ?parent) }})}This query
is similar to the presented in the previous examples. However, in this case
the variable ?parent in the inner query is global according with S2 and S3,
and local according with S1. Thus, the solutions are $\\{\mu_{b}\\}$ for S2
and S3. On the other hand, the result is $\\{\\}$ for S1. Indeed, the filter
condition ?chparent = ?parent gets an error, because ?parent is unbound .

### Example 4

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?chparent FILTER (bound(?parent)) }})}This query checks
if the variable ?parent is bound in the inner sub-select with the build-in
function bound(?parent). Thus, this query returns $\\{\mu_{a},\mu_{b}\\}$ in
S2 and S3 and returns $\\{\\}$ in S1.

## Example 5

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?chparent FILTER (?chparent = ?parent &&
bound(?parent)) }})}This query is equivalent to the query of Example 3
according the studied semantics. The addition of the condition bound(?parent)
must not affect the result.

### Example 6

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
?chparent WHERE { ?child :parent ?chparent FILTER (?parent = 1 || ?parent != 1
)}})}In this example, the filter clause ?parent = 1 || ?parent != 1 is a
tautology when ?parent is bound. Otherwise, both sides of the disjunction are
evaluated as error so the whole clause gets an error. Thus, the output of this
query is $\\{\mu_{a},\mu_{b}\\}$ according S2 and S3 and $\\{\\}$ according
S1.

### Example 7

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT * WHERE {
?child :parent ?chparent FILTER (?parent = 1 || ?parent != 1 )}})}This example
is equivalent with Example 6. In fact, the semantics of the wildcard ‘*’ is
the list of all variables that are in-domain of the query.

### Example 8

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?parent FILTER (?parent = :c)}})}In this query the
variable ?parent has three occurrences. The first is in the outer graph
pattern and the other two in the inner graph pattern. In any of the semantics
?parent is bound to :a and :b in the solutions of the outer graph pattern.

According S2 and S3 the variable ?parent is local in the inner graph pattern.
Thus it is bound to :a, :b and :c in the inner graph pattern. Then, the filter
clause of the inner graph pattern is true for :c. Thus, the result of this
query is $\\{\mu_{a},\mu_{b}\\}$.

On the other hand, according S3 the variable ?parent is global in the inner
graph pattern. So, it is replaced with the values comming from the outer graph
pattern. None of this values satisfy the condition ?parent = :c. Thus, the
result of this query is $\\{\\}$.

### Example 9

SELECT ?parentWHERE { ?parent :country :j FILTER ( EXISTS { SELECT ?child
WHERE { ?child :parent ?parent FILTER (EXISTS{?parent :parent :d})}})}On the
dataset used in these examples, This query seems to be equivalent to the
previous query (presented in Example 8), because the graph pattern ?parent
:parent :d only has solutions if ?parent is :c. Thus, in S2 and S3 the result
of this query is $\\{\\}$. On the other hand, in S1 the result of this query
is $\\{\mu_{a},\mu_{b}\\}$.

### Example 10

SELECT *WHERE { { { ?x :p ?y } OPTIONAL { ?y :q ?z } } FILTER ( EXISTS { ?z :r
?v } ) }Consider the following RDF graph that is the dataset $D$ where we will
evaluate this query.

:a:b:c:d:e:f:g:h:i:p:q:r:p:q:p Figure 2: RDF graph.

The normalization of the inner graph pattern gives the same result in the
three semantics, because the variables ?z and ?v are in the domain of the
inner graph pattern. Thus, the evaluation of this query is the set $\Omega$
defined as:

$\Omega=\\{\mu\in\llbracket\mathtt{P}\rrbracket_{D}\mid\llbracket\mathtt{Q}\rrbracket_{D}\Join\\{\mu\\}\text{
is not empty}\\},$

where P and Q are the outer and inner graph patterns, respectively.
$\llbracket\mathtt{P}\rrbracket_{D}$ and $\llbracket\mathtt{Q}_{D}\rrbracket$
are respectively the sets
$\\{\mu_{\mathtt{abc}},\mu_{\mathtt{efg}},\mu_{\mathtt{hi}}\\}$ and
$\\{\mu_{\mathtt{cd}}\\}$ where:

$\displaystyle\mu_{\mathtt{abc}}$
$\displaystyle=\\{\text{\tt?x}\mapsto\text{\tt:a},\text{\tt?y}\mapsto\text{\tt:b},\text{\tt?z}\mapsto\text{\tt:c}\\},$
$\displaystyle\mu_{\mathtt{efg}}$
$\displaystyle=\\{\text{\tt?x}\mapsto\text{\tt:e},\text{\tt?y}\mapsto\text{\tt:f},\text{\tt?z}\mapsto\text{\tt:g}\\},$
$\displaystyle\mu_{\mathtt{hi}}$
$\displaystyle=\\{\text{\tt?x}\mapsto\text{\tt:h},\text{\tt?y}\mapsto\text{\tt:i}\\},$
$\displaystyle\mu_{\mathtt{cd}}$
$\displaystyle=\\{\text{\tt?z}\mapsto\text{\tt:c},\text{\tt?v}\mapsto\text{\tt:d}\\}.$

Thus, $\Omega=\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$.

### Summary

The following table summarizes the results that the example queries get for
each of the studied semantics and the results that the studied implementations
actually output.

# | S1 | S2 | S3 | rdf4j | Virtuoso | Fuseki | Blazegraph
---|---|---|---|---|---|---|---
1 | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$
2 | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$
3 | $\\{\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$
4 | $\\{\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$ | $\\{\\}$
5 | $\\{\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$
6 | $\\{\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$
7 | $\\{\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\\}$
8 | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$
9 | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\\}$ | $\\{\\}$ | $\\{\\}$ | $\\{\mu_{a},\mu_{b}\\}$ | $\\{\mu_{a},\mu_{b}\\}$
10 | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$ | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$ | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$ | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$ | $\\{\mu_{\mathtt{abc}}\\}$ | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$ | $\\{\mu_{\mathtt{abc}},\mu_{\mathtt{hi}}\\}$

We distinguish two groups of implementations. Blazegraph and Fuseki match S1
and Virtuoso and rdf4j matche S3. However, only Blazegraph and rdf4j match
their respectively semantics in all the examples.

Fuseki agree with S1 except in the query of Example 7 with . The queries in
the examples 6 and 7 are equivalent. However, in Fuseki the results differ.
This seems as a bug of Fuseki.

Virtuoso agree with S3 except in the queries of examples 4, 8 and 10. The
result given in the query 4 seems as a bug, because it is contradictory that
?parent is unbound when it is bound in query 5. The result given in the query
8 require more study because it is not clear if it is a bug or it is motivated
by a different interpretation of the correlation. The result given in the
query 10 shows that there are an special treatment with unbound variables.


# OpenBox: A Python Toolkit for Generalized Black-box Optimization

Huaijun Jiang1∗<EMAIL_ADDRESS>
Yu Shen1∗<EMAIL_ADDRESS>
Yang Li2∗<EMAIL_ADDRESS>
Beicheng Xu1<EMAIL_ADDRESS>
Sixian Du1<EMAIL_ADDRESS>
Wentao Zhang1<EMAIL_ADDRESS>
Ce Zhang3<EMAIL_ADDRESS>
Bin Cui1<EMAIL_ADDRESS>
1 School of Computer Science, Peking University, Beijing, China
2 Department of Data Platform, TEG, Tencent Inc., China
3 Department of Computer Science, ETH Zürich, Switzerland
∗ Equal contribution.

###### Abstract

Black-box optimization (BBO) has a broad range of applications, including
automatic machine learning, experimental design, and database knob tuning.
However, users still face challenges when applying BBO methods to their
problems at hand with existing software packages in terms of applicability,
performance, and efficiency. This paper presents OpenBox, an open-source BBO
toolkit with improved usability. It implements user-friendly inferfaces and
visualization for users to define and manage their tasks. The modular design
behind OpenBox facilitates its flexible deployment in existing systems.
Experimental results demonstrate the effectiveness and efficiency of OpenBox
over existing systems. The source code of OpenBox is available at
https://github.com/PKU-DAIR/open-box.

Keywords: Python, Black-box Optimization, Bayesian Optimization, Hyper-
parameter Optimization

##  1 Introduction

Black-box optimization (BBO) (Muñoz et al., 2015) deals with optimizing an
objective function under limited budget for function evaluation. However,
since the evaluation of objective function is usually expensive, the goal of
BBO is to find a configuration that approaches the optimal configuration as
soon as possible. Recently, generalized BBO has attracted great attraction in
various areas (Foster et al., 2019; Belakaria et al., 2020; Sun et al., 2022b,
a), which requires more functionalities than traditional BBO tasks.
Specifically, traditional BBO refers to BBO with integer or float input
parameters and with only a single objective, while there can be various input
types (e.g. ordinal and categorical), multiple objectives, and constraints in
generalized BBO. Though many softwares and platforms have been developed for
traditional BBO (Hutter et al., 2011; Bergstra et al., 2011; Golovin et al.,
2017; Akiba et al., 2019; Balandat et al., 2020; Lindauer et al., 2022), so
far, there is no platform specifically designed to target generalized BBO.
Existing platforms suffer from the following limitations when applied to
generalized BBO scenarios: 1) Restricted application scope. Many existing BBO
platforms cannot support multiple objectives and constraints, and they cannot
support categorical parameters. 2) Unstable performance across problems. Many
platforms only implement one or very few BBO algorithms. According to the “no
free lunch” theorem (Ho and Pepyne, 2001), this would inevitably lead to
unstable performance when applied to various problems. 3) Limited scalability
and efficiency. Most platforms execute optimization in a sequential manner,
which is inefficient and unscalable.

This paper proposes OpenBox to address the above limitations simultaneously.
OpenBox has the following crucial features: 1) Generality. OpenBox hosts most
state-of-the-art optimization algorithms, and is capable of handling BBO tasks
with different requirements. 2) Ease of use. OpenBox provides user-friendly
interfaces, visualization and automatic decisions on algorithms. Users can
conveniently define their tasks via either wrapped services or ask-and-tell
interfaces. 3) State-of-the-art performance.  Extensive experiments show that
OpenBox outperforms the existing systems on a wide range of BBO tasks.

So far, OpenBox has helped researchers solve various realistic BBO problems
like database tuning (Kanellis et al., 2022; Zhang et al., 2022c) and traffic
simulation (Liang et al., 2022). It has also performed as the core part in
open-source graph learning system SGL (Zhang et al., 2022a) and database
tuning system DBTune (Zhang et al., 2022b). Besides the academic usages,
OpenBox won the first place in CIKM 2021 AnalytiCup Track 2 (Jiang et al.,
2021), and parts of the toolkit have been successfully deployed in
corporations like Tencent and ByteDance (Shen et al., 2023).

Figure 1: Simplified overview of supported scenarios and built-in algorithms
in OpenBox.

##  2 Functionality Overview

As shown in Figure 1, OpenBox implements a wide range of state-of-the-art
algorithms to tackle various BBO problems. Concretely, OpenBox is capable of
handling BBO problems with different number of objectives (Belakaria and
Deshwal, 2019; Belakaria et al., 2020) and constraints (Sui et al., 2015), and
the optimization procedure can either be sequential or parallel (González et
al., 2016). To ensure stable performance in different scenarios, OpenBox
implements variants of Bayesian optimization (Hutter et al., 2011; Bergstra et
al., 2011; Snoek et al., 2012), evolutionary algorithms (Storn and Price,
1997; Deb et al., 2002; Jin, 2011), and other competitive methods like CMA-ES
(Hansen et al., 2003).

While it may be challenging for users to choose the proper algorithm for
different scenarios, OpenBox also provides automatic decisions on algorithms
and settings according to the characteristic of the incoming task. The
decisions are based on experimental analysis (Eggensperger et al., 2013) or
practical experience. For example, if there are over 50 parameters in the
input space, or the number of trials exceeds 300, we choose Probabilistic
Random Forest (PRF) (Hutter et al., 2011) instead of Gaussian Process (GP) as
the surrogate to avoid incompatibility or high computational complexity in
Bayesian optimization.

##  3 System Design

In this section, we will introduce the system design of OpenBox. As shown in
the upper left corner of Figure 2, the core of the optimization framework is
Optimizer, which takes an objective function and a search space as inputs,
executes the optimization process, and outputs the final results. Optimizer
consists of three main components – Advisor, Executor, and Visualizer. Advisor
implements the optimization algorithms described in Section 2 and suggests new
configurations based on provided search space and stored optimization history.
Executor then runs the objective function on the recommended configurations
and returns the results, i.e. observations. To monitor the optimization
process, Visualizer provides comprehensive visualization APIs for users,
including the convergence curve, parameter importance analysis based on SHAP
(Lundberg and Lee, 2017), etc. For multi-objective problems, Pareto front and
Hypervolume charts are also available. An example of the convergence curve is
provided on the bottom left of Figure 2, where the best-observed
configurations during optimization are connected by a blue line.

Figure 2: System overview of OpenBox, including the system architecture (upper
left), an example of the ask-and-tell interface using Advisor (right), and an
example of visualization interfaces (bottom left).

For ease of use, OpenBox also provides the ask-and-tell interface using
Advisor. The example code is shown on the right side of Figure 2. Users first
build an Advisor based on the search space (Line 4-5). Next, users run
optimization by interacting with the Advisor (Line 8-16). Concretely, users
get a configuration suggestion from Advisor (Line 10) and evaluate the
performance of the configuration by themselves (Line 12). Users then build an
Observation that contains the evaluation result (Line 14) and update the
Observation to Advisor (Line 16). Finally, an HTML page for visualization is
generated based on the optimization history obtained from Advisor (Line
19-20). This ask-and-tell interface is compatible with various types of
optimization algorithms and enables users to make flexible modifications to
the optimization process.

##  4 Benchmark

(a) CONSTR (2 objectives, 2 constraints)

(b) LightGBM on 24 OpenML datasets

Figure 3: Performance comparison on constrained multi-objective benchmark
CONSTR (left) and LightGBM tuning task (right).

To demonstrate the generality and efficiency of OpenBox, we conduct
experiments on the constrained multi-objective benchmark CONSTR and the
LightGBM (Ke et al., 2017) tuning task on 24 OpenML datasets (Feurer et al.,
2021). We report the Hypervolume difference from the optimum in the CONSTR
benchmark and the performance rank of the best-achieved accuracy in the
LightGBM tuning task. In Figure 3(a), we observe that OpenBox outperforms the
other baselines in terms of convergence speed and stability. In Figure 3(b),
we observe that OpenBox outperforms the other competitive systems, achieves a
median rank of 1.25, and ranks first in 12 out of 24 datasets.

##  5 Conclusion

This paper presents OpenBox, an open-source system for solving generalized BBO
tasks. OpenBox hosts a wide range of state-of-the-art optimization algorithms
and provides user-friendly interfaces along with comprehensive visualization
functions. Evaluations showcase the excellent performance of OpenBox over
existing systems. The recent released version 0.8.2 has been tested on Linux,
macOS, and Windows, and can be installed easily via PyPI by ‘pip install
openbox’. The source code of OpenBox is now available at
https://github.com/PKU-DAIR/open-box. More detailed examples, APIs, and
advanced usages can be found in our documentation111https://open-
box.readthedocs.io/.

Acknowledgments

We thank all contributors to this project. This work is supported by the
National Natural Science Foundation of China (NSFC) (No. 61832001 and
U22B2037).

## References

  * Aguilar Melgar et al. (2021) Leonel Aguilar Melgar, David Dao, Shaoduo Gan, Nezihe M Gürel, Nora Hollenstein, Jiawei Jiang, Bojan Karlaš, Thomas Lemmin, Tian Li, Yang Li, et al.  Ease. ml: A lifecycle management system for machine learning.  In _11th Annual Conference on Innovative Data Systems Research (CIDR 2021)(virtual)_. CIDR, 2021.
  * Akiba et al. (2019) Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama.  Optuna: A next-generation hyperparameter optimization framework.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 2623–2631, 2019.
  * Azizi et al. (2010) Omid Azizi, Aqeel Mahesri, Benjamin C Lee, Sanjay J Patel, and Mark Horowitz.  Energy-performance tradeoffs in processor architecture and circuit design: a marginal cost analysis.  _ACM SIGARCH Computer Architecture News_ , 38(3):26–36, 2010.
  * Balandat et al. (2020) Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Samuel Daulton, Benjamin Letham, Andrew Gordon Wilson, and Eytan Bakshy.  BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization.  In _NeurIPS_ , 2020.
  * Baptista and Poloczek (2018) Ricardo Baptista and Matthias Poloczek.  Bayesian optimization of combinatorial structures.  In _International Conference on Machine Learning_ , pages 462–471. PMLR, 2018.
  * Belakaria and Deshwal (2019) Syrine Belakaria and Aryan Deshwal.  Max-value entropy search for multi-objective bayesian optimization.  In _International Conference on Neural Information Processing Systems (NeurIPS)_ , 2019.
  * Belakaria et al. (2020) Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa.  Uncertainty-aware search framework for multi-objective bayesian optimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 10044–10052, 2020.
  * Bergstra and Bengio (2012) James Bergstra and Yoshua Bengio.  Random search for hyper-parameter optimization.  _Journal of machine learning research_ , 13(2), 2012.
  * Bergstra et al. (2011) James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.  Algorithms for hyper-parameter optimization.  In _Advances in neural information processing systems_ , pages 2546–2554, 2011.
  * Chen et al. (2018) Yutian Chen, Aja Huang, Ziyu Wang, Ioannis Antonoglou, Julian Schrittwieser, David Silver, and Nando de Freitas.  Bayesian optimization in alphago.  _arXiv preprint arXiv:1812.06855_ , 2018.
  * Deb et al. (2002) Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  _IEEE transactions on evolutionary computation_ , 6(2):182–197, 2002.
  * Domhan et al. (2015) Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter.  Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves.  In _Twenty-fourth international joint conference on artificial intelligence_ , 2015.
  * Eggensperger et al. (2013) Katharina Eggensperger, Matthias Feurer, Frank Hutter, James Bergstra, Jasper Snoek, Holger Hoos, Kevin Leyton-Brown, et al.  Towards an empirical foundation for assessing bayesian optimization of hyperparameters.  In _NIPS workshop on Bayesian Optimization in Theory and Practice_ , volume 10, 2013.
  * Eggensperger et al. (2015) Katharina Eggensperger, Frank Hutter, Holger Hoos, and Kevin Leyton-Brown.  Efficient benchmarking of hyperparameter optimizers via surrogates.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 29, 2015.
  * Eriksson and Poloczek (2021) David Eriksson and Matthias Poloczek.  Scalable constrained bayesian optimization.  In _International Conference on Artificial Intelligence and Statistics_ , pages 730–738. PMLR, 2021.
  * Falkner et al. (2018) Stefan Falkner, Aaron Klein, and Frank Hutter.  Bohb: Robust and efficient hyperparameter optimization at scale.  In _International Conference on Machine Learning_ , pages 1437–1446. PMLR, 2018.
  * Feurer et al. (2018) Matthias Feurer, Benjamin Letham, and Eytan Bakshy.  Scalable meta-learning for bayesian optimization using ranking-weighted gaussian process ensembles.  In _AutoML Workshop at ICML_ , volume 7, 2018.
  * Feurer et al. (2021) Matthias Feurer, Jan N van Rijn, Arlind Kadra, Pieter Gijsbers, Neeratyoy Mallik, Sahithya Ravi, Andreas Müller, Joaquin Vanschoren, and Frank Hutter.  Openml-python: an extensible python api for openml.  _Journal of Machine Learning Research_ , 22(100):1–5, 2021.
  * Foster et al. (2019) Adam Foster, Martin Jankowiak, Eli Bingham, Paul Horsfall, Yee Whye Teh, Tom Rainforth, and Noah Goodman.  Variational bayesian optimal experimental design.  _arXiv preprint arXiv:1903.05480_ , 2019.
  * Franceschi et al. (2017) Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil.  Forward and reverse gradient-based hyperparameter optimization.  In _International Conference on Machine Learning_ , pages 1165–1173. PMLR, 2017.
  * Gardner et al. (2014) Jacob R Gardner, Matt J Kusner, Zhixiang Eddie Xu, Kilian Q Weinberger, and John P Cunningham.  Bayesian optimization with inequality constraints.  In _ICML_ , volume 2014, pages 937–945, 2014.
  * Gijsbers et al. (2019) Pieter Gijsbers, Erin LeDell, Janek Thomas, Sébastien Poirier, Bernd Bischl, and Joaquin Vanschoren.  An open source automl benchmark.  _arXiv preprint arXiv:1907.00909_ , 2019.
  * Golovin et al. (2017) Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and David Sculley.  Google vizier: A service for black-box optimization.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pages 1487–1495, 2017.
  * González et al. (2016) Javier González, Zhenwen Dai, Philipp Hennig, and Neil Lawrence.  Batch bayesian optimization via local penalization.  In _Artificial intelligence and statistics_ , pages 648–657. PMLR, 2016.
  * Griffiths and Hernández-Lobato (2020) Ryan-Rhys Griffiths and José Miguel Hernández-Lobato.  Constrained bayesian optimization for automatic chemical design using variational autoencoders.  _Chemical science_ , 11(2):577–586, 2020.
  * Hansen et al. (2003) Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos.  Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es).  _Evolutionary computation_ , 11(1):1–18, 2003.
  * Hernández-Lobato et al. (2015) José Miguel Hernández-Lobato, Michael Gelbart, Matthew Hoffman, Ryan Adams, and Zoubin Ghahramani.  Predictive entropy search for bayesian optimization with unknown constraints.  In _International conference on machine learning_ , pages 1699–1707. PMLR, 2015.
  * Hernández-Lobato et al. (2016) José Miguel Hernández-Lobato, Michael A Gelbart, Ryan P Adams, Matthew W Hoffman, and Zoubin Ghahramani.  A general framework for constrained bayesian optimization using information-based search.  2016\.
  * Ho and Pepyne (2001) Yu-Chi Ho and David L Pepyne.  Simple explanation of the no free lunch theorem of optimization.  In _Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No. 01CH37228)_ , volume 5, pages 4409–4414. IEEE, 2001.
  * Hutter et al. (2011) Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _International Conference on Learning and Intelligent Optimization_ , pages 507–523. Springer, 2011.
  * Hutter et al. (2014) Frank Hutter, Holger Hoos, and Kevin Leyton-Brown.  An efficient approach for assessing hyperparameter importance.  In _International conference on machine learning_ , pages 754–762. PMLR, 2014.
  * Hutter et al. (2019) Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren.  _Automated machine learning: methods, systems, challenges_.  Springer Nature, 2019.
  * Imani et al. (2019) Mahdi Imani, Seyede Fatemeh Ghoreishi, Douglas Allaire, and Ulisses M Braga-Neto.  Mfbo-ssm: Multi-fidelity bayesian optimization for fast inference in state-space models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7858–7865, 2019.
  * Jiang et al. (2021) Huaijun Jiang, Yu Shen, and Yang Li.  Automated hyperparameter optimization challenge at cikm 2021 analyticcup.  _arXiv preprint arXiv:2111.00513_ , 2021.
  * Jin (2011) Yaochu Jin.  Surrogate-assisted evolutionary computation: Recent advances and future challenges.  _Swarm and Evolutionary Computation_ , 1(2):61–70, 2011.
  * Kanellis et al. (2022) Konstantinos Kanellis, Cong Ding, Brian Kroth, Andreas Müller, Carlo Curino, and Shivaram Venkataraman.  Llamatune: sample-efficient dbms configuration tuning.  _Proceedings of the VLDB Endowment_ , 15(11):2953–2965, 2022.
  * Ke et al. (2017) Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu.  Lightgbm: A highly efficient gradient boosting decision tree.  _Advances in neural information processing systems_ , 30, 2017.
  * Knudde et al. (2017) Nicolas Knudde, Joachim van der Herten, Tom Dhaene, and Ivo Couckuyt.  GPflowOpt: A Bayesian Optimization Library using TensorFlow.  _arXiv preprint – arXiv:1711.03845_ , 2017.
  * Koch et al. (2018) Patrick Koch, Oleg Golovidov, Steven Gardner, Brett Wujek, Joshua Griffin, and Yan Xu.  Autotune: A derivative-free optimization framework for hyperparameter tuning.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 443–452, 2018.
  * Li et al. (2017) Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _The Journal of Machine Learning Research_ , 18(1):6765–6816, 2017.
  * Li et al. (2020) Yang Li, Jiawei Jiang, Jinyang Gao, Yingxia Shao, Ce Zhang, and Bin Cui.  Efficient automatic cash via rising bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 4763–4771, 2020.
  * Li et al. (2021a) Yang Li, Yu Shen, Jiawei Jiang, Jinyang Gao, Ce Zhang, and Bin Cui.  Mfes-hb: Efficient hyperband with multi-fidelity quality measurements.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 8491–8500, 2021a.
  * Li et al. (2021b) Yang Li, Yu Shen, Wentao Zhang, Yuanwei Chen, Huaijun Jiang, Mingchao Liu, Jiawei Jiang, Jinyang Gao, Wentao Wu, Zhi Yang, et al.  Openbox: A generalized black-box optimization service.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 3209–3219, 2021b.
  * Liang et al. (2022) Chumeng Liang, Zherui Huang, Yicheng Liu, Zhanyu Liu, Guanjie Zheng, Hanyuan Shi, Yuhao Du, Fuliang Li, and Zhenhui Li.  Cblab: Scalable traffic simulation with enriched data supporting.  _arXiv preprint arXiv:2210.00896_ , 2022.
  * Liberty et al. (2020) Edo Liberty, Zohar Karnin, Bing Xiang, Laurence Rouesnel, Baris Coskun, Ramesh Nallapati, Julio Delgado, Amir Sadoughi, Yury Astashonok, Piali Das, et al.  Elastic machine learning algorithms in amazon sagemaker.  In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_ , pages 731–737, 2020.
  * Lindauer et al. (2022) Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Benjamins, Tim Ruhkopf, René Sass, and Frank Hutter.  Smac3: A versatile bayesian optimization package for hyperparameter optimization.  _Journal of Machine Learning Research_ , 23(54):1–9, 2022.
  * Liu et al. (2020) Sijia Liu, Parikshit Ram, Deepak Vijaykeerthy, Djallel Bouneffouf, Gregory Bramble, Horst Samulowitz, Dakuo Wang, Andrew Conn, and Alexander Gray.  An admm based framework for automl pipeline configuration.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 4892–4899, 2020.
  * Lundberg and Lee (2017) Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ , 30, 2017.
  * Močkus (1975) Jonas Močkus.  On bayesian methods for seeking the extremum.  In _Optimization techniques IFIP technical conference_ , pages 400–404. Springer, 1975.
  * Muñoz et al. (2015) Mario A Muñoz, Yuan Sun, Michael Kirley, and Saman K Halgamuge.  Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges.  _Information Sciences_ , 317:224–245, 2015.
  * Oh et al. (2018) ChangYong Oh, Efstratios Gavves, and Max Welling.  Bock: Bayesian optimization with cylindrical kernels.  In _International Conference on Machine Learning_ , pages 3868–3877. PMLR, 2018.
  * Pedregosa et al. (2011) Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  _the Journal of machine Learning research_ , 12:2825–2830, 2011.
  * Perrone et al. (2021) Valerio Perrone, Michele Donini, Muhammad Bilal Zafar, Robin Schmucker, Krishnaram Kenthapadi, and Cédric Archambeau.  Fair bayesian optimization.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 854–863, 2021.
  * Salinas et al. (2022) David Salinas, Matthias Seeger, Aaron Klein, Valerio Perrone, Martin Wistuba, and Cedric Archambeau.  Syne tune: A library for large scale hyperparameter tuning and reproducible research.  In _International Conference on Automated Machine Learning_ , pages 16–1. PMLR, 2022.
  * Sen et al. (2018) Rajat Sen, Kirthevasan Kandasamy, and Sanjay Shakkottai.  Multi-fidelity black-box optimization with hierarchical partitions.  In _International conference on machine learning_ , pages 4538–4547. PMLR, 2018.
  * Shen et al. (2023) Yu Shen, Xinyuyang Ren, Yupeng Lu, Huaijun Jiang, Huanyong Xu, Di Peng, Yang Li, Wentao Zhang, and Bin Cui.  Rover: An online spark sql tuning service via generalized transfer learning.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 4800–4812, 2023.
  * Sivaprasad et al. (2020) Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and François Fleuret.  Optimizer benchmarking needs to account for hyperparameter tuning.  In _International Conference on Machine Learning_ , pages 9036–9045. PMLR, 2020.
  * Snoek et al. (2012) Jasper Snoek, Hugo Larochelle, and Ryan P Adams.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ , 25, 2012.
  * Song et al. (2022) Xingyou Song, Sagi Perel, Chansoo Lee, Greg Kochanski, and Daniel Golovin.  Open source vizier: Distributed infrastructure and api for reliable and flexible blackbox optimization.  In _International Conference on Automated Machine Learning_ , pages 8–1. PMLR, 2022.
  * Storn and Price (1997) Rainer Storn and Kenneth Price.  Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces.  _Journal of global optimization_ , 11(4):341, 1997.
  * Sui et al. (2015) Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause.  Safe exploration for optimization with gaussian processes.  In _International conference on machine learning_ , pages 997–1005. PMLR, 2015.
  * Sun et al. (2022a) Tianxiang Sun, Zhengfu He, Hong Qian, Yunhua Zhou, Xuan-Jing Huang, and Xipeng Qiu.  Bbtv2: towards a gradient-free future with large language models.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 3916–3930, 2022a.
  * Sun et al. (2022b) Tianxiang Sun, Yunfan Shao, Hong Qian, Xuanjing Huang, and Xipeng Qiu.  Black-box tuning for language-model-as-a-service.  In _International Conference on Machine Learning_ , pages 20841–20855. PMLR, 2022b.
  * Van Aken et al. (2017) Dana Van Aken, Andrew Pavlo, Geoffrey J Gordon, and Bohan Zhang.  Automatic database management system tuning through large-scale machine learning.  In _Proceedings of the 2017 ACM International Conference on Management of Data_ , pages 1009–1024, 2017.
  * Wen et al. (2018) Zeyi Wen, Jiashuai Shi, Qinbin Li, Bingsheng He, and Jian Chen.  Thundersvm: A fast svm library on gpus and cpus.  _The Journal of Machine Learning Research_ , 19(1):797–801, 2018.
  * Zhang et al. (2022a) Wentao Zhang, Yu Shen, Zheyu Lin, Yang Li, Xiaosen Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui.  Pasca: A graph neural architecture search system under the scalable paradigm.  In _Proceedings of the ACM Web Conference 2022_ , pages 1817–1828, 2022a.
  * Zhang et al. (2022b) Xinyi Zhang, Zhuo Chang, Yang Li, Hong Wu, Jian Tan, Feifei Li, and Bin Cui.  Facilitating database tuning with hyper-parameter optimization: a comprehensive experimental evaluation.  _Proceedings of the VLDB Endowment_ , 15(9):1808–1821, 2022b.
  * Zhang et al. (2022c) Xinyi Zhang, Hong Wu, Yang Li, Jian Tan, Feifei Li, and Bin Cui.  Towards dynamic and safe configuration tuning for cloud databases.  In _Proceedings of the 2022 International Conference on Management of Data_ , pages 631–645, 2022c.