11institutetext: Université Orléans, INSA CVL, LIFO EA, Orléans, France
22institutetext: Université de Tours, LIFAT, Blois, France. 33institutetext:
Quy Nhon University, Vietnam.
33email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Querying Linked Data: how to ensure user’s quality requirements

Jacques Chabin 11 Mirian Halfeld-Ferrari 11 Béatrice Markhoff 22 Thanh Binh
Nguyen 33

###### Abstract

In the distributed and dynamic framework of the Web, data quality is a big
challenge. The Linked Open Data (LOD) provides an enormous amount of data, the
quality of which is difficult to control. Quality is intrinsically a matter of
usage, so consumers need ways to specify quality rules that make sense for
their use, in order to get only data conforming to these rules. We propose a
user-side query framework equipped with a checker of constraints and
confidence levels on data resulting from LOD providers’ query evaluations. We
detail its theoretical foundations and we provide experimental results showing
that the check additional cost is reasonable and that integrating the
constraints in the queries further improves it significantly.

###### Keywords:

Query rewriting Constraints Context Confidence degree User-side quality

##  1 Introduction

Very large knowledge bases on the web of Linked Open Data (as DBpedia, Yago or
BabelNet) need applications to help humans exploring their huge knowledge,
performing data analysis and data mining tasks. One crucial point for such
applications, and in particular for data mining algorithms, is that the data
collection and pre-processing steps have to be safe and sound.

In order to help semantic Web data mining tool designers for performing the
data collection and pre-processing steps, we propose a semantic web data
validator. The idea is to extend a query environment over semantic graph
databases with a mechanism for filtering answers according to a user
customized context. The user context is composed of (i) the view she/he has
defined on the needed semantic web data and (ii) a set of personalization
tools, such as integrity constraints and confidence degrees. Both the
constraints and the queries are expressed in terms of the user’s view of data.
Query answers are built only with data respecting a required confidence
degree. The constraint verification is triggered by a query and consists in
filtering its answers. In this way, there may be some inconsistencies within
sources, but the answers given to the user are filtered to ensure their
consistency w.r.t. her/his context.

#### Motivating example.

Let Univ be a database where : $professor(X_{id})$ and $employ-$
$eeGov(X_{id})$ indicate if a person is a professor or an employee working for
the government; $teacherOf(X_{id},X_{course})$ associates a teacher with a
course, while $takesCourse(X_{id},X_{course})$ refers to a student enrolling
in a course; $offered-$ $CourseAt(X_{course},X_{dep})$ indicates in which
department a course is taught; $re-$ $searchesIn(X_{id},X_{domain})$ and
$worksFor(X_{id},X_{dep},X_{org})$ refer to the research domain and the work
place (a department of an organization) of a person; $headOf(X_{id},Y_{dep})$
indicates the head of a department. The context depicted in Table 1 is
composed by $6$ constraints ($4$ positive, $1$ negative and $1$ EGD), namely:
($c_{P_{1}}$) every professor must offer a course; ($c_{P_{2}}$) every course
given by a teacher must be associated with a department; ($c_{P_{3}}$)
professors are government employees; ($c_{P_{4}}$) if a teacher offers a
database course, then he must be a researcher in the database domain;
($c_{N_{1}}$) nobody can teach and follow the same course; ($c_{K_{1}}$) the
head of a department in an organization cannot be a person working in a
different department.

$\hbox{${\cal C}$}_{P}$ | positive constraints
---|---
$c_{P_{1}}:$ | $professor(X_{id})\rightarrow teacherOf(X_{id},X_{course}).$
$c_{P_{2}}:$ | $teacherOf(X_{id},X_{course})\rightarrow offeredCourseAt(X_{course},X_{dep}).$
$c_{P_{3}}:$ | $professor(X_{id})\rightarrow employeeGov(X_{id}).$
$c_{P_{4}}:$ | $teacherOf(X_{id},DB)\rightarrow researchesIn(X_{id},DB).$
$\hbox{${\cal C}$}_{N}$ | negative constraints
$c_{N_{1}}:$ | $teacherOf(X_{id},X_{course}),takesCourse(X_{id},X_{course})\rightarrow\bot$
$\hbox{${\cal C}$}_{K}$ | key constraints
$c_{K_{1}}:$ | $worksFor(X_{id},X_{dep},X_{org}),headOf(X_{id},Y_{dep})\rightarrow X_{dep}=Y_{dep}$
Table 1: Set of constraints on $\mathbb{G}$

The querying system computes answers on a distributed database, where data
sources come from different providers who are not trusted equally. In Table 2,
$\tau$ indicates the accuracy associated with each provider (Source 1 is
considered to be $95\%$ reliable while the reliance on Source 3 is smaller).

Source 1, $\tau_{S1}=0.95$ |  |  Source 2, $\tau_{S2}=0.80$ |  |  Source 3, $\tau_{S3}=0.70$
---|---|---|---|---
professor(Bob) |  | offeredCourseAt(DB,LIFO) |  | professor(Peter)
professor(Tom) |  | offeredCourseAt(Java,LIFAT) |  | professor(Ann)
professor(Alice) |  | worksFor(Bob,LIFO,UO) |  | headOf(Bob,LIFO)
bornIn(Bob,USA) |  | worksFor(Ann,LIFAT,UT) |  | headOf(Ann,CNRS)
bornIn(Tom,UK) |  | takesCourse(Tom, Java) |  | bornIn(Peter,UK)
bornIn(Alice,Denmark) |  | takesCourse(Bob, Net) |  | bornIn(Ann,USA)
foreignCountry(USA) |  | teacherOf(Bob, DB) |  | teacherOf(Peter,Java)
foreignCountry(UK) |  | teacherOf(Bob, Java) |  | teacherOf(Ann,DB)
foreignCountry(Denmark) |  | teacherOf(Tom, Java) |  | researchesIn(Bob,DB)
|  | teacherOf(Alice, Net) |  | employeeGov(Bob)
|  |  |  | employeeGov(Tom)
|  |  |  | employeeGov(Alice)
|  |  |  | employeeGov(Peter)
Table 2: Example of local sources

Suppose one user wants to work in a context that contains only constraints
$c_{P1}$ and $c_{P2}$. In this scenario let us consider query $q(X)\leftarrow
professor(X),$ $bornIn(X,Y),foreignCountry(Y)$ to find the foreign professors.
The required confidence degree is $\tau_{in}=0.75$, indicating that sources
having a smaller confidence degree should not be taken into account. In this
case, only data from sources 1 and 2 are considered. Source 3 is ignored as
$\tau_{S3}<\tau_{in}$. The answer is the set $\\{(Bob):0.8,(Tom):0.8\\}$ as
both Bob and Tom are professor ($professor(Bob),professor(Tom)$); they were
born in foreign countries ($bornIn(Bob,USA)$, $bornIn(Tom,UK)$,
$foreignCountry(USA)$, $foreign\\-$ $Country(UK)$), and they teach at least
one course ($teacherOf(Bob,DB)$,$teacherOf(Tom,Java)$) at a department
($offeredCourseAt(DB,LIFO)$, $offeredCourseAt(Java,LIFAT)$). Tuple $(Alice)$
is not an answer because, although we have $teacherOf(Alice,Net)$ in the
database ($c_{P1}$ is satisfied), her course is not associated with any
department, a violation of constraint $c_{P2}$.

A new user wants a context involving all the constraints in Table 1. For a
degree $\tau_{in}=0.7$ and the same query of the first scenario, data from all
three sources are taken into account. $Alice$’s course, $Net$, is associated
with no department (violating $c_{P2}$), $Tom$ teaches and follows a $Java$
course (violating $c_{N1}$), $Ann$ is not a government employee (violating
$c_{P3}$). In fact, $c_{P4}$ and $c_{K1}$ are also violated as Ann teaches
database but she does not do research in the database domain. Moreover, she is
the head of $CNRS$ while not working there. Only $Bob$ and $Peter$ satisfy all
constraints. Thus, the answer is the set $\\{(Bob):0.7,(Peter):0.7\\}$.
$\hfill\Box$

#### Querying Environment.

Our query processing framework, depicted in Figure 1a, comprises two distinct
parts which communicate: Data validation, responsible for checking constraints
satisfaction, and Data providers for computing answers to the queries. The
latter may integrate several end-data-providers, or it may connect only one
provider. For ensuring that the final answers to the user’s queries satisfy
all user constraints, a dialogue between the two parts is established, for
getting intermediate results and sending subsidiary queries.

A user context sets the user’s view on the queried sources. It is defined as
set of predicates and quality constraints involving these predicates. The
user’s query also involves these predicates, so quality constraints can be
used as rewriting-rules to reformulate each query $q$ into a set of
conjunctive queries whose answers, contained in $q$’s answers, are valid
w.r.t. the user quality constraints. Afterwards, these conjunctive queries are
sent to the Data providers part, which evaluates them against data stored on
sources. The query evaluation process is transparent to the validation step,
in particular, answers that are entailed are treated in the same way as those
that actually exist in sources. We respect the potential ontological dimension
of semantic web sources, while interpreting the user constraints using the
closed-world assumption. Indeed, as it deals with semantic data, the
evaluating process performed by the Data providers part relies on the open-
world assumption, where ontological constraints are used to deduce new
information. Ontological constraints are used as rewriting-rules to
reformulate a query into a set of new conjunctive queries, for taking into
account integration information (OBDA/OBDI Systems [23, 2]), or for dealing
with incomplete information issues [2, 14, 18]. But such rewritings are
performed by the Data providers part, independently from the Data validation
part. As our system may be deployed with various data management systems, a
translator module deals with datalog+- [4] for Graal111https://graphik-
team.github.io/graal/, SPARQL for FedX [25], and HIVE-SQL for MapReduce (see
[21]).

Organization (Extended Version). This paper extends the work in [8] by
presenting a new and more detailed version of our rewriting querying approach
together with its theoretical foundations and new experimental results. It is
organised as follows: Section 2 focus on related work. Section 3 formally
introduces our querying system. Section 4 details our query rewriting system
and Section 5 presents experimental results. Section 6 concludes the paper.

##  2 Related Work

The main goal of this work is to provide a quality-driven querying system on
distributed data, particularly on LOD. But our proposal is independent of LOD
specificities, as the results verification is based on a dialogue between the
checker and a LOD endpoint (or a federated query system). Inconsistency in
knowledge bases is the kernel of proposals such as [6, 7, 13, 15, 19, 24],
which consider the consistency of the data stored in the source databases. The
general idea is to restore database consistency or to propose update
approaches which ensure consistency or to refuse the database when consistency
is not achievable. In brief, those proposals try to use constraints to compute
the new consistent database. Contrary to them, our work focuses on the
consistency of the query answers returned to a user. Instead of trying to
establish the consistency of a database in order to query over it, we want to,
firstly, just evaluate a query on a given (possibly) inconsistent database,
and, then, use rules (which define a context) as filters to obtain the valid
answers. In this way, we also obtain consistent data. Our goal is neither to
modify the database nor to try to compute its different possible consistent
states. We do not want to refuse an inconsistent database. Since the meaning
of consistency is in connexion to a user profile; one can admit things that
are prohibited by others. Checking consistency of the answers is usually a
smaller task than verifying the whole database validity. A parallel can be
done between saturation in [13], the chase in [7] and our query rewriting.

Besides, in our proposal, rules defining a context are quality constraints.
They impose a filter on retrieved data (in contrast to work, e.g.  [6, 19,
24], where constraints are just inference rules). In [11] we find a solution
that is close to ours, but it does not comprehensively consider the presence
of constants in constraints and queries and it does not handle negative
constraints, either. Moreover, the way it deals with equality-generating
dependencies (EGD) differs from ours. Precisely, in [11] an equality is added
to the rewritten query only when the whole body of an EGD matches a subset of
atoms in the query’s body. This is an EGD chase step [22]. In our solution, an
EGD has to be considered even if there is only one atom in EGD’s body matching
an atom in the query’s body, reinforcing the idea that only consistent data
are allowed to compute results. Finally, the principle of restricting results
by rules is also the motivation of [9], which extends ontology-based data
access (OBDA) with data protection policies. But they proceed by compiling the
policies into the OBDA mappings, whereas our proposal is independent of
whether or not the query evaluation uses the ontological part of LOD resources
(see Fig.1).

(a) Query system overview. |  (b) Module Validator.
---|---
Figure 1: Query system overview and a zoom-in the Validator module.

##  3 Querying System: formal definitions

Our constraints are expressed in a first-order logic formalism. We consider an
alphabet made up of the equality symbol ($=$), quantifiers ($\forall$ and
$\exists$), the symbols $\top$ (true) and $\bot$ (false) and of four disjoint
sets const (of constants) null (of fresh labeled nulls), var (of variables
used to range over elements of const or null) and pred (of predicates). The
only possible terms are constants, nulls or variables. A free tuple $u$ is a
sequence of either variables or constants, or both. We denote by $var(u)$ the
set of variables in $u$. An atom is a formula having one of the forms: (i)
$p(t_{1},...,t_{n})$, where $p$ is an $n$-ary predicate, and $t_{1},...,t_{n}$
are terms; (ii) expressions $\top$ and $\bot$; (iii) $t_{1}=t_{2}$, where
$t_{1}$ and $t_{2}$ are terms. A conjunction of atoms is often identified with
the set of all its atoms. A fact over a predicate $p$ is an atom $p(u)$ where
$u\in\textsf{const}^{n}$. A homomorphism from a set of atoms $A_{1}$ to a set
of atoms $A_{2}$ is a mapping $h$ from the terms of $A_{1}$ to the terms of
$A_{2}$ such that: (i) if $t\in\textsf{const}$, $\bot$ or $\top$ then
$h(t)=t$; (ii) if $t\in\textsf{null}$, then
$h(t)\in(\textsf{const}\cup\textsf{null})$ and (iii) if $r(t_{1},...,t_{n})$
is in $A_{1}$, then $h(r(t_{1},...,t_{n}))=r(h(t_{1}),...,h(t_{n}))$ is in
$A_{2}$. The notion of homomorphism naturally extends to sets of atoms and
conjunctions of atoms. An isomorphism is a bijective homomorphism. Two atoms
$A$ and $A^{\prime}$ are unifiable iff there exists an homomorphism $\sigma$
(denoted by unifier) on $\\{A,A^{\prime}\\}$, such that
$\sigma(A)=\sigma(A^{\prime})$. If $A$ and $A^{\prime}$ are unifiable, then
they have a unifier $\theta$ such that every unifier $\sigma$ of $A$ and
$A^{\prime}$ can be written as $\sigma=h\theta$ for some homomorphism $h$ on
$\\{A,A^{\prime}\\}$. Such a unifier is called the most general unifier of $A$
and $A^{\prime}$ (denote by mgu).

A conjunctive query (CQ) has the form $q:R_{0}(u_{0})\leftarrow
R_{1}(u_{1})\dots R_{n}(u_{n})\linebreak comp_{1}(v_{1})\dots comp_{m}(v_{m})$
where $n,m\geq 0$, $R_{i}$ ($0\leq i\leq n$) are predicate names of a database
schema, $u_{i}$ are free tuple of appropriate arity and $comp_{j}(v_{j})$
($0\leq j\leq m$) are comparison formulas having the form $(X=a)$ or $(X=Y)$
where $X$ and $Y$ are variables appearing in $u_{i}$ ($0\leq i\leq n$) and $a$
is a constant. We denote $head(q)$ its left hand-side and $body(q)$ its right
hand-side. Queries are range restricted and satisfiable [1]. The answer to a
conjunctive query $q$ of arity $n$ over a database instance $I$, denoted as
$q(I)$, is the set of all tuples $t\in\textsf{const}^{n}$ for which there
exists a homomorphism $h_{t}$ such that $h_{t}(body(q))\subseteq I$ and
$h_{t}(u_{0})=t$.
(*) We denote by $h_{t}$ a homomorphism used to obtain an answer tuple $t$.

#### Querying with confidence.

Confidence in data providers may vary and a user’s query $q$ may be bounded by
a confidence degree $\tau_{in}$. We define answering with confidence on a data
source and then on a set of data sources, possibly from different providers.
Indeed, $q$’s evaluation may concern distinct data sources.

######  Definition 1 (Querying with confidence on a data source)

Let $(\hbox{${\cal S}$},$ $\tau)$ be a source database: ${\cal S}$ is a
database instance and $\tau$ is its truth or confidence degree. Let $q$ be a
query and $\tau_{in}$ its truth degree. The answer of $q:\tau_{in}$ over
$(\hbox{${\cal S}$},\tau)$ is the set
$ans(\hbox{$q\\!:\\!\tau_{in}$},(\hbox{${\cal S}$},$ $\tau))=$
$\\{(t:\tau_{out})\mid\tau_{out}=\tau$ and $t\in q(\hbox{${\cal S}$})$ and
$cond(\tau_{in},\tau)\\}$, where $cond(\tau_{in},\tau)$ is a condition given
by the user. $\hfill\Box$

######  Definition 2 (Querying with confidence on $\overline{(\hbox{${\cal
S}$},\tau)}$ )

Let $\overline{(\hbox{${\cal S}$},\tau)}$ be a database instance composed of
$n$ databases having different truth degrees. A couple $(t:\tau_{out})$ is a
candidate answer for query ($q:\tau_{in},\hbox{$\overline{(\hbox{${\cal
S}$},\tau)}$})$ if the following conditions hold: $(1)$ tuple $t$ is an answer
obtained from local sources, i.e. $t\in ans(q,\hbox{$\overline{\hbox{${\cal
S}$}}$})$; $(2)$ $\tau_{in}\leq\tau_{out}$ and the computation of $\tau_{out}$
is defined by
$\tau_{out}=f(\tau_{in},\\{\tau^{1}_{out_{S_{i}}},\dots,\tau^{m}_{out_{S_{l}}}\\})$
where: $(i)$ each $\tau^{k}_{out_{S_{j}}}$ denotes the degree of the tuples in
$ans(q_{k}:\tau^{k}_{in},(S_{j},\tau_{j}))$ for the sub-query $q_{k}$ ($1\leq
k\leq m$) generated to be evaluated on the local source $(S_{j},\tau_{j})$
during the evaluation process of $q$ (where $i,j,l\in[1,n]$) and $(ii)$
function $f$ computes a confidence degree taking as input the query confidence
degree and the confidence degrees of data sources concerned by $q$.
$\hfill\Box$

A user can parametrize the use of confidence degrees by choosing different
functions $f$ and by combining this choice with $cond$ in Definition 1. In
this paper we consider that
$f(\tau_{in},\\{\tau^{1}_{out_{S_{i}}},\dots,\tau^{m}_{out_{S_{l}}}\\})$
corresponds to $min(\\{\tau^{1}_{out_{S_{i}}},\dots,$
$\tau^{m}_{out_{S_{l}}}\\})$ and we disregard sources whose confidence is
inferior to $\tau_{in}$.

#### Context-driven querying system.

A context is a set of constraints. Only data respecting them are allowed as
answers for the user’s query.

######  Definition 3 (Constraints)

A context ${\cal C}$ is composed by the following sets:

$\bullet$ Positive constraints ($\hbox{${\cal C}$}_{P}$): A positive
constraint has the form

$c:\forall x_{1},\dots,x_{n}~{}~{}~{}L_{1}(u_{1})\rightarrow\exists
y_{1},\dots,y_{m}~{}~{}L_{2}(u_{2})$

where $L_{1}$ and $L_{2}$ are predicate names in $\mathbb{G}$; $u_{1}$ and
$u_{2}$ are free tuples and $var(u_{1})\cap
var(u_{2})=\\{x_{1},\dots,x_{k}\\}$ for
$var(u_{1})=\\{x_{1},\dots,x_{k},x_{k+1},\dots,x_{n}\\}$,
$var(u_{2})=\\{x_{1},\dots,x_{k},y_{1},\dots,y_{m}\\}$, with $n\geq k\geq 0$,
$m\geq 0$.

$\bullet$ Negative constraints ($\hbox{${\cal C}$}_{N}$): A negative
constraint is a rule where all variables in the free tuple $u$ are universally
quantified and which has one of the (equivalent) formats:
$c:\phi(u)\rightarrow\bot$ or $c:\phi^{\prime}(u),comp\rightarrow\bot$.
Formula $\phi(u)$ is an atom $L_{1}(u)$ or a conjunction of two atoms
$L_{1}(u_{1}),L_{2}(u_{2})$, for which if $var(u_{1})$ and $var(u_{2})$ are
non-empty sets, then $var(u_{1})\cap var(u_{2})\neq\emptyset$. In the second
format, equalities on variables are explicitly expressed in the comp atoms. We
refer to $\hbox{${\cal C}$}_{N1}$ and $\hbox{${\cal C}$}_{N2}$ as sets of
negative constraints having only one atom and two atoms, respectively.

$\bullet$ Equality-generating dependency constraints without nulls
($\hbox{${\cal C}$}_{K}$) (also called key constraints): An EGD is a rule
having the general form $c:~{}~{}L_{1}(u_{1}),L_{2}(u_{2})\rightarrow
u^{\prime}_{1}=u^{\prime}_{2}$ where all variables in the free tuple $u_{1}$
and $u_{2}$ are universally quantified; $L_{1}$, $L_{2}$ are predicate names
in $\mathbb{G}$; $u_{1}$, $u_{2}$ are free tuples such that $var(u_{1})\cap
var(u_{2})\neq\emptyset$; $u^{\prime}_{1}$ and $u^{\prime}_{2}$ are sub-tuples
(i.e. an ordered-subset of variables) of var($u_{1}$) and var($u_{2}$)
respectively. EGD include functional dependency (and thus, key constraints)
having the form: $L_{1}(u_{1}),L_{1}(u_{2})\rightarrow
u^{\prime}_{1}=u^{\prime}_{2}$ $\hfill\Box$

For simplicity, we usually omit quantifiers. We say that a constraint $c$ is
triggered by an atom $A$ when there is a homomorphism $h$ from $body(c)$ to
$A$. Positive constraints are a special case of linear tuple generating
dependency (TGD [1]) which contain only one atom in the head. When $u_{2}$ has
existential quantified variables, the homomorphism $h$ is extended to
$h^{\prime}$ such that, for each existential variable $z\in u_{2}$,
$h^{\prime}(z)$ is a new fresh null. It is well-known that facts from a
database instance may trigger such constraints, and the chase procedure [20]
is the standard process for the generation of new facts from a database
instance and a set of dependencies (TGD or EGD) [1]. It can also be used to
decide containment of conjunctive queries in the presence of constraints [17].
We consider that the set of positive constraints is weakly acyclic [12],
ensuring: (i) that positive constraints do not have a cyclic condition such
that a null value forces the adding of a new null value [22] and (ii) the
decidability of query containment [11]. Our motivating example in Section 1
illustrates all three types of constraints.

Now, let $q\\!:\\!\tau_{in}$ be a CQ and $\hbox{${\cal C}$}=\hbox{${\cal
C}$}_{P}\cup\hbox{${\cal C}$}_{N}\cup\hbox{${\cal C}$}_{K}$ be a context.
Valid answers are those that respect constraints in ${\cal C}$ and are
obtained by trusted databases. In the following, given $\hbox{${\cal
C}$}_{P}$, we denote by $chase(\hbox{${\cal C}$}_{P},I)$ the procedure capable
of computing all consequences of $\hbox{${\cal C}$}_{P}$ in an instance $I$.
We refer to [3, 22] for details on the different chase algorithms.

######  Definition 4 (Valid answers)

The set of valid answers of a query $q:\tau_{in}$, restrained by ${\cal C}$,
over a database $\overline{(\hbox{${\cal S}$},\tau)}$, denoted by $valAns$
$(\hbox{$q\\!:\\!\tau_{in},\hbox{${\cal C}$}$},$
$\hbox{$\overline{(\hbox{${\cal S}$},\tau)}$})$ is defined by the set
$\\{(t:\tau_{out})\\}$ respecting the following conditions:
$\bullet$ $t$ is a candidate answer as in Definition 2 with its (maybe
several) $h_{t}$ (*);
$\bullet$ there exists $h_{t}$ such that for all $L\in$
$h_{t}(chase(\hbox{${\cal C}$}_{P},J))$, where $J=\\{l|l\in
h_{t}(body(q))\\}$, the following conditions hold:
(a) there is a positive answer for $q()\leftarrow L:\tau_{in}$ on
$\overline{(\hbox{${\cal S}$},\tau)}$;
(b) for each $c\in\hbox{${\cal C}$}_{N2}$ of the form
$L_{1},L_{2}\rightarrow\bot$, if there is a homomorphism $\nu$ such that
$\nu(L_{i})=L$, then there is no homomorphism $\nu^{\prime}$ that extends
$\nu$ and for which there is a positive answer for
$q^{\prime}()\leftarrow\nu^{\prime}(L_{\overline{i}}):\tau_{in}$ (In our
notation, if $i=1$ then $\overline{i}=2$ and vice-versa);
(c) for each $c\in\hbox{${\cal C}$}_{N1}$ of the form $L_{1}\rightarrow\bot$,
there is no homomorphism $\nu$ such that $\nu(L_{1})=L$;
(d) for each $c\in\hbox{${\cal C}$}_{K}$ of the form
$L_{1}(u_{1}),L_{2}(u_{2})\rightarrow X_{1}=X_{2}$ where $X_{1}$ and $X_{2}$
are variable in $u_{1}$ and $u_{2}$ respectively, if there is a homomorphism
$\nu$ such that $\nu(L_{i}(u_{i}))=L$, then the answer of
$q(X_{\overline{i}})\leftarrow\nu(L_{\overline{i}}(u_{\overline{i}})):\tau_{in}$
is a singleton containing the tuple value $\nu(X_{i})$. $\hfill\Box$

Valid answers can be computed in different ways. The naive approach is a
direct implementation of Definition 4: its main idea is to validate each
answer of a query $q$ by generating sub-queries corresponding to each
constraint $c\in\hbox{${\cal C}$}$. We refer to [21] for the algorithm
implementing this approach. The rewriting approach focuses on building new
queries that incorporate the constraints. It is the subject of the following
section.

##  4 The query rewriting approach

Figure 1b offers a closer look at the Validator module. It receives the user’s
query $q$ and a set ${\cal C}$ of constraints, and treats each constraint type
differently. In a preprocessing step, the set of negative constraints
$\hbox{${\cal C}$}_{N}$ is translated into a new set $\hbox{${\cal C}$}_{Nrw}$
of positive constraints involving new auxiliary relations. Auxiliary relations
are stored in $S_{aux}$, an auxiliary database, or they can be defined as
views and evaluated over the database instance when needed. Translated
negative constraints, together with positive constraints, are used as
rewriting rules: if the body of a constraint $c$ matches atoms in the body of
$q$, then the head of $c$ is integrated into $q$’s body. The new rewritten
query allows the validation and the query evaluation to be performed together,
avoiding validating an extremely large number of intermediate results. This
query rewriting process gives rise to a set ${\cal Q}$ of rewritten queries,
which are evaluated over $S_{aux}$ and $\overline{(\hbox{${\cal S}$},\tau)}$.
If we denote by ${\cal R}$ the set of answers obtained from the evaluation of
${\cal Q}$, then ${\cal R}$ is valid w.r.t. $\hbox{${\cal C}$}_{P}$ and
$\hbox{${\cal C}$}_{N}$ (proofs in Section 4.3). The validity of each tuple in
${\cal R}$ w.r.t. key constraints is done by the naive approach.

Before presenting our rewrite method in details, we consider three examples to
illustrate the situations our algorithm tackles with.

###### Example 1

Let $q_{1}(X_{1})\leftarrow
professor(X_{1}),bornIn(X_{1},Z_{1}),foreignCoun$$try(Z_{1})$ be the query
considered in Section 1 and a user’s context composed of $c_{P_{1}}$,
$c_{P_{2}}$ and $c_{P_{3}}$ (Table 1). The mgu $\\{\sigma(X_{id})=X_{1}\\}$
allows unification between $professor(X_{1})$ in $body(q_{1})$ and
$body(c_{P_{1}})$. As $c_{P_{1}}$ is triggered and $\sigma$ is an homomorphism
from $body(c_{P1})$ to $body(q_{1})$, the rewriting step is done by adding
$\sigma(head(c_{P_{1}}))=teacherOf(X_{1},N_{1})$ into $body(q_{1})$.
Existential variable $Y$ in $head(c_{P_{1}})$ is replaced by a new fresh
variable $N_{1}$. This is a step on the chase computation. Then, the new atom
$teacherOf(X_{1},N_{1})$ triggers constraint $c_{P_{2}}$, and so on. The chase
process terminates when a fix-point is reached. Then the following query
$q^{\prime}_{1}(X_{1})\leftarrow$
$professor(X_{1}),teacherOf(X_{1},N_{1}),offeredCourseAt(N_{1},$ $N_{2}),$
$employeeGov(X_{1}),$ $bornIn(X_{1},Z_{1}),foreignCountry(Z_{1})$ is sent to
data providers. Answers for $q^{\prime}_{1}$ satisfy both $q_{1}$ and all the
three above constraints. $\hfill\Box$

###### Example 2

Let us consider $q_{1}$ in a new context, composed of $c_{P_{1}}$(Table 1) and
a new $c_{N_{2}}:$ $teacherOf(X,Y),headOf(X,Z)\rightarrow\bot.$ Initially, the
rewriting step is identical to the one discussed in Example 1:
$teacherOf(X_{1},N_{1})$ is added to the query’s body. This new atom triggers
$c_{N2}$. To avoid dealing with negative atoms in the rewritten query, we
replace the negative constraint $c_{N2}$ by a new positive constraint
$c_{aux_{1}}:teacherOf(X,Y)\rightarrow aux\\_teacherOf(X,Y)$, where
aux_teacherOf is an auxiliary relation containing tuples which respect
$c_{N_{2}}$ (according to the datasets in Table 2, aux_teacherOf contains data
about $Peter$, $Tom$ and $Alice$). We then treat the negative constraint
$c_{N2}$ as a positive one. The rewritten query
$q^{\prime}_{1}(X_{1})\leftarrow$ $professor(X_{1}),teacherOf(X_{1},N_{1}),$
$aux\\_teacherOf(X_{1},$ $N_{1}),$ $bornIn(X_{1},Z_{1}),foreignCountry(Z_{1})$
is evaluated on $\overline{(\hbox{${\cal S}$},\tau)}$, composed by instances
shown in Table 2, together with the auxiliary database instance $\hbox{${\cal
S}$}_{Aux}$.$\hfill\Box$

###### Example 3

Constraint $c_{P4}$ imposes restrictions on teachers who teach database: they
should do research in the database domain. No restriction is imposed on
teachers in other domains. For query $q_{2}(X)\leftarrow teacherOf(X,Y)$ the
situation is different from the one in Example 1: the unifier between
$body(q_{2})$ and $body(c_{P4})$ is not a homomorphism from $body(c_{P4})$ to
$body(q_{2})$ (but the inverse). We cannot apply the reasoning of Example 1: a
query such as $q^{\prime}_{2}(X)\leftarrow teacherOf(X,DB),$
$researchesIn(Z,DB)$ would ignore the teachers of all other domains. Here, we
replace $q_{2}$ by the two queries, namely, $q_{2.1}(X)\leftarrow
teacherOf(X,Y),$ $Y\neq DB$ and $q_{2.2}(X)\leftarrow
teacherOf(X,DB),researchesIn(X,DB).$ The first query is created by adding a
comparison atom to deal with results that are not concerned by the constraint.
The second query is created by integrating $head(c_{P4})$ in $q_{2}$ and
applying a comparison atom ($Y=DB$) which covers the results related to the
constraint.$\hfill\Box$

In the rest of this section, we explain the preprocessing of negative
constraints, we show the details of our rewriting method proving that it is
sound and complete and we present the whole validation process via rewriting.

###  4.1 Preprocessing Negative Constraints

The translation of negative constraints implies computing auxiliary instances.

######  Definition 5 (Auxiliary Relations from Negative Constraints)

Let $L_{1}(u_{1}),L_{2}(u_{2}),comp\rightarrow\bot$ be a negative constraint
with $var(u_{1})\cap var(u_{2})=\\{x_{1},\dots,x_{n}\\}$ (we denote a sequence
such as $x_{1},\dots,x_{n}$ by a variable in capital letter). Auxiliary
relations ${L^{c}_{1,\overline{L_{2}}}}$, and, resp.,
${L^{c}_{2,\overline{L_{1}}}}$, denoted as the complementary relation of
$L_{1}$ w.r.t. $L_{2}$ (resp., of $L_{2}$ w.r.t. $L_{1}$) are obtained by the
evaluation of the following datalog programs on a given database source
$\overline{(\hbox{${\cal S}$},\tau)}$.

Computation of ${L^{c}_{1,\overline{L_{2}}}}$: |  | Computation of ${L^{c}_{2,\overline{L_{1}}}}$:
---|---|---
$q_{1}(X)\leftarrow L_{1}(X,Y)$ |  | $q_{1}(X)\leftarrow L_{2}(X,Y)$
$q_{2}(X)\leftarrow L_{2}(X,Y),comp|_{L_{2}}$ |  | $q_{2}(X)\leftarrow L_{1}(X,Y),comp|_{L_{1}}$
$q_{3}(X)\leftarrow q_{1}(X),\neg q_{2}(X)$ |  | $q_{3}(X)\leftarrow q_{1}(X),\neg q_{2}(X)$
$\hbox{${L^{c}_{1,\overline{L_{2}}}}$}(X,Y)\leftarrow L_{1}(X,Y),q_{3}(X)$ |  | $\hbox{${L^{c}_{2,\overline{L_{1}}}}$}(X,Y)\leftarrow L_{2}(X,Y),q_{3}(X)$

or, equivalently, the evaluation of the following relational algebra queries:
$~{}~{}~{}\hbox{${L^{c}_{1,\overline{L_{2}}}}$}:=L_{1}\Join(\Pi_{X}(L_{1})\setminus\Pi_{X}(\sigma_{comp|L_{2}}(L_{2}))$
and
$~{}~{}~{}\hbox{${L^{c}_{2,\overline{L_{1}}}}$}:=L_{2}\Join(\Pi_{X}(L_{2})\setminus\Pi_{X}(\sigma_{comp|L_{1}}(L_{1}))$
$\Box$

Let $c_{N}$ be a negative constraint. Algorithm Preprocessing Negative
Constraints (detailed in [21]) deals with different situations. Firstly, when
the body of $c_{N}$ contains facts, we distinguish two scenarios. If these
facts do not exist in the database instance $\overline{(\hbox{${\cal
S}$},\tau)}$, the constraint $c_{N}$ is not added into the set $C_{Nrw}$.
Otherwise, if these facts are true in $\overline{(\hbox{${\cal S}$},\tau)}$,
for each fact $f$ in $body(c_{N})$ we create a new constraint of the format
$f\rightarrow\bot$. Finally, when the body of $c_{N}$ is not composed by
facts, new constraints are added to $C_{Nrw}$. If $c_{N}$ has only one atom in
its body; $c_{N}$ itself is added to $C_{Nrw}$. Otherwise, when $c_{N}$ has
two atoms in its body (i.e., $L_{1}(u_{1}),L_{2}(u_{2})\rightarrow\bot$);
$c_{N}$ is translated into two new constraints. Each new constraint involves
an auxiliary complementary relation. Relation
$\hbox{${L^{c}_{1,\overline{L_{2}}}}$}(u_{1})$
($\hbox{${L^{c}_{2,\overline{L_{1}}}}$}(u_{1})$) contains the complement of
$L_{1}$ w.r.t. $L_{2}$ (respectively, $L_{2}$ w.r.t. $L_{1}$ ) and the join
and selection conditions appearing in $c_{N}$. Definition 5 establishes the
queries that should be evaluated in order to compute instances of
$\hbox{${L^{c}_{1,\overline{L_{2}}}}$}(u_{1})$ and
$\hbox{${L^{c}_{2,\overline{L_{1}}}}$}(u_{1})$ (to be stored in $\hbox{${\cal
S}$}_{aux}$). All instances in $\hbox{${\cal S}$}_{aux}$ are computed on the
basis of the current instance $\overline{(\hbox{${\cal S}$},\tau)}$.

###### Example 4

Consider the dataset $\overline{(\hbox{${\cal S}$},\tau)}$ and the new
negative constraint:

$c_{N_{3}}:worksFor(X,Y,Z),bornIn(X,W),(Z=CNRS),(W=France)\rightarrow\bot.$

According to Definition 5, auxiliary relations $aux\\_worksFor^{c_{N_{3}}}$
and $aux\\_bornIn^{c_{N_{3}}}$ are computed by the rules
$aux\\_worksFor^{c_{N_{3}}}(X,Y,Z)\leftarrow worksFor(X,Y,Z),q_{13}(X)$ and
$aux\\_bornIn^{c_{N_{3}}}(X,W)$ $\leftarrow bornIn(X,W),q_{23}(X)$ with:

$q_{11}(X)\leftarrow worksFor(X,Y,Z);$ | $q_{12}(X)\leftarrow bornIn(X,France);$ | $q_{13}(X)\leftarrow q_{11}(X),\neg q_{12}(X)$
---|---|---
$q_{21}(X)\leftarrow bornIn(X,W);$ | $q_{22}(X)\leftarrow worksFor(X,Y,CNRS);$ | $q_{23}(X)\leftarrow q_{21}(X),\neg q_{22}(X).$

These relations are added into the auxiliary database $S_{aux}$ and $c_{N3}$
is transformed into two constraints: $worksFor(X,Y,CNRS)\rightarrow
aux\\_worksFor^{c_{N3}}(X,Y,Z)$ and $bornIn(X,France)\rightarrow
aux\\_bornIn^{c_{N3}}(X,W).$ $\Box$

###  4.2 Rewriting Query Algorithm

Given a query $q$, and a set of constraints $\hbox{${\cal C}$}_{rw}$, which
consists of constraints in $\hbox{${\cal C}$}_{P}$ and those resulted from the
preprocessing step, the rewriting process consists of performing the chase,
starting with the atoms in $body(q)$. The idea is similar to the one used in
[10]. Our algorithm denoted by $RewriteQuery$ (Algorithm 2) proposes an
iteration over constraints and queries. At each iteration, a step of the chase
is performed by Algorithm 1 to incorporate constraints in $\hbox{${\cal
C}$}_{rw}$ to the body of $q$.

A constraint $c$ is integrated into query $q$ if it is triggered by an atom in
$q$. After translating $\hbox{${\cal C}$}_{N}$ into $\hbox{${\cal C}$}_{Nrw}$,
constraints have only one atom in their bodies. Thus, testing whether $c$ is
triggered by an atom $L$ in $body(q)$ is to check the existence of $\theta$, a
mgu which ensures $q$’s satisfiability, between $L(u)$ and $body(c)$
(Algorithm 1, line 1). Once the condition on line 1 is satisfied, the
constraint $c$ should be matched to atom $L(u)$. To this end, variables in $c$
are renamed by variables in $q$ by using the one-way mgu defined below.

######  Definition 6 (One-way MGU)

Let $l_{1}$ and $l_{2}$ two literals which are unifiable. A one-way unifier
denoted by $\theta_{l_{1}\rightarrow l_{2}}$ is a $mgu$ for $l_{1}$ and
$l_{2}$ such that all variables of $\theta_{l_{1}\rightarrow l_{2}}(l1)$ are
variables of $l2$. $\Box$

For example, let $l_{1}=A(X_{1},a,b,Y_{1},Y_{1})$ and
$l_{2}=A(a,X_{2},Y_{2},Z_{2},U_{2})$ which are unifiable. A possibility for
the one-way mgu from $l_{1}$ to $l_{2}$ is $\\{\theta_{l_{1}\rightarrow
l_{2}}(X_{1})=a,\theta_{l_{1}\rightarrow
l_{2}}(Y_{1})=Z_{2},\theta_{l_{1}\rightarrow
l_{2}}(X_{2})=a,\theta_{l_{1}\rightarrow
l_{2}}(Y_{2})=b,\theta_{l_{1}\rightarrow l_{2}}(U_{2})=Z_{2}\\}$ and
$\\{\theta_{l_{2}\rightarrow l_{1}}(X_{1})=a,\theta_{l_{2}\rightarrow
l_{1}}(X_{2})=a,\theta_{l_{2}\rightarrow
l_{1}}(Y_{2})=b,\theta_{l_{2}\rightarrow
l_{1}}(Z_{2})=Y_{1},\theta_{l_{2}\rightarrow l_{1}}(U_{2})=Y_{1}\\}$ for the
one-way mgu from $l_{2}$ to $l_{1}$. Clearly $\theta_{l_{1}\rightarrow
l_{2}}(l1)=\theta_{l_{1}\rightarrow l_{2}}(l2)$.

The notion of one-way unifier is essential when constraints have constants or
repeated variables in their bodies. Algorithm 1, line 1, finds the
homomorphism $h$ once the one-way unifier is applied to the body of $c$. The
need of the one-way mgu is illustrated by the example below.

###### Example 5

Let $c:A(X_{1},a,b,Y_{1},Y_{1})\rightarrow B(X_{1},Y_{1})$ be a constraint and
let $q(X_{2},Y_{2},Z_{2},U_{2})\leftarrow
A(a,X_{2},Y_{2},Z_{2},U_{2}),C(U_{2})$ be a query.

Atoms $l_{1}=A(X_{1},a,b,Y_{1},Y_{1})$ and
$l_{2}=A(a,X_{2},Y_{2},Z_{2},U_{2})$ are unifiable but there is neither a
homomorphism from the $l_{1}$ (i.e., $c$’s body) to $l_{2}$ nor a homomorphism
from $l_{2}$ to $l_{1}$. However, since mgu $\theta$ exists, it is possible to
find an instantiation of $A(a,X_{2},Y_{2},Z_{2},U_{2})$ that triggers $c$. In
other terms, an answer for $q$ can trigger $c$ imposing the constraint
verification.

An one-way unifier, such as $\\{\theta_{l_{1}\rightarrow
l_{2}}(X_{1})=a,\theta_{l_{1}\rightarrow
l_{2}}(Y_{1})=Z_{2},\theta_{l_{1}\rightarrow
l_{2}}(X_{2})=a,\theta_{l_{1}\rightarrow
l_{2}}(Y_{2})=b,\theta_{l_{1}\rightarrow l_{2}}(U_{2})=Z_{2}\\}$ applied to
$c$ gives $A(a,a,b,Z_{2},Z_{2})\rightarrow B(a,Z_{2})$. Now it is possible to
find a homomorphism from $l_{2}$ to $l_{1}$.

An one-way unifier allows Algorithm 1 to produce new queries $q_{1}$ and
$q_{2}$, according to lines 1-1. Let us consider the homomorphism $h$ from
$l_{2}$ to $\theta_{l_{1}\rightarrow l_{2}}(l_{1})$ such that: $h(X_{2})=a,$
$h(Y_{2})=b$, $h(Z_{2})=Z_{2}$, $h(U_{2})=Z_{2}$. Then, according to Algorithm
1 we obtain the following queries:

  1. $q_{2}:$ $q(X_{2},Y_{2},Z_{2},U_{2})\leftarrow A(a,X_{2},Y_{2},Z_{2},U_{2}),C(U_{2}),B(a,Z_{2}),X_{2}=a,Y_{2}=b,U_{2}=Z_{2}$

  2. $q_{1_{1}}:$ $q(X_{2},Y_{2},Z_{2},U_{2})\leftarrow A(a,X_{2},Y_{2},Z_{2},U_{2}),C(U_{2}),X_{2}\neq a$

  3. $q_{1_{2}}:$ $q(X_{2},Y_{2},Z_{2},U_{2})\leftarrow A(a,X_{2},Y_{2},Z_{2},U_{2}),C(U_{2}),Y_{2}\neq b$

  4. $q_{1_{3}}:$ $q(X_{2},Y_{2},Z_{2},U_{2})\leftarrow A(a,X_{2},Y_{2},Z_{2},U_{2}),C(U_{2}),U_{2}\neq Z_{2}$

The one-way unifier allows rewriting a query on the basis of the unification
of only two atoms - one in the query’s body, the other in the constraint’s
body. Without it, it would be necessary to apply a $mgu$ to the whole query’s
body at each step. $\Box$

Input : A conjunctive query $q:\tau_{in}$ and a constraint $c\in\hbox{${\cal
C}$}_{rw}$ where $\hbox{${\cal C}$}_{rw}=\hbox{${\cal C}$}_{P}\cup\hbox{${\cal
C}$}_{Nrw}$

Output : A set $Q$ of rewritten queries $q_{r}:\tau_{in}$, such that for each
$q_{r}:\tau_{in}$ we have $head(q_{r})=head(q)$.

1 Function  _StepChase(_$q:\tau_{in}$ , c_)_:

_2_ _ _ foreach  _atom $L(u)\in body(q)$ such that:_

3  _there is a mgu_ $\theta:\theta(L(u))=\theta(body(c))$ for which
$\theta(body(q))$ is satisfiable  do

4 Denote query $q:\tau_{in}$ by $q(u_{0})\leftarrow\beta(u_{1}),L(u)$;

5 Let $\sigma_{c}$ be $\theta_{body(c)\rightarrow L(u)}$ (Definition 6) ;

6 if  _$\exists\ homomorphism\ \nu\ from\ body(\sigma_{c}(c))\ to\ L(u)$ _
then

7 if  _$\neg Isomorphic(\nu(\sigma_{c}((head(c))),q)$ _ then

8 $q(u_{0})\leftarrow\beta(u_{1}),L(u),(\nu(\sigma_{c}((head(c)))$ ;

9 $Q:=Q\cup\\{q:\tau_{in}\\}$;

10

11

12 else

13 Let $h$ be a homomorphism such that $h(L(u))=\sigma_{c}(body(c))$ ;

14 Let $Q:=\emptyset$;

15 Let $q_{2}:\tau_{in}$ be
$q(u_{0})\leftarrow\beta(u_{1}),L(u),h(\sigma_{c}(head(c)))$;

16 foreach  _var. $x$ in $u$ for which $h(x)=a$, where $a$ is a term $a\neq x$
_ do

17 Let $q_{1}:\tau_{in}$ be $q(u_{0})\leftarrow\beta(u_{1}),L(u),(x\neq a)$;

18 $Q:=Q\cup\\{q_{1}:\tau_{in}\\}$;

19 $body(q_{2}):=body(q_{2})\wedge(x=a)$;

20

21 $Q:=Q\cup\\{q_{2}:\tau_{in}\\}$ ;

22

23 return($Q$);

24

25

Algorithm 1 A step of chase processing

Once $\theta$ and $\theta_{body(c)\rightarrow L(u)}$ are determined on line 1
of Algorithm 1, we test if there is a homomorphism $\nu$ from
$body(\sigma_{c}(c))$ to $L(u)$. This is the criteria to decide how $c$ is
integrated into $q$ (line 1). Indeed, we have two main situations:

(1) When the homomorphism $\nu$ exists, the query’s body is completed with the
atom computed from the head of $\sigma_{c}(c)$ (line 1). The new atom is added
into $body(q)$ if it is not isomorphic to any atom already existing in $q$
(line 1). In this way, we avoid adding redundant atoms into the body of the
query, but we allow the result of the rewriting step to be empty (since $c$’s
consequence may already be in $body(q)$). We recall that our constraints
respect some syntactic restrictions, namely: (A) $\hbox{${\cal C}$}_{P}$ is a
set of weakly acyclic TGD [12]: it does not allow infinite labelled null
creation during the chase, (B) rules resulting from the translation of
negative constraints cannot trigger other constraints: their head’s predicates
are new, and do not belong to the initial schema.

(2) When the homomorphism $\nu$ does not exist, one of the following
situations hold: (i) we cannot map a constant in $body(c)$ to a variable or a
different constant in $L(u)$ or (ii) we cannot map a variable in $body(c)$
(appearing more than once) to different variables in $L(u)$. For instance, in
Example 3, no homomorphism from $body(\sigma_{c}(c_{p2}))$ to
$L=teacherOf(X,Y)$ is possible. However, as there is a mgu between $L$ and
$body(c)$, there is a homomorphism $h$ from $L$ to $body(\sigma_{c}(c_{p2}))$
(line 1). In this case, we generate two queries, namely: (A) a query ($q_{2}$
in the Algorithm 1) that deals with results (i.e., possible query
instantiations) involving constraint $c$, and (B) a set of queries ($q_{1}$ in
the foreach loop at line 1-1) dealing with results that are not concerned by
$c$. In both cases, $c$ can be written by using comparison atoms ($comp$)
containing equalities. During the rewriting process, Algorithm 1 generates
queries $q_{1}$ by adding into $body(q)$ the negation of these comparison
atoms. For instance, in our Example 3, $q_{2.1}$ selects people who do not
teach $DB$. With the database instance of Table 2, the answer for $q_{2.1}$ is
$Tom,Alice,Peter$. Query $q_{2.2}$ deals with results concerned by the
constraint. It selects two kinds of people: $(i)$ those who are database
researchers and only teach $DB$ and $(ii)$ those who teach and do research in
the database domain but also teach other subjects. In this example, the
answers for $q_{2}$ on the instance of Table 2 are $Bob$, $Tom$, $Alice$ and
$Peter$. Notice that $Bob$ is not an answer for $q_{2.1}$, but it is the
answer to $q_{2.2}$. The result of $q_{2}$ is the union of the answers for
$q_{2.1}$ and $q_{2.2}$. Rewritten queries dealing with results not concerned
by c (i.e. $q_{1}$ in Algorithm 1) introduce negative $comp$ atoms which, in
the relational algebra, can be translated to a selection with a negative
condition.

Let us now consider in detail Algorithm 2. The general idea here is to apply
exhaustively the chase step with constraints in $C_{rw}$ on $q$. Applying the
chase step on $q$ and a constraint $c\in C_{rw}$ results in a set of rewritten
queries $Q^{\prime}$ (line 2) which may replace $q$ in the next step. Recall
that the purpose of integrating constraint $c$ into $q$ by applying the chase
step on $q$ and $c$ is to filter answers of $q$ that are valid with respect to
$c$.

Input : A conjunctive query $q:\tau_{in}$ and a set of constraints
$\hbox{${\cal C}$}_{rw}=\hbox{${\cal C}$}_{P}\cup\hbox{${\cal C}$}_{Nrw}$

1

2 Function  _RewriteQuery(_$q:\tau_{in}$ , ${\cal C}$_)_:

3 $Q=\\{q:\tau_{in}\\}$;

4 repeat

5 $Changed:=false$;

6 foreach  _ $c\in\hbox{${\cal C}$}$ _ do

7 foreach  _ $q:\tau_{in}\in Q$ _ do

8 $replace:=false$;

9 $Q^{\prime}:=$ StepChase(_$q:\tau_{in}$ , c_);

/* Algorithm 1 */

10 foreach  _ $q^{\prime}:\tau_{in}\in Q^{\prime}$ _ do

11 if  _( $q^{\prime}:\tau_{in}$ is more restricted than $q:\tau_{in}$) and
($q^{\prime}:\tau_{in}$ is not contradictory) _ then

12 $Q:=Q\cup\\{q^{\prime}:\tau_{in}\\}$;

13 $Changed:=true$;

14 $replace:=true$;

15

16

17 if  _$replace$_ then

18 $Q:=Q\setminus\\{q:\tau_{in}\\}$ ;

19

20

21

22

23 until  _not Changed_ ;

24 return Q;

25

Algorithm 2 Query Rewriting

Query $q$ is replaced by $Q^{\prime}$ only if $Q^{\prime}$ is more restricted
than $q$, i.e. $ans(Q^{\prime})$ is included in $ans(q)$ (line 2). On the
other hand, in Algorithm 1, for a given query $q$, each rewritten query
$q^{\prime}$ is created by instantiating atoms or adding more atoms into
$body(q)$. Thus, an answer to each $q^{\prime}$ is either equal to or included
in the answer to $q$. When $q^{\prime}$ is equivalent to $q$, we can remove it
from $Q^{\prime}$. In other words, only rewritten queries (strictly) more
restricted than $q$ are considered replacing $q$ in $Q$ (lines 2-2). The new
set $Q$, in turn, will be chased with every constraint $c\in C_{Nrw}$,
including constraints already considered in previous steps, until no new query
is generated.

###### Example 6

Consider query $q(X)\leftarrow L_{1}(X,Y)$ and two constraints
$c_{1}:L_{1}(X,Y)$ $\rightarrow L_{2}(X,Y)$ and $c_{2}:L_{2}(X,a)\rightarrow
L_{1}(X,b)$. Figure 2a illustrates the execution of Algorithm 2, step by step:
each column points to the execution of a specific line. The sixth column shows
$q^{\prime}$ in $Q^{\prime}=stepChase(q,c)$ such that $q^{\prime}$ is
satisfiable and more restricted than $q$. Intermediate rewritten queries are
depicted in Figure 2b. Notice that queries $q^{\prime}_{21}$,
$q^{\prime}_{22}$ and $q^{\prime}_{31}$ are removed from $Q^{\prime}$ by the
isomorphic condition in Algorithm 1 (line 1), i.e. there exists an atom in
$body(q)$ that is isomorphic to the added atom in the rewriting step. Queries
$q_{41}$ and $q_{42}$ are removed by the condition at line 2 in Algorithm 2.
Thus, the rewriting result of $q$ w.r.t. $c_{1}$ and $c_{2}$ is the set of two
following rewritten queries: $q_{21}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y),Y\neq
a$ and
$q_{31}(X)\leftarrow L_{1}(X,a),L_{1}(X,b),L_{2}(X,a),L_{2}(X,b)$.
$\hfill\Box$

---

Line3 | Line5 |  $Q$(line3) | $q\in Q$ |  $Q^{\prime}$(line8) |  $q^{\prime}$(line10) |  $Q$(line16) | Changed
---|---|---|---|---|---|---|---
1 | $c_{1}$ |  {$q$} | $q$ |  {$q_{1}$} |  {$q_{1}$} |  {$q_{1}$} | T
| $c_{2}$ |  {$q_{1}$} | $q_{1}$ |  {$q_{21}$,$q_{22}$} |  {$q_{21}$,$q_{22}$} |  {$q_{21}$,$q_{22}$} | T
2 | $c_{1}$ |  {$q_{21}$,$q_{22}$} | $q_{21}$ | { } | { } |  {$q_{21}$,$q_{22}$} | F
|  |  | $q_{22}$ |  {$q_{31}$} |  {$q_{31}$} |  {$q_{21}$,$q_{31}$} | T
| $c_{2}$ |  {$q_{21}$,$q_{31}$} | $q_{21}$ |  {$q_{41}$,$q_{42}$} | { } |  {$q_{21}$,$q_{31}$} | F
|  |  | $q_{31}$ | { } | { } |  {$q_{21}$,$q_{31}$} | F

(a)  Intermediate results of Algorithm 2

Algo. 1 | $q^{\prime}$ | Remark
---|---|---
| $q(X)\leftarrow L_{1}(X,Y)$ |
$(q,c_{1})$ | $q_{1}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y)$ |
$(q_{1},c_{2})$ | $q_{21}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y),Y\neq a$ |
| $q_{22}(X)\leftarrow L_{1}(X,a),L_{2}(X,a),L_{1}(X,b)$ |
$(q_{21},c_{1})$ | $q^{\prime}_{21}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y),L_{2}(X,Y)$ | isomophism
$(q_{22},c_{1})$ | $q^{\prime}_{22}(X)\leftarrow L_{1}(X,a),L_{2}(X,a),L_{2}(X,a),L_{1}(X,b)$ | isomophism
$(q_{22},c_{1})$ | $q_{31}(X)\leftarrow L_{1}(X,a),L_{2}(X,a),L_{1}(X,b),L_{2}(X,b)$ |
$(q_{21},c_{2})$ | $q_{41}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y),Y\neq a,Y\neq a$ |  | not more
---
restricted than $q_{21}$
| $q_{42}(X)\leftarrow L_{1}(X,Y),L_{2}(X,Y),Y=a,L_{1}(X,b),Y\neq a$ | contradictory
$(q_{31},c_{2})$ | $q^{\prime}_{31}(X)\leftarrow L_{1}(X,a),L_{2}(X,a),L_{1}(X,b),L_{1}(X,b),L_{2}(X,b)$ | isomophism

(b)  Intermediate rewritten queries

Figure 2: Running Algorithm 2.

###  4.3 Correctness of Validation through rewriting queries

The complete proof of the correctness and completeness of Algorithm 2 is
presented in [21] (page 76). It concerns the following two propositions.

###### Proposition 1

Given a conjunctive query $q$ and a set of constraints $\hbox{${\cal
C}$}_{rw}$, Algorithm 2 finishes in a finite number of steps. $\hfill\Box$

proof : The rewriting algorithm is composed of two parts. The first part deals
with situations where the homomorphism $\nu$ exists. Therefore, when our
rewriting algorithm is restricted to these situations (i.e., when only lines 1
to 1 are executed in function StepChase (Algorithm 1)), it corresponds to the
chase with non weakly acyclic constraints $\hbox{${\cal C}$}_{1}$ (tgd) of a
conjunctive query $q$ (and therefore to the chase phase of algorithms
introduced in [11]). Thus, as in [11], which is based on proofs in [12], it
terminates. The second part considers the situation where the homomorphism
$\nu$ does not exist. In this situation, a query $q$ generates at least two
other queries. Clearly, the number of new queries that can be created during
the execution of lines 1 to 1 is finite and bounded by the number of variables
for which conditions on line 1 hold. From these observations and since the
number of constraints and queries is finite, Algorithm 2 terminates. Moreover,
after each execution of Algorithm 1 the new generated queries are compared to
those already existing, allowing to keep only the most restricted ones (along
the lines of [1]). $\Box$

###### Proposition 2

Let $\hbox{${\cal C}$}_{1}$ be the set of constraints obtained from a given
context ${\cal C}$ (where $\hbox{${\cal C}$}=\hbox{${\cal
C}$}_{P}\cup\hbox{${\cal C}$}_{N}$) by the preprocessing of negative
constraints. Let $\overline{(\hbox{${\cal S}$},\tau)}$ and $S_{aux}$ be,
respectively, the database instance and the auxiliary database obtained on the
basis of Definition 5. For any database instance $\overline{(\hbox{${\cal
S}$},\tau)}$, we have $q(\hbox{$\overline{(\hbox{${\cal
S}$},\tau)}$},\hbox{${\cal C}$})=q_{r}(\hbox{$\overline{(\hbox{${\cal
S}$},\tau)}$}\cup S_{aux})$ where $q(\hbox{$\overline{(\hbox{${\cal
S}$},\tau)}$},\hbox{${\cal C}$})$ is the set of valid answers of $q$ (with
respect to ${\cal C}$) on $\overline{(\hbox{${\cal S}$},\tau)}$ and
$q_{r}(\hbox{$\overline{(\hbox{${\cal S}$},\tau)}$}\cup S_{aux})$ is the set
of answers of $q_{r}$ on $\hbox{$\overline{(\hbox{${\cal S}$},\tau)}$}\cup
S_{aux}$ with respect to the translated set of constraints $\hbox{${\cal
C}$}_{1}$. $\Box$

proof: (Sketch) The proof is done by contradiction and is based on two lemmas.
The first lemma deals with the situation where ${\cal C}$ has only a positive
constraint whose body cannot be mapped to an atom in the query’s body
(although a unifier exits) (as on line 1 Algorithm 1). We prove that the
corresponding rewritten query $q_{r}$ computes all and only the $q$’s answers
which are valid with respect to ${\cal C}$. The second lemma proves that when
${\cal C}$ has only one negative constraint of the form
$c:A(v_{1}),B(v_{2})\rightarrow\bot$ whose body is triggered by an atom in the
query’s body, the corresponding rewritten query $q_{r}$ computes all and only
the $q$’s answers which are valid with respect to ${\cal C}$. Moreover, it
proves that, in this situation, query $q_{r}$ involves auxiliary instances
computed according to Definition 5 and stored in $S_{aux}$. $\Box$

###  4.4 The whole validation process

The query rewriting process (Algorithms 1 and 2) only deals with $C_{P}$ and
$C_{N}$ (besides $\tau_{in}$). To verify if the results obtained from
evaluations of rewritten queries respect constraints in $C_{K}$, the naive
approach is used. This overall process is depicted in Algorithm 3.

Input : $\bullet$ A conjunctive query $q:\tau_{in}$ and a set of constraints
$\hbox{${\cal C}$}=C_{P}\cup C_{N}\cup C_{K}$.

$\bullet$ An access to the database instance $\overline{(\hbox{${\cal
S}$},\tau)}$

Output : Answers of $q:\tau_{in}$ respecting ${\cal C}$.

1 Function  _valCandAns(_$q:\tau_{in},\hbox{${\cal C}$}$_)_:

2

3 $\textsf{AnsSet}=\emptyset$;

4 $C_{rw}=C_{P}\cup RewritingNegConstraints(C_{N});$

5 $Q=RewriteQuery(q:\tau_{in},C_{rw})$;

6 $\textsf{Solutions}=Eval(Q,\hbox{$\overline{(\hbox{${\cal S}$},\tau)}$})$;

7 $\textit{Cache}=CreateCache()$;

8 foreach  _$sol\in\textsf{Solutions}$ where $sol=(t,h_{t})$_ do

9 if  _$\textit{Valid}(sol,\hbox{${\cal C}$}_{K},\textit{Cache},\tau_{in})$ _
then

10 $\textsf{AnsSet}:=\textsf{AnsSet}\cup\\{t\\}$;

11

12 return _$AnsSet$_ ;

Algorithm 3 Valid candidate answers

Function $RewriteQuery$ on line 3 of the Algorithm 3 uses constraints in
$C_{rw}$ as rewriting rules to reformulate $q:\tau_{in}$ into a set $Q$ of
rewritten queries. Function $Eval$ (line 3) then computes the union of the
candidate answers sets for each rewritten query $q^{\prime}:\tau_{in}\in Q$.
These candidate answers are stored in the set Solutions. Note that each
candidate answer is computed on $\overline{(\hbox{${\cal S}$},\tau)}$ w.r.t.
$C_{P}$, $C_{N}$, $\tau_{in}$, and they are stored in Solutions in the form of
a pair $(t,h_{t})$, where $h_{t}$ is the homomorphism used to produce tuple
$t$ as an answer to a query $q\in Q$. We need $h_{t}$ for creating the
auxiliary query that is used to validate $t$ in the next step. Function
$Valid$ verifies whether a candidate answer $sol$ is valid w.r.t.
$\hbox{${\cal C}$}_{K}$ and $\tau_{in}$ on $\overline{(\hbox{${\cal
S}$},\tau)}$ by generating corresponding auxiliary queries. $Valid$ implements
the verification concerning $\hbox{${\cal C}$}_{K}$ and is performed by the
naive algorithm. A cache can be used to store the results of auxiliary queries
to avoid overcharging data sources (lines 3,3).

##  5 Experimental Study

To the best of our knowledge, there is no similar system that supports
semantic web data querying and that verifies results to obtain user’s quality-
driven answers. Ideas in [11, 12, 16] are similar to ours, but they are used
to other purposes. Those in [4, 6, 5, 18] lack the use of constraints to
filter answers – our main contribution. Comparing our proposal to these
systems would require too heavy adaptations. Hence, our option is to evaluate
the performance of the different versions of our Validator, namely the Naive
(mentioned in Section 3) and the Rewriting approaches. Both prototypes have
been implemented in Java; developed on the basis of Graal’s
framework222https://graphik-team.github.io/graal/  and tests have been carried
out on an HP ZBook with a quad-core Intel i7-4800MQ processors at 2.7GHz with
32KBx4 L1 Cache, 256KBx4 L2 Cache, 6MB L3 Cache, 16GB 799MHz RAM, and a 120 GB
hard drive. A 64-bit Windows 10 operating system and the 64-bit Java VM
1.8.031 constitute the software environment.

Experiments are built on the LUBM benchmark333Lehigh University:
http://swat.cse.lehigh.edu/projects/lubm/, which describes the structure of
universities with 43 classes and 32 properties, and provides a generator of
synthetic data with varying size. We devised 7 queries and 13 constraints over
the LUBM ontology (5 positive, 5 negative, and 3 key) c.f.[21] (page 89). Our
queries spread from simple ones, with few atoms ($Q1$, $Q2$) to more complex
ones ($Q6$, $Q7$). The number of answers vary: $Q2$, $Q4$, $Q6$ give large
result sets while $Q5$, $Q7$ return small ones. The constraint triggering
chain can involve more than one constraint. Constants appear in some queries
or constraints allowing us to also evaluate the most original aspect of our
work: constraints with constants not appearing in queries. This is a fine-
grained contribution of practical significance – constants are commonly used
in real life scenarios.

With the UBA Data Generator provided by the LUBM, we produced two
ABoxesdatasets of different sizes: Dataset 1 contains data of one university,
with 86,165 triples and Dataset 5 concerns 5 universities with 515,064
triples. Produced by LUBM’s generator, those datasets are consistent with the
inference rules of LUBM, but may be inconsistent with 13 constraints of our
experiment.

|  |  | Dataset 1 | Dataset 5
---|---|---|---|---
|  | Num.of
---
atoms in
original
query
| Num.of
---
involved
constr.
| Num.of
---
ans. of
original
query
| Num.
---
of
valid
ans.
| Num.of
---
eval.
queries
| Eval.
---
time
| Verif.
---
time
| Total
---
time
| Num.of
---
ans.s of
original
query
| Num
---
of
valid
ans.
| Num.of
---
eval.
queries
| Eval.
---
time
| Verif.
---
time
| Total
---
time
Q1 | 1 | 8 | 1544 | 523 | 6449 | 0.368 | 4.306 | 4.674 | 10095 | 3319 | 42583 | 2.971 | 77.479 | 80.45
Q2 | 1 | 1 | 7861 | 7861 | 7862 | 0.109 | 47.769 | 47.878 | 36682 | 36682 | 36683 | 0.454 | 659.937 | 660.391
Q3 | 2 | 2 | 1822 | 1821 | 3600 | 0.039 | 1.911 | 1.95 | 11900 | 11900 | 23750 | 5.96 | 12.177 | 18.137
Q4 | 2 | 0 | 5939 | 5939 | 1 | 0.033 | 0.364 | 0.397 | 37854 | 37854 | 1 | 0.55 | 2.008 | 5.021
Q5 | 3 | 10 | 50 | 50 | 601 | 0.278 | 0.609 | 0.887 | 59 | 59 | 886 | 1.975 | 2.73 | 4.705
Q6 | 4 | 10 | 6564 | 6564 | 137977 | 8.218 | 127.19 | 135.408 | 36008 | N/A | N/A | 12.617 | oom.err | N/A
Q7 | 4 | 9 | 94 | 21 | 502 | 14.512 | 0.296 | 14.808 | 644 | 219 | 4328 | 326.689 | 5.244 | 331.933

(time in seconds)

Table 3: Evaluation and Verification in the Naive Approach

Table 3 reports the result of the Naive approach which consists of two main
steps: query evaluation to obtain initial results which are, then, checked
w.r.t. constraints, through sub-queries. The first two columns indicate, for
each query, the number of atoms (i.e., its complexity) and the number of
constraints it triggers. The remaining columns include information about the
execution time and the number of returned results for the original query, the
number of answers which are valid w.r.t. the constraints, the number of
auxiliary sub-queries needed to perform the constraint verification and the
total time required for the process.

Naive algorithm can handle well small data sets, but, large datasets may
provoke memory overflow (e.g. $Q6$) due to the great number of auxiliary sub-
queries, generated in a process which is similar to the chase. Most of our
tests show that the verification step is the most time-consuming step. For
$Q7$, however, the evaluating time of the complex original query is
significantly greater than the validating time for the small number of results
(94 and 644 answers in $Dataset\ 1$ and $Dataset\ 5$, respectively).

|  |  |  |  | Dataset 1 | Dataset 5
---|---|---|---|---|---|---
|  | Num.
---
of
invol.
const.
| Num.
---
of
rew.
queries
| Max num
---
of atomes
in rew.
queries
| Rewriting
---
time
| Num.
---
of
valid
ans.
| Eval.
---
time
| Verif.
---
time
(for CKs)
| Total
---
time
| Num.
---
of
valid
ans.
| Eval.
---
time
| Verif.
---
time
(for CKs)
| Total
---
time
Q1 | 8 | 1 | 8 | 0.017 | 523 | 0.473 | 2.094 | 2.584 | 3319 | 1.791 | 10.111 | 11.919
Q2 | 1 | 1 | 2 | 0.001 | 7861 | 0.14 | 0.07 | 0.211 | 36682 | 1.221 | 0.407 | 1.629
Q3 | 2 | 2 | 5 | 0.001 | 1821 | 0.109 | 0.078 | 0.188 | 11900 | 1.221 | 0.297 | 1.519
Q4 | 0 | 1 | 2 | 0 | 5939 | 0.031 | 0.061 | 0.092 | 37854 | 0.544 | 0.447 | 1.427
Q5 | 11 | 1 | 12 | 0.01 | 50 | 6.83 | 0.153 | 6.993 | 59 | 9.37 | 0.249 | 9.629
Q6 | 14 | 1 | 12 | 0.005 | 6564 | 25.296 | 19.351 | 44.652 | 35922 | 85.293 | 113.451 | 198.749
Q7 | 11 | 1 | 12 | 0.008 | 21 | 1.427 | 0.313 | 0.992 | 219 | 14.561 | 1.417 | 15.986

(time in seconds)

Table 4: Evaluation and Verification of Rewriting Approach

We now turn our attention to the results of the rewriting approach which
consists of four steps.

  * •

The preprocessing step is performed once for each user-setting-context on a
database instance. Auxiliary relations either are materialized and managed in
the local system or stored as views computed at evaluating-time. To simplify,
the former was realized in the current implementation. Naturally, the
preprocessing time is directly proportional to the size of the dataset.
Clearly, the number of constraints may increase after this step.

  * •

The rewriting step uses positive constraints and transformed negative
constraints as rewriting rules to reformulate the initial query. This step is
completely independent of data in sources. Theoretically, in the worst case,
the number of reformulations of a query can grow exponentially, because each
constant in a constraint can lead to two new reformulations. However, thanks
to the test conditions for containment and contradiction in Query Rewriting
Algorithm (line 2 Algorithm 2), only useful reformulations are accepted. Our
experimental results proved that the number of rewritten queries can be very
small even if the number of involved constraints is not small ($Q1$, $Q5$,
$Q6$, $Q7$ in Table 4). By the way, although rewritings are very fast and, in
all cases, the total time is mostly impacted by the evaluation and
verification time, the rewritten-query complexity affects the evaluation time
(e.g. evaluation time for the rewritten queries of Q6 and Q7, with 12 atoms in
their bodies is high).

  * •

The two last steps are the evaluation of rewritten queries followed by the
verification of the obtained results w.r.t. key constraints. The first
noteworthy result is that the rewriting approach has produced answers in all
tested cases. Moreover, as expected, as in the naive approach, the total
processing time is directly proportional to the size of the dataset.

Figure 3: Comparison of total time of Naive approach and Rewrite approach

Figure 3 is a summary of the total processing time for both approaches.
Whether working on small or large dataset, whether treating simple (e.g.
$Q1$, $Q2$) or complex (e.g.  $Q6$, $Q7$) initial query, whether having few
(e.g.  $Q2$, $Q4$) or many (e.g.  $Q6$, $Q7$) involved constraints, the
rewriting approach always requires less processing time. Thus, the rewriting
approach is more efficient than the naive one. This better performance is
partially explained by our fined-grained method which treats the presence of
constants by adding atoms (e.g.  $Q7$), a solution which can highly reduce
querying space. Naive approach is better only for $Q5$, a special case: $Q5$’s
answer set is very small (only 50 answers on the dataset 1, or 59 on the
dataset 5).

##  6 Conclusions

This paper details our solution for validating a set of user quality
constraints and confidence degrees when performing query evaluation. We
present it formally and discuss experimental results demonstrating that the
validation cost is reasonable, and further reduced with our proposed rewriting
techniques. This is true in particular when constants appear in queries and
constraints, and even for constraints with constants not appearing in queries.
This is the most original aspect of our work, of practical significance as
constants are commonly used in real life scenarios. As a future work we plan
plan to study to which extent our solution would apply to the verification of
some SHACL constraints on results from SPARQL Endpoints.

## References

  * [1] Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases, vol. 8. Addison-Wesley Reading (1995)
  * [2] Abiteboul, S., Manolescu, I., Rigaux, P., Rousset, M.C., Senellart, P.: Web Data Management. Cambridge University Press, New York, NY, USA (2011)
  * [3] Benedikt, M., Konstantinidis, G., Mecca, G., Motik, B., Papotti, P., Santoro, D., Tsamoura, E.: Benchmarking the chase. In: Proc. of the 36th ACM SIGMOD-SIGACT-SIGAI Symp. on Principles of Database Systems. pp. 37–52. PODS ’17, ACM (2017)
  * [4] Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. J. Web Sem. 14, 57–83 (2012)
  * [5] Calì, A., Gottlob, G., Pieris, A.: Advanced processing for ontological queries. Proc. VLDB Endow. 3(1-2), 554–565 (Sep 2010)
  * [6] Cali, A., Lembo, D., Rosati, R.: Query rewriting and answering under constraints in data integration systems. In: Proc. of the 18th Int. Joint Conf. on Artificial Intelligence. pp. 16–21. IJCAI’03, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (2003)
  * [7] Chabin, J., Halfeld Ferrari, M., Laurent, D.: Consistent updating of databases with marked nulls. Knowl. Inf. Syst. 62(4), 1571–1609 (2020)
  * [8] Chabin, J., Halfeld-Ferrari, M., Markhoff, B., Nguyen, T.B.: Validating data from semantic web providers. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018: Theory and Practice of Computer Science. pp. 682–695. Springer International Publishing, Cham (2018)
  * [9] Cima, G., Lembo, D., Marconi, L., Rosati, R., Savo, D.F.: Controlled Query Evaluation in Ontology-Based Data Access. In: The Semantic Web – ISWC 2020. pp. 128–146. Springer International Publishing (2020)
  * [10] Deutsch, A., Popa, L., Tannen, V.: Physical data independence, constraints, and optimization with universal plans. In: VLDB’99, Proc. of 25th Int. Conf. on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. pp. 459–470 (1999)
  * [11] Deutsch, A., Popa, L., Tannen, V.: Query reformulation with constraints. SIGMOD Rec. 35(1), 65–73 (Mar 2006)
  * [12] Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (May 2005)
  * [13] Goasdoué, F., Manolescu, I., Roatiş, A.: Efficient query answering against dynamic RDF databases. In: Proc. of the 16th Int. Conf. on Extending Database Technology. pp. 299–310. EDBT ’13, ACM, NY, USA (2013)
  * [14] Gottlob, G., Orsi, G., Pieris, A.: Ontological queries: Rewriting and optimization. In: ICDE. pp. 2–13 (2011)
  * [15] Grieco, L., Lembo, D., Rosati, R., Ruzzi, M.: Consistent query answering under key and exclusion dependencies: Algorithms and experiments. In: Proc. of the 14th ACM Int. Conf. on Information and Knowledge Management. pp. 792–799. CIKM ’05, ACM, NY, USA (2005)
  * [16] Ileana, I., Cautis, B., Deutsch, A., Katsis, Y.: Complete yet practical search for minimal query reformulations under constraints. In: Proc. of the 2014 ACM SIGMOD Int. Conf. on Management of Data. pp. 1015–1026. SIGMOD ’14, ACM, NY, USA (2014)
  * [17] Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167–189 (1984)
  * [18] Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant query answering in ontology-based data access. Web Semantics: Science, Services and Agents on the World Wide Web 33, 3 – 29 (2015)
  * [19] Lukasiewicz, T., Martinez, M.V., Simari, G.I.: Inconsistency-tolerant query rewriting for linear datalog+/–. In: Barceló, P., Pichler, R. (eds.) Datalog in Academia and Industry. pp. 123–134. Springer Berlin Heidelberg, Berlin, Heidelberg (2012)
  * [20] Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM Trans. Database Syst. 4(4), 455–469 (Dec 1979)
  * [21] Nguyen, T.B.: L’interrogation du web de données garantissant des réponses valides par rapport à des critères donnés (in English). Theses, Université d’Orléans (Dec 2018), https://tel.archives-ouvertes.fr/tel-02426935
  * [22] Onet, A.: The chase procedure and its applications in data exchange. In: Data Exchange, Integration, and Streams, pp. 1–37. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2013)
  * [23] Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. In: Journal on data semantics X, pp. 133–173. Springer (2008)
  * [24] Rosati, R., Ruzzi, M., Graziosi, M., Masotti, G.: Evaluation of techniques for inconsistency handling in owl 2 ql ontologies. In: Proceedings of the 11th International Conference on The Semantic Web - Volume Part II. pp. 337–349. ISWC’12, Springer-Verlag, Berlin, Heidelberg (2012)
  * [25] Schwarte, A., Haase, P., Hose, K., Schenkel, R., Schmidt, M.: FedX: Optimization Techniques for Federated Query Processing on Linked Data. In: ISWC. pp. 601–616 (2011)