Hs

Key Tuples B 0 02, d4, 2 HD Key Tuples

Abstract

The inconsistency problems in databases and knowledge bases have been largely tackled and discussed in the last forty years. Inconsistency is one of the main dimensions of data quality. In our era, data is the new gold, but data without quality or lack of quality measures is another burden leading to erroneous and uninformative analysis results from data. The inconsistency problem arises when a set of constraints that have to be satisfied by the database instance are violated by this database instance. All the previous works that deal with the problem of inconsistency are focused on either the repair of the inconsistent database to obtain a new database that is consistent (i.e, there is no violation of constraints), or quantification of the inconsistency in the entire database. In this thesis, we propose a new approach to handle inconsistency in relational database by quantifying it on the level of tuples, and then ranking tuples/answers according to their inconsistency to enable choosing among query answers the most consistent/inconsistent ones. So, we define different new of measures of inconsistency degrees that based either on tuples violation (tuple-based approach) or on constraints violation(constraint-based approach). We consider the class of denial constraints as class of constraints and the class of conjunctive queries as class of queries. We leverage why-provenance and polynomial provenance to identify inconsistent tuples and to compute inconsistency degrees of query answers, respectively. We convert each denial constraint into a boolean conjunctive query and evaluate this last one on database to compute the why-provenance of the true answer. Using why-provenance, each tuple in the database is annotated with the set of constraints that it violates and its identifiers in a monomial form (otherwise, i.e, the tuple does not involve in violation of any constraint, then it is annotated by the monomial 1), then we obtain an annotated database. Given a conjunctive query Q, Q is evaluated on the annotated database and each answer is computed with a polynomial provenance that encodes in a polynomial formula the set of constraints violated by the answers as well as the set of tuples used to compute answer and involved in violation of these constraints. Then, we define twelve measures of inconsistency degrees using the polynomial provenance of answers. Once, measures of inconsistency are defined, it is interesting to allow ranking of answers (tuples in database) according to their inconsistency degrees. We design a set of top-k algorithms, including TopINC on which the idea of other algorithms is based, allowing to rank the query answers according to their inconsistency degrees. We introduce a new class of algorithms with a new cost model and shown the optimality of these top-k algorithms in some specifics conditions. Also, for each top-k algorithm, we give its theoretical complexity. We have conducted a large experiment to show the feasibility of our approach in practice and also to show the efficiency of our top-k developed algorithms. Key words: Inconsistency, Inconsistency Measure, Top-K Algorithm, Provenance, Conjunctive Query, Denial Constraint

Résumé

Les problèmes de l'incohérence dans les bases de données et les bases de connaissances ont été largement abordés et discutés au cours des quarante dernières années. L'incohérence est l'une des principales dimensions de la qualité des données. À notre époque, les données sont le nouvel or, mais les données sans qualité ou l'absence de mesures de qualité peuvent entraîner d'autres fardeaux qui conduisent à des résultats d'analyse erronés et peu informatifs à partir des données. Le problème de l'incohérence survient lorsqu'un ensemble de contraintes qui doivent être satisfaites par l'instance de la base de données sont violées par cette instance. Les travaux précédents qui traitent du problème de l'incohérence se sont intéressés soit de la réparation de la base de données incohérente pour obtenir une nouvelle base de données qui est cohérente (c'est-à-dire qu'il n'y a pas de violation des contraintes), soit sur la quantification de l'incohérence dans la base de données entière. Dans cette thèse, nous proposons une nouvelle approche pour gérer l'incohérence dans les bases de données relationnelles en la quantifiant au niveau des tuples, puis en classant les tuples/réponses selon leur incohérence pour permettre de choisir parmi les réponses aux requêtes celles qui sont les plus cohérentes/inconsistantes. Ainsi, nous définissons différentes nouvelles mesures de degrés de l'incohérence basées soit sur la violation des tuples. Nous considérons la classe des contraintes de déni( denial constraint en anglais) et la classe des requêtes conjonctives. Nous tirons parti des méthodes why-provenance et polynomial provenance pour identifier les tuples incohérents et pour calculer les degrés de l'incohérence des réponses aux requêtes, respectivement. Nous convertissons chaque contrainte de déni en une requête booléenne conjonctive et évaluons cette dernière sur la base de données pour calculer le why-provenance de la réponse true. En utilisant le why-provenance, chaque ligne de la base de données est annotée avec l'ensemble des contraintes qu'elle viole et son identifiant sous une forme de monôme (dans le cas contraire, c'est-à-dire si la ligne de donées n'est impliquée dans aucune violation de contrainte, elle est alors annotée par le monôme 1), on obtient alors une base de données annotée. Étant donné une requête conjonctive Q, Q est évaluée sur la base de données annotée et chaque réponse est calculée avec une provenance polynomiale qui encode dans une formule polynomiale l'ensemble des contraintes violées par les réponses ainsi que l'ensemble des lignes de données utilisées pour calculer la réponse et impliquées dans la violation de ces contraintes. Ensuite, nous définissons douze mesures de degré de l'incohérence en utilisant la provenance polynomiale des réponses. Une fois les mesures d'incohérence définies, il est intéressant de permettre le classement des réponses aux rêquetes en fonction de leur degré d'incohérence. Nous concevons un ensemble d'algorithmes de top-k, dont TopINC sur lequel est basée l'idée des autres algorithmes, permettant de classer les réponses aux requêtes en fonction de leurs degrés d'incohérence. Nous introduisons une nouvelle classe d'algorithmes avec un nouveau modèle de coût et montrons l'optimalité de ces algorithmes de top-k dans certaines conditions spécifiques. De plus, pour chaque algorithme de top-k, nous donnons sa complexité théorique. Nous avons mené une grande expérience pour montrer la faisabilité de notre approche en pratique et aussi pour montrer l'efficacité de nos algorithmes de top-k développés.

À la mémoire de mes Papas : À mon défunt Papa Issa OUSMANE, À mon défunt Oncle Issiaka NOUHOU, À mon défunt Tonton Ousmane DOUMBIA «Il n'y a le défaut que s'il est entraitenu». «Maitriser l'incohérence c'est se rapporcher de la perfection». «Mais l'incohérence n'est pas le monopole des fous: toutes les idées essentielles d'un homme sain sont des constructions irrationnelles». André Maurois

List of Figures

INTRODUCTION

In the last twenty years, special attention has been given to the problem of data quality [START_REF] Batini | Data Quality Issues in Data Integration Systems[END_REF][START_REF] Fan | Data quality: From theory to practice[END_REF][START_REF] Fan | Foundations of Data Quality Management[END_REF][START_REF] Laranjeiro | A survey on data quality: Classifying poor data[END_REF]. Poor data quality can cause major problems in decision making in private companies and public organizations [START_REF] Fisher | Criticality of data quality as exemplified in two disasters[END_REF]. Hence, It is essential to alleviate this problem and bring concrete solutions. Nowadays, with the evolution of artificial intelligence, the quality of the data plays an important role in the quality of models and algorithms.

There are several dimensions of data quality [START_REF] Redman | Data Quality for the Information Age[END_REF][START_REF] Sidi | Data quality: A survey of data quality dimensions[END_REF]. Among which the most important ones are [START_REF] Sidi | Data quality: A survey of data quality dimensions[END_REF]:

• data completeness: it treats the missing data problem; it gives also information about how the real world is entirely represented by data [START_REF] Batini | Methodologies for data quality assessment and improvement[END_REF].

• data accuracy: it is concerned with the design of a set of tools to ensure the correctness of stored data [START_REF] Batini | Methodologies for data quality assessment and improvement[END_REF][START_REF] Wang | Beyond accuracy: What data quality means to data consumers[END_REF].

• data currency: it is about the data freshness [START_REF] Batini | Methodologies for data quality assessment and improvement[END_REF][START_REF] Redman | Data Quality for the Information Age[END_REF].

• data consistency: it concerns the reliability of data in compliance with a set of constraints that have to be satisfied by data [START_REF] Batini | Methodologies for data quality assessment and improvement[END_REF]. Integrity constraints are notable class of such constraints.

This thesis focuses on data inconsistency. There is inconsistency in data when at least one of the set of these constraints, that have to be satisfied, is violated by these data.

Inconsistency can be introduced in database for various reasons, among these reasons we have:

• data integration, that consists to combine (heterogeneous) data from many sources [START_REF] Decker | Modeling, Measuring and Monitoring the Quality of Information[END_REF][START_REF] Lenzerini | Data integration: A theoretical perspective[END_REF],

• temporary disabling of constraints checking in relational databases [START_REF] Decker | Modeling, Measuring and Monitoring the Quality of Information[END_REF],

• application of new constraints to stored data in databases [START_REF] Decker | Modeling, Measuring and Monitoring the Quality of Information[END_REF],

• human mis-typing during data entry in database,

• inconsistency in set of constraints defined on databases, etc.. Several research problems around inconsistency have been conducted such as fixing the inconsistency problem in knowledge databases [START_REF] Nuel | A Useful Four-Valued Logic[END_REF][START_REF] Benferhat | Some Syntactic Approaches to the Handling of Inconsistent Knowledge Bases: A Comparative Study Part 1: The Flat Case[END_REF][START_REF] Newton | On the theory of inconsistent formal systems[END_REF][START_REF] Hunter | Managing inconsistent specifications: reasoning, analysis, and action[END_REF], database repairing and consistent query answers [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF][START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF], data cleaning [START_REF] Chu | Data cleaning: Overview and emerging challenges[END_REF], constraints checking (by quantifying inconsistency, for example, before any update operation in databases) [START_REF] Decker | Modeling, Measuring and Monitoring the Quality of Information[END_REF]. However, little attention has been paid to leaving the database instances intact and quantifying their degrees of inconsistency at different levels of granularity (tuple, sets of tuples, attribute, set of attributes, etc..). Such a characterization enables the users of a DBMS to quantify the level of trust that they shall expect from the data that they query and manipulate. In our work, we are interested in augmenting relational instances with novel inconsistency measures that can also be propagated to query results. The inconsistency degrees of an answer of a given query is determined by relying on provenance-based information of the input tuples involved in the computation of this answer. We first leverage why-provenance in order to identify the inconsistent base tuples of a relational instance with respect to a set of denial constraints. Then, we rely on provenance polynomials [START_REF] Green | Provenance semirings[END_REF] in order to propagate the annotations of inconsistencies from the base tuples to the answer tuples of conjunctive queries. Building upon the computed annotations, we define twelve measures of inconsistency degrees, which consider single and multiple violations of constraints and tuples. Since some of our measures are non-monotonic functions, we design new top-k algorithms to rank the top-k results of a query w.r.t. the inconsistency measures, as presented in table 1.1. Since the existing cost models are not suited to our context, we introduce a new class of algorithms called SBA and a new cost function denoted cost ∆ tailored to generic scoring function(monotonic and non monotonic). We show the optimality our top-k algorithms in SBA w.r.t the cost function cost ∆ .

We envision several applications of our framework, as follows. Inconsistency-aware queries for analytical tasks, as we expect that our framework enables inconsistency quantification in querying and analytical tasks within data science pipelines. Our annotations are not merely numbers and convey provenance-based information about the violated constraints, the latter being viable for user consumption in data science tasks. External annotations for data cleaning pipelines, as our approach can also ease data cleaning tasks in tools such as OpenRefine, Wrangler and Tableau by injecting into them the external information of inconsistency indicators and putting upfront the resulting ranking prior to cleaning and curation. Approximation schemes for integrity constraints that have been used in order to guarantee a polynomial number of samples in recent probabilistic inference approaches for data cleaning [START_REF] Rekatsinas | Holoclean: Holistic data repairs with probabilistic inference[END_REF]. We believe that an alternative to constraint approximation would be to build samples based on the top-k number of constraints leading to the most consistent (the least consistent, respectively) tuples. Combined ranking as our quality-informed ranking can be combined with other ranking criteria, e.g. user preferences in recommender systems and unfairness and discrimination in marketplaces and search sites [START_REF] Amer-Yahia | Fairness in online jobs: A case study on taskrabbit and google[END_REF].

Contributions

We introduce a novel framework to manage inconsistency in relational database. As shown in figure 1.1, we consider as an input of the framework a database and a set of denial constraints, then, we deploy two-steps process:

• Preprocessing step, we convert this input database, according to the set of denial constraints, into another database where each tuple is annotated with the set of constraints it violates. We rely on why-provenance [START_REF] Deutch | Circuits for datalog provenance[END_REF][START_REF] Green | Containment of conjunctive queries on annotated relations[END_REF] to compute such annotations. • Query evaluation step, we consider as class of queries the class of conjunctive queries. The queries are evaluated on the converted database using polynomial provenance [START_REF] Green | Provenance semirings[END_REF]. In the step of query evaluation, query answers can be ranked according to their inconsistency degrees and the k first interesting answers (the most consistent/inconsistent) are chosen using one of the top-k algorithms defined in this thesis.

Constraint-based measures

In this thesis we make the following technical contributions:

1. We design novel measures of inconsistency degrees of answer for conjunctive queries over an inconsistent database in the presence of a set of denial constraints 4.4. In particular, we consider two approaches to quantify inconsistency of query answers:

• Tuple-based approach, let t be a query answer, this class of measures counts the number of inconsistent tuples involved in computation of t. We propose six different measures of inconsistency of query answers in this class [START_REF] Issa | A relational framework for inconsistency-aware query answering[END_REF].

• Constraint-based approach, considering t a query answer, this class of measures counts the number of constraints violated by the tuples involved in computation of t. We proposed six measures of inconsistency of query answers in this class [START_REF] Issa | Evaluating top-k queries with inconsistency degrees[END_REF].

2. We define top-k problems and threshold problems based on these measures [START_REF] Issa | Evaluating top-k queries with inconsistency degrees[END_REF].

• We classify the top-k algorithms into two classes, Disk-based algorithms and Memory-based algorithms, according to the nature of the cost model that they minimize.

• We design new top-k algorithms to efficiently compute top-k answers in the context where the input scoring functions are the set of measures defined above. • We define a new class of algorithms called semi-blind algorithms (SBA) that contains both algorithms working with monotonic scoring functions and those working with non-monotonic scoring functions.

We theoretically show the efficiency of these algorithms

• We introduce a new cost model denoted cost ∆ that minimizes the number of tuples read on disk while avoiding indeterminism caused by the tuples having the same score but different values in join attributes.

• We show optimality of these top-k algorithms in SBA class w.r.t our new cost model cost ∆ for algorithms in Disk-based. For the algorithms in Memorybased, we show that they are polynomial in data complexity.

4. We experimentally show efficiencies of our main algorithm [START_REF] Issa | Evaluating top-k queries with inconsistency degrees[END_REF].

• The running time of some measures is studied and analyzed.

• The time consumed by the preprocessing phase is also analyzed.

• We experimentally lead a quality evaluation of some measures.

5. We develop a tool, called INCA system, that allows users to explore data profiling and query answering profiling based on inconsistency quantification.

6. We present a preliminary work to handle inconsistency in a setting where the set of constraints are inconsistent.

Organization

This thesis is organized as follows: Chapter 2 presents the background; Chapter 3 discusses the state of art; Chapter 4 introduces the set of measures of inconsistency degrees proposed in this thesis; Chapter 5 presents different top-k algorithms for the proposed inconsistency measures; Chapter 6 extends measures of inconsistency with new measures in the context of presence of inconsistency in the set of constraints; Chapter 7 is dedicated to the experimentations and evaluations of the proposed measures and top-k algorithms; Chapter 8 explores our inconsistency prototype INCA system; Chapter 9 concludes this thesis and gives some perspectives.

In the next chapter we describe the necessary background to this thesis in database management field.

Chapter 2

PRELIMINARY NOTIONS

This chapter introduces some basic notions and notations used throughout this thesis. First, we recall some relevant concepts in relational database and then we present different notions in top-k processing and optimal join processing.

Relational Database

We assume that the reader is familiarized with relational database [START_REF] Abiteboul | Foundations of Databases[END_REF].

We provide the formal definition of a relational database [START_REF] Abiteboul | Foundations of Databases[END_REF] and different notations used throughout this thesis. The domain of the database is an infinite set of constants, denoted by D. The database schema, denoted S = {R 1 , . . . , R n } is a finite set of relations/predicates such that D ∩ S = ∅. Let SetAttrs be a countable infinite set of attribute names such that S ∩ SetAttrs = ∅ and D ∩ SetAttrs = ∅. On each relation R ∈ S the function Attr associates a set of attributes from SetAttrs (i.e, Attr : S → P f in (SetAttrs), with P f in (SetAttrs) the finitary powerset of SetAttrs). Given a relation R, then Attr(R) is called the set of attributes of R. A tuple t is a function from a finite subset A ∈ P f in (SetAttrs) to the domain D; we say that t is a tuple from set of attributes A. A relation R ∈ S is a finite set of tuples from Attr(R). We denote by R(t) with t a tuple to mean that the tuple t is in a relation R, denoted also by t ∈ R. A relational database (or shortly database or instance) from a schema S and a domain D, is a finite set of relations from the schema S [START_REF] Abiteboul | Foundations of Databases[END_REF]. A relation in a database instance I is denoted by I(R). Let id be a function that associates to each tuple an unique identifier, so the identifier of a tuple t is denoted id(t). We denote Γ by the set of all identifiers of the instance of the database considered.

Conjunctive Query

In the following, we introduce conjunctive query, i.e, the main class of queries used in this thesis. The class of conjunctive queries (CQ) is defined as a set of queries of the following form:

Q(u) ← R 1 (u 1 ), ..., R n (u m ), φ(u 1 , . . . , u m ) (2.1)
where each R i is a relation symbol in S and Q is a relation symbol in the output schema O, each u i is a tuple of variables or/and constants having the same arity as R i , and u is a tuple of distinguished variables. Those are variables occurring in query in tuples u i with i ∈ {1, . . . , m}, i.e, Var(u) ⊆ i∈{1,...,m} Var(u i ) with Var a function that returns the set of variables in a tuple) or/and constants. The formula φ(u 1 , . . . , u m ) is a conjunction of built-in atom under the form x op y where op ∈ {=, =, ≥, ≤, <, >} (op is a arithmetical predicate), with x and y being either variables from i∈{1,...,m} Var(u i ) or constant. The set of variable in a query Q is denoted Vars (Q). When the conjunctive query does not contain a built-in part or the built-in part contains only equal (=) predicates then it is called an equi-conjunctive query. Any equi-conjunctive query can be converted into an equi-conjunctive query that contains no built-in formula (each builtin predicate x = y is eliminated by rename each instance of y to x). We say that Q is a

full conjunctive query if Var(u) = m i=1
Var(u i ).

A valuation of Q over a domain D is a function v : Vars(Q) → D, extended to be the identity on constants, i.e, for each e ∈ D then v(e) = e. For a tuple t = (a 1 , . . . , a p ) consisting of variables and/or constraints, v(t) = (v(a 1 ), . . . , v(a p )). The result (or query answers) Q(I ) of executing a query Q over an instance I is:

Q(I ) = {v(u)|v is a valuation over Vars(Q) and ∀i ∈ [1, n], v(u i ) ∈ I(R i ) and φ(v(u 1 ), . . . , v(u m )) is true }.
An union of conjunctive queries, denoted UCQ, is a set of conjunctive queries with the same output predicate. Let Q be a conjunctive query, Q is a self-join conjunctive query if there are at least two relation atoms in Q, R i and R j , such that R i = R j , i = j and i, j ∈ [1, m]. The query Q is a free self-join conjunctive query if Q is not a self-join conjunctive query.

Example 2.2. Consider the following query Stu_Cour(name, title) :-Student(mat, name, Cour I D), Course(Cour I D, title), title = "Physics". The query Stu_Cour extract all the student names with their preferred courses, only for courses different from "Physics".

NAME TITLE

Bob

Computer Science

Only one valuation v (v(name) = "Bob", v(title) = "Computer Science", v(mat) = "M02", v(Cour I D) = "C01") satisfies the query Stu_Cour, any other valuation fails to satisfy this query.

Denial Constraints

Various classes of database constraints have been studied in the context of relational database [START_REF] Baudinet | Constraint-Generating Dependencies[END_REF][START_REF] Chu | Discovering denial constraints[END_REF][START_REF] Fan | Conditional functional dependencies for capturing data inconsistencies[END_REF]. In this thesis, we consider the class of denial constraints that is the one of the most used classes of constraints [START_REF] Eduardo | Discovery of approximate (and exact) denial constraints[END_REF]. The class of denial constraints covers many other classes of constraints such as functional dependencies, conditional functional dependencies, metric functional dependencies [START_REF] Chu | Discovering denial constraints[END_REF][START_REF] Rekatsinas | Holoclean: Holistic data repairs with probabilistic inference[END_REF]. Informally, a denial constraint expresses a forbidden pattern in database. The class of denial constraints (DC) is defined as the set of constraints of the following form:

← R 1 (u 1 ) ∧ ... ∧ R n (u m ) ∧ φ(u 1 , . . . , u m ) (2.2)
where the R i (u i ) are defined as previously, in section 2.2 and in Equation 2.1, and φ is a conjunction of a built-in atoms. Let C be a denial constraint, we denote by Var(C) all the variables present in C. We denote by C id an unique identifier of C. We denote Υ the set of the identifiers of the denial constraints considered.

A denial constraint C is satisfied by an instance I, denoted I |= C (otherwise, we denote I |= C), if and only if for any valuation v over Vars(Q) then: there exists at

least i ∈ [1, n], v(u i ) / ∈ I(R i ) or φ(v(u 1 ), . . . , v(u m
)) leads to false. So, we say that the database instance is consistent with respect to the constraint C (or shortly, we say it is consistent). Otherwise, we say that the database is inconsistent.

Let DC be a set of denial constraints over a schema S, DC is consistent if there exists an instance I = ∅ on schema S such that I |= DC. Otherwise, we say that DC is inconsistent.

Given a set of denial constraints DC, an instance I is consistent if and only if I is consistent with each constraint C ∈ DC in the set of constraints DC (denoted I |= DC), otherwise we say that the instance I is inconsistent with respect to the set of denial constraints DC (denoted I |= DC).

Example 2.3. Let C 1 ← Student(mat, name, pre f _course), Student(mat, name 1 , pre f _course 1 ), name 1 = name and C 2 ← Course(id, title), Course(id, title 1 ), title 1 = title be two denials constraints. The constraint C 1 is about the uniqueness of the student number according to the name and the second constraint (C 2 ) is about the uniqueness of the course identifier. As one can easily note, the constraint C 1 is satisfied by the instance in example 2.1 since there are no two students with the same number. By opposite, the constraint C 2 is violated by the instance given in Example 2.1 since there are two courses that have the identifier (the identifier C02).

In the remaining of this thesis, denial constraint is abbreviated constraint, unless otherwise specified.

Provenance in relational databases

We recall the provenance semiring framework, introduced in [START_REF] Green | Provenance semirings[END_REF] as a unifying framework able to capture a wide range of provenance models at different levels of granularity [START_REF] Deutch | Circuits for datalog provenance[END_REF][START_REF] Green | Provenance semirings[END_REF][START_REF] Green | Provenance semirings[END_REF]. This framework is based on a general data model that extends the relational model with the so-called K-relations in which tuples are assigned annotations from a given semiring. An extension for Postgresql, called ProvSQL, enabling to evaluate queries and return answers of queries with their provenances is developed in [START_REF] Senellart | Provsql: Provenance and probability management in postgresql[END_REF].

A monomial M over N and a finite set of variables X is defined by

M = a × x m 1 1 × ... × x m n
n with a, m 1 , ..., m n ∈ N and x 1 , ..., x n ∈ X . A null monomial is a monomial where a = 0, otherwise we call the monomial a non null monomial. Let M = a × x m1 1 × ... × x m n n be a monomial. We denote by Var(M) = {x 1 , . . . , x n } the set of variables that appear in the monomial M. The weight of a variable x i ∈ Var(M) w.r.t a monomial M, denoted by W(M, x i ), is equal to m i , the exponent of the variable x i in M. The weight of a non null monomial M, denoted by W(M), is defined as the sum of the weights of its variables, i.e.:

W(M) = ∑ x∈Var(M)
W(M, x). A polynomial P over N and a finite set of variables X is a finite sum of monomials over X . We denote by M(P) the set of monomials of P.

Example 2.4. Consider the following monomials (arbitrarily chosen)

• M 1 = 4X 2 1 X 2 X 3 X 4 , W(M 1 ) = 5, V(M 1 ) = 4 • M 2 = X 1 X 2 X 4 3 , W(M 1 ) = 6, V(M 2 ) = 3 • P = M 1 + M 2 , M(P) = {M 1 , M 2 } K-relations
A commutative semiring is an algebraic structure (K, ⊕, ⊗, 0, 1), where 0 and 1 are two constants in K and K is a set equipped with two binary operations ⊕ (sum) and ⊗ (product) such that (K, ⊕, 0) and (K, ⊗, 1) are commutative monoids 1 with identities 0 and 1 respectively, ⊗ is distributive over ⊕ and 0 ⊗ a = a ⊗ 0 = 0 holds ∀a ∈ K.

Example 2.5. The following structures are commutative semirings structures:

• (N, +, * , 0, 1) the Natural semiring

• (B, ∨, ∧, f alse, true) the Boolean semiring Definition 2.1 (K-relations.). An n-ary K-relation is a function R : D n → K such that its support, defined by supp(R) def = {t : t ∈ D n , R(t) = 0}, is finite.
Hence, a K-relation is an extension of the classical notion of relation to allow tuples to be annotated by the elements of a any semiring but not only by the elements from the Boolean semiring.

Let R be an n-ary K-relation and let t ∈ D n , the value R(t) ∈ K assigned to the tuple t by the K-relation R is called the annotation of t in R. Note that R(t) = 0 means that t is "out of" R [START_REF] Green | Provenance semirings[END_REF]. A K-instance is a mapping from relations symbols in a database schema S to K-relations (i.e, a finite set of K-relations over S). If J is a K-instance over a database schema S and R i ∈ S is a relation symbol in S, we denote by J (R i ) the K-relation corresponding to the value of R i in J (otherwise we use only R i is J is understood).

Conjunctive queries on K-instances

Let Q(u) ← R 1 (u 1 ), ..., R n (u m ), φ(u 1 , .
. . , u m ) be a conjunctive query and let J be a Kinstance over the same schema than Q, with (K, ⊕, ⊗, 0, 1) a semiring. A valuation of Q over a domain D is a function v : Vars(Q) → D, extended to be the identity on constants. The result of executing a query Q over a K-instance J , using the semiring (K, ⊕, ⊗, 0, 1), is the K-relation Q(J ) defined as follows:

Q(J ) def = { (v(u), Π n i=1 R i (v(u i ))) | v is a valuation over Vars(Q)}
The K-relation Q(J ) associates to each tuple t = v(u), which is in the answer of the query Q over the K-instance J , an annotation Π n i=1 R i (v(u i ))) obtained from the product, using the ⊗ operator, of the annotations R i (v(u i )) of the base tuples contributing to t. Since there could exist different ways to compute the same answer t, the complete annotation of t is obtained by summing the alternative ways (i.e., the various valuations) to derive a tuple t using the ⊕ operator. Consequently, the provenance of an answer t of Q over a K-instance J is given by: Q

(J )(t) = ∑ v s.t v(u)=t Π n i=1 R i (v(u i )))
. A polynomial provenance is the provenance/annotation obtained when the semiring structure considered to evaluate the query is (N[X], +, * , 0, 1).

Example 2.6. Consider the database instance in Example 2.1. We associate randomly annotation from the Natural semiring to each tuple as follows, each annotation represents the number of times tuples is present in the instance (in this case, the instance is a bag):

• Student( M01, Alice, C02 ) = 1 • Student( M02, Bob, C01 ) = 2 • Course( C01, "Computer Science" ) = 3 • Course( C02, "Physics" ) = 1 • Course( C02, "Biology" ) = 2
Let's denote the previous N-instance by J . Consider now the query in Example 2.2, then we have the unique answer with its annotation is as follows: Stu_Cour( Bob, "Computer Science" ) = Student( M02, Bob, C01 ) * Course( C01, "Computer Science" ) = 6. The annotation 6 means that this answers can be obtained six times in the N-instance J (represented as bag)

Hyper Graph and Join Tree

In this section, we overview a set of approaches introduced to efficiently evaluate the relational join operation. The join operator is the expensive operation in query processing. We consider only the equi-conjunctive queries. An equi-conjunctive query (shortly, in the following we use/say query) has the following form :

Q(u) ← R 1 (u 1 ), ..., R n (u m )
A hypergraph HG is tuple HG = (V, HE) composed from a finite set of nodes (elements from V) and a set of non empty subsets from V called the set of hyper edges (elements in HE). Definition 2.2 (Query Hyper graph). Let Q(u) ← R 1 (u 1 ), ..., R n (u m ) be an equi-conjunctive query, the query hypergraph of Q, denoted H(Q), is an hypergraph H with the set of nodes Var(Q) and the set of hyperedges the set {Var(u i ) : i ∈ {1, . . . , m}}, defined as follows :

H(Q) = (Var(Q), {Var(u i ) : i ∈ {1, . . . , m}})
An hypergraph HG is acyclic if and only if it can be turned into a tree T of the following features: the nodes of T are the set of hyperedges and each two n 1 and n 2 in T, with their hyperedges having at least one node from HG(V) in common, so n 1 and n 2 are connected in a sub graph (sub tree) of T [START_REF] Bagan | On Acyclic Conjunctive Queries and Constant Delay Enumeration[END_REF]. We say that also, an hypergraph is acyclic if the GYO algorithm (from Graham-Yu-Ozsoyoglu), that takes as input an hypergraph and returns an other hypergraph, outputs an empty hypergraph [START_REF] Yu | An algorithm for tree-query membership of a distributed query[END_REF]. The GYO algorithm is as follows:

• Choose on arbitrary node N of the hypergraph H(Q) such that one can divide its set of variables into two parts -The first one, denoted Isolated(N), is the set of variables that are present in only N.

-The other one is the set of variables present in N and only another node.

• Remove N and the set of variables Isolated(N) from the hypergraph H(Q).

A query is acyclic if its underling hypergraph is acyclic.

Example 2.7. Consider a database I from this arbitrary schema {R The Yannakakis's algorithm [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF] designed for acyclic query Q evaluation over an instance I runs in a complexity O(|I | + |Q(I)|), it is an optimal. The main lines of this algorithm are:

1 (A 1 , A 2 , A 3 ), R 2 (A 4 , A 5 , A 6 ), R 3 (A 7 , A 8 , A 9 )}. Let Q(x, u, x 2 ) :-R 1 (x, y, z), R 2 (u, y, w), R 3 (x 2 , v,
• Associate to each node of the tree a map. Given a node n, the set of keys of the map of n is from the valuation values of common variables between n and its parent and the its set values is from the tuples of the relation represented by this node;

• The root r node has one key that is the empty tuple since its has no parent, and the set of values corresponding to this key is the set of tuples from relation that r represents;

• Remove the dangling tuples in each node in each parent node remove tuples that do not match any tuple in a least one of its children nodes, using its associated map (top down traversal to remove other dangling tuple);

in each node, remove all the tuples that do not match any tuple in its parent node, using the its associated map (bottom up traversal to remove some dangling tuple);

• Answers are computed by doing just a Cartesian product using the result tree So, any acyclic query can be performed in linear time in data complexity. The following example illustrates the Yanakakis's algorithm.

Example 2.8. Consider the query and the schema of the example 2.7. Consider the following instance from this schema. 11 3 The matching between the variables and the attributes is as follows:

R 1 A 1 A 2 A 3 a 1 1 3 a 2 2 4 R 2 A 4 A 5 A 6 b 1 1 1 b 2 3 0 b 3 4 4 R 3 A 7 A 8 A 9 c 1 0 1 c 2 10 1 c 3
x → {A 1 } y → {A 2 , A 5 } z → {A 3 } u → {A 4 } w → {A 6 , A 9 } x 2 → {A 7 } v → {A 8 }.
On this instance we run the Yannakakis's algorithm as follows:

x, y, z

Key Tuples 1 [ a 1 , 1, 3 ] 2 a 2 , 2, 4 ] u, y, w Key Tuples [ b 1 , 1, 1 , b 2 , 3, 0 , b 3 , 4, 4 ] x 2 , v, w Key Tuples 1 [ c 1 , 0, 1 , c 2 , 10, 1 ] 3 [ c 3 , 11, 3 ]
(a.) The tree of Q with data structures

x, y, z

Key Tuples 1 [ a 1 , 1, 3 ] u, y, w Key Tuples [ b 1 , 1, 1 ] x 2 , v, w Key Tuples 1 [ c 1 , 0, 1 , c 2 , 10, 1 ] (b.
) The tree of Q after dangling tuples eliminations

The set of answers is the set b

1 , 1, 1 × [ a 1 , 1, 3 ] × [ c 1 , 0, 1 , c 2 , 10, 1
] after projection on variable x, u, x 2 . So, the set of answers is:

• π x,u,x 2 ( b 1 , 1, 1 × a 1 , 1, 3 × c 1 , 0, 1 ) = a 1 , b 1 , c 1 • π x,u,x 2 ( b 1 , 1, 1 × a 1 , 1, 3 × c 2 , 10, 1 ) = a 1 , b 1 , c 2
When the query is not acyclic then, it can be decomposed into a tree in a way that the cycle is removed. This approach merges some nodes of the hypergraph to obtain an acyclic hypergraph and then obtain the tree [START_REF] Gottlob | A Backtracking-Based Algorithm for Hypertree Decomposition[END_REF]. The merged nodes implies intermediary results, i.e, one needs to first compute the result of these merged nodes before computing the final result. Hypergraph decomposition is an active research area. One of the main challenge is to find the hypergraph decomposition that minimizes the intermediary result [START_REF] Gottlob | A Backtracking-Based Algorithm for Hypertree Decomposition[END_REF].

Example 2.9. Consider now the query Q 1 (x, u) : -R 1 (x, y, z), R 2 (u, y, w), R 3 (x, v, w) similar as the query Q in Example 2.7. As one can easily note, the query Q 1 is a cyclic query since the GYO algorithm does not return an empty result after its running with H(Q 1 ) = (V , HE ) as input hypergraph: any hyperedge among HE = {{x, y, z}, {u, y, w}, {x, v, w}} has common variables from at least two other hyperedges. The H(Q 1 ) is as follows:

x z y u w v H(Q 1 )
It is possible to merge some hyperedges to have a tree, then an hypergraph that is acyclic. For example, merge the node {x, y, z} and {u, y, w} to obtain the following {{{x, y, z, u, w}, {x, v, w}}} hypereadges that forms an acyclic hypergraph. But one has to materialize first the result of join between {x, y, z} and {u, y, w}.

The fractional vertex cover of an hypergraph H(Q) = (V, HE), for a query Q, is a solution of the following system of inequalities [START_REF] Gottlob | A Backtracking-Based Algorithm for Hypertree Decomposition[END_REF]:

∑ e∈HE:v∈e X e ≥ 1 ∀v ∈ V with X e ≥ 0
The variables X e are real number that represent each hyperedge (an hyperedge corresponds e ∈ HE to a relational atom in Q). The minimum vertex cover of H(Q) corresponds to the minimum among vertex covers (with summation of their components) of H (Q). So, the minimum vertex cover is obtained by resolving the above system of inequalities with the following objective function to minimize:

∑ e∈HE X e
Let N R = |R| be the number of tuples in the relation R. The AGM bound [START_REF] Atserias | Size bounds and query plans for relational joins[END_REF] of the query answers size of a query Q evaluated over an instance

I is Q(I ) ≤ ∏ i∈{1,...,m} N X e i R i ,
in the case where Var(u) = i∈{1,...,m}

Var(u i ), with e i the hyperedge corresponding, in the hypergraph H(Q), to the relational atom R i . The sum ∑ e∈HE X e is called the fractional width. This maximum fractional width bound allows to choose the best merging of the nodes of a cyclic hypergraph to have a small size of intermediary result. The largest fractional width among all the merged nodes during the decomposition of the hypergraph to a tree is called the tree fractional width of the resulting tree. The tree fractional width enables to give the largest intermediary result size. These efficient techniques to compute the join result are used in Chapter 5 to do enumeration of query answers in order of their score (inconsistency degrees according to a measure of inconsistency degrees). The next chapter presents the state of the art.

Chapter 3

STATE OF THE ART

We overview related works in the following areas: inconsistency handling in knowledge bases and relational databases (section 3.1) and top-k queries processing algorithms (3.2).

Data Inconsistency

We discuss related works in the areas of knowledge bases and relational databases.

Inconsistency in knowledge bases

The problem of inconsistency in knowledge bases is studied since more than forty years ago [START_REF] Newton | On the theory of inconsistent formal systems[END_REF]. In the literature, the inconsistency problem in knowledge bases is handled in two manners: defining new class of logic with new rules of inference that take account inconsistency, called paraconsistent logic system [START_REF] Carnielli | A Taxonomy of C-systems[END_REF][START_REF] Grant | Classifications for inconsistent theories[END_REF][START_REF] Grant | Applications Of Paraconsistency In Data And Knowledge Bases[END_REF][START_REF] Hunter | Managing inconsistent specifications: reasoning, analysis, and action[END_REF][START_REF] Hunter | Paraconsistent Logics[END_REF][START_REF] Hieu | Integration of Knowledge in Disjunctive Structure on Semantic Level[END_REF][START_REF] Ulbricht | Understanding Inconsistency -A Contribution to the Field of Nonmonotonic Reasoning[END_REF] or quantifying the level of inconsistency in the knowledge bases [7, 40, 50, 68, 90, 94, 109, 112-114, 116, 122, 129, 137, 142-144, 153, 159].

The paraconsistent logic systems are defined to tackle the problem of triviality arisen in classical logic caused by the occurrence of inconsistency [START_REF] Arieli | The value of the four values[END_REF][START_REF] Nuel | A Useful Four-Valued Logic[END_REF][START_REF] Benferhat | Some Syntactic Approaches to the Handling of Inconsistent Knowledge Bases: A Comparative Study Part 1: The Flat Case[END_REF][START_REF] Bertossi | Inconsistency Tolerance [result from a Dagstuhl seminar[END_REF][START_REF] Besnard | Quasi-classical logic: Non-trivializable classical reasoning from inconsistent information[END_REF][START_REF] Xiaowang | Quasi-Classical Description Logic[END_REF].

To reason in a context of inconsistency in a knowledge bases K, Rescher et al, in [2], propose two notions of logical consequence: one that is strong called W-consequence, in this case a proposition is true if it is a consequence of at least one maximal consistent set (under set-inclusion) of K; the second one called I-consequence, considers all the maximal consistent sets from K to valid a proposition. Benferhat et al [START_REF] Benferhat | Some Syntactic Approaches to the Handling of Inconsistent Knowledge Bases: A Comparative Study Part 1: The Flat Case[END_REF] tackle the problem of inconsistency by using argue consequence notion, in other word, any formula valid φ using an inconsistent knowledge bases K is a consequence of a minimal consistent subset (under set-inclusion) S (i.e, S ⊆ K and S |= φ and ∃S ⊆ S such that S consistent and S |= φ ) of K; and the contradictory formula of φ (¬φ) is not a consequence of any other minimal consistent subset S of K (S |= ¬φ).

Besnard et al [START_REF] Besnard | Quasi-classical logic: Non-trivializable classical reasoning from inconsistent information[END_REF] introduce a new class of logical system called quasi-classical logic, designed from classical first order logical by making strict inference rules enabling to avoid triviality during deduction (i.e, to avoid to deduce any formula). One of the paraconsistent logic introduced is the four values logic [START_REF] Arieli | The value of the four values[END_REF][START_REF] Nuel | A Useful Four-Valued Logic[END_REF]. The four values logic introduces two new truth values. One of the two values concerns formulas that are neither true nor false. The second one is about propositions that are true and false at the same time. An interesting discussion about these paraconsistent systems is done in [START_REF] Carnielli | A Taxonomy of C-systems[END_REF]. These approaches assume a specific logic system to query knowledge bases and limit query answers to a specific subset of answers, instead of our approaches that keep standard query language and quantify inconsistency of query answers.

Concerning quantification of inconsistency in the knowledge base, a set of measures of inconsistency levels, that measure inconsistency in the entire knowledge bases, are introduced [START_REF] Grant | Analysing inconsistent first-order knowledgebases[END_REF][START_REF] Hunter | Approaches to Measuring Inconsistent Information[END_REF][START_REF] Jabbour | On inconsistency measuring and resolving[END_REF][START_REF] Jabbour | Measuring Inconsistency Through Minimal Proofs[END_REF][START_REF] Jabbour | Quantifying Conflicts in Propositional Logic Through Prime Implicates[END_REF][START_REF] Mu | A general framework for measuring inconsistency through minimal inconsistent sets[END_REF][START_REF] Muino | Measuring and repairing inconsistency in knowledge bases with graded truth[END_REF][START_REF] Picado | Measuring and repairing inconsistency in probabilistic knowledge bases[END_REF][START_REF] Thimm | Measuring Inconsistency in Probabilistic Knowledge Bases[END_REF][START_REF] Thimm | Towards Large-Scale Inconsistency Measurement[END_REF][START_REF] Thimm | Measuring Inconsistency with Many-Valued Logics[END_REF]. The inconsistency level of the entire knowledge base enables to compare two knowledge bases [START_REF] Hunter | Approaches to Measuring Inconsistent Information[END_REF]. This level of inconsistency can be also used to help the engine of integrity constraint checking [START_REF] Decker | Quantifying the Quality of Stored Data by Measuring their Integrity[END_REF][START_REF] Decker | Causes of the Violation of Integrity Constraints for Supporting the Quality of Databases[END_REF][START_REF] Decker | Inconsistency-Tolerant Integrity Checking Based on Inconsistency Metrics[END_REF][START_REF] Decker | A Relaxed Approach to Integrity and Inconsistency in Databases[END_REF][START_REF] Decker | Classifying integrity checking methods with regard to inconsistency tolerance[END_REF][START_REF] Decker | Modeling, Measuring and Monitoring the Quality of Information[END_REF][START_REF] Decker | Data Consistency: Toward a Terminological Clarification[END_REF]. Jabbour et al introduce in [START_REF] Jabbour | Quantifying Conflicts in Propositional Logic Through Prime Implicates[END_REF] two measures, measuring inconsistency in whole of the database; one measure counts the number of minimal inconsistent subsets of the knowledge bases and the second counts the number of conflicts(a conflict arises when an atom and its negation are both present in the knowledge base) that one can find in the knowledge bases. Thimm et al propose in [START_REF] Thimm | Measuring Inconsistency in Probabilistic Knowledge Bases[END_REF] a set of measures for probabilistic knowledge bases.

An overview of measures of inconsistency level of knowledge bases in literature is presented in [START_REF] Hunter | Towards a Unified Framework for Syntactic Inconsistency Measures[END_REF]. A study about the quality of the measures of inconsistency level defined in literature is investigated in [START_REF] Grant | General information spaces: measuring inconsistency, rationality postulates, and complexity[END_REF][START_REF] Thimm | On the Compliance of Rationality Postulates for Inconsistency Measures: A More or Less Complete Picture[END_REF]. All these works quantify inconsistency in the entire knowledge bases opposed to our works that quantify inconsistent at the level of tuple. We quantify inconsistency for each tuple in database and for each query answer.

Inconsistency in relational database

Concerning the inconsistency problem in relational databases, it has been mainly tackled by the database repair approaches; also, the consistent query answering approach (CQA) based on these database repair approaches is developed to answer queries on inconsistent databases [6, 8, 19-21, 32, 58, 59, 64, 72, 98, 103, 104, 106, 107, 111, 119, 120, 120, 146, 146, 150, 155]. The repairing approach consists to restore the database consistency by making deletion of tuples from database, or addition of new tuples in database, or modification of values of some attributes, etc [START_REF] Bertossi | Consistent query answering in databases[END_REF][START_REF] Bertossi | Database repairs and consistent query answering: Origins and further developments[END_REF][START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. These actions to restore the database consistency are called semantic of repairs [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. A database in which the consistency is restored is called repair. Each semantic of repair can generate many repairs (possible infinite set of repairs) [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. Given a query Q and a semantic of repair Sem, the consistent query answers is the intersection of answers of Q computed over all the repairs obtained with the semantic Sem [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF].

The repairing and CQA notion have been first introduced by Arena et al [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF], and in this seminal paper they propose repair by deletion. The main semantics of repairs are: repair by deletion [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF][START_REF] Chomicki | Minimal-change integrity maintenance using tuple deletions[END_REF][START_REF] Livshits | Computing optimal repairs for functional dependencies[END_REF][START_REF] Wijsen | On condensing database repairs obtained by tuple deletions[END_REF][START_REF] Wijsen | Project-join-repair: An approach to consistent query answering under functional dependencies[END_REF] consisting to restore consisting by deleting some tuples, repair by insertion [START_REF] Molinaro | Polynomial time queries over inconsistent databases with functional dependencies and foreign keys[END_REF] that restores consistency by inserting (possibly fictive) tuples and repair by update [START_REF] Bertossi | Fixing inconsistent databases by updating numerical attributes[END_REF][START_REF] Greco | Probabilistic query answering over inconsistent databases[END_REF][START_REF] Liu | Consistent query answering based on repairing inconsistent attributes with nulls[END_REF][START_REF] Livshits | Computing optimal repairs for functional dependencies[END_REF][START_REF] Lopatenko | Efficient approximation algorithms for repairing inconsistent databases[END_REF][START_REF] Molinaro | Polynomial time queries over inconsistent databases with functional dependencies and foreign keys[END_REF] that modifies values of attributes to restore consistency.

The theoretical complexity of CQA have been largely investigated in literature [31, 33-35, 52, 60, 75, 92, 92, 93, 95-97, 110, 118, 120, 147-149, 151], these research works have shown that computing CQA is a Co-NP complete problem. Other works are focused on specific classes of queries and constraints. So, they have proposed for these classes a rewriting approach that enables to compute CQA in polynomial time in data complexity [START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF][START_REF] Fuxman | First-order query rewriting for inconsistent databases[END_REF][START_REF] Gardezi | Query rewriting using datalog for duplicate resolution[END_REF]. Also, in the same direction to find efficient algorithm to compute CQA, some quantitative approaches that quantify inconsistency are defined [START_REF] Koutris | Consistent query answering for self-join-free conjunctive queries under primary key constraints[END_REF][START_REF] Livshits | Counting and enumerating (preferred) database repairs[END_REF][START_REF] Livshits | Counting subset repairs with functional dependencies[END_REF][START_REF] Maslowski | On counting database repairs[END_REF], but all these works depend to a repairing approach. For more details about repairing and CQA, the reader can be referred to the Bertossi's book [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. Several repairs approaches have been defined in literature [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. Depending to the repair approach, the consistent query answers can be different from a repair approach to an other and CQA keeps only a subset of answers of the query [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF]. Another problem of the repairing and CQA approach is the fact that the number of repairs generated is exponential (can be infinite) in the size of the database; and in the best case, the complexity of CQA is CO-NP-complete [START_REF] Wijsen | Condensed representation of database repairs for consistent query answering[END_REF]. Opposed to our work, we propose a set of measures that quantify inconsistency and that do not assume any repairing approach. Also, we allow a ranking of query answers according to the their inconsistency degrees.

Top-k algorithms

In this section, we discuss the works related to top-k queries. Two classes of algorithms have been considered: Disk-based algorithms and Memory-based algorithms.

Disk-based algorithms

In this class of top-k algorithms, the top-k answers are computed while optimizing the input/output operations (i.e, read and write operations made on disk). A seminal work in this area is developed by Fagin [START_REF] Fagin | Combining Fuzzy Information from Multiple Systems[END_REF] through the famous FA(Fagin algorithm) instance optimal algorithm [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF]. Given m lists of items and each item has a score (the lists contains the same items with not necessary the same scores), the FA algorithm sorts first each list and in each one it takes the k first items with the high scores; in second step, it aggregates the scores of items (by an aggregate monotone scoring function) from different lists and when an item is not loaded in one or more of the lists then it is accessed by a random access. The FA is extended to TA algorithm by integration of notion of scoring bound [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF]. The TA algorithm works exactly as the FA algorithm and assumes the same conditions as FA but the items in lists are sequentially accessed one after one and a threshold score is computed after each read of item; this threshold score enables to know what item, among seen items, belongs to the top-k. The algorithms FA and TA assumes a random access and a sequential access; NRA [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] is developed to work only with sequential access. Similar works have been investigated in [START_REF] Chen-Chuan | Minimal probing: Supporting expensive predicates for top-k queries[END_REF][START_REF] Güntzer | Optimizing multi-feature queries for image databases[END_REF][START_REF] Marian | Evaluating top-k queries over web-accessible databases[END_REF]. The above top-k algorithms assume a simple input selection query with only natural join on key attributes. Then, Natsev et al [START_REF] Natsev | Supporting incremental join queries on ranked inputs[END_REF] introduce the J * algorithm that works with the general join, J * assumes only the sequential access. Other top-k algorithms for general join are proposed in [START_REF] Peter | Ripple joins for online aggregation[END_REF][START_REF] Ihab | Joining ranked inputs in practice[END_REF][START_REF] Ihab | Supporting top-k join queries in relational databases[END_REF][START_REF] Li | Ranksql: Query algebra and optimization for relational top-k queries[END_REF][START_REF] Schnaitter | Evaluating rank joins with optimal cost[END_REF][START_REF] Schnaitter | Optimal algorithms for evaluating rank joins in database systems[END_REF], all these works assume a sequential access (with sorted relations). In [START_REF] Li | Supporting ad-hoc ranking aggregates[END_REF] the authors propose a top-k algorithm for queries with aggregation clause and/or aggregation function. A survey of the top-k algorithms is presented in [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF].

These research works have developed top-k algorithms to work only for monotonic functions and the input data are, at least, sequentially accessed in sorting order of scores. In this thesis, we design top-k algorithms for non-monotonic scoring functions.

Memory-based algorithms

The class of Memory-based algorithms does not take into account minimization of input/output operations, it loads all the database in main memory and computes top-k answers while minimizing operations in main memory.

The referential work in this area is investigated by Tziavel et al in [START_REF] Tziavelis | Optimal join algorithms meet top-k[END_REF]. The authors combine the new techniques developed to efficiently compute the join [START_REF] Goodman | GYO reductions, canonical connections, tree and cyclic schemas, and tree projections[END_REF][START_REF] Gottlob | A Backtracking-Based Algorithm for Hypertree Decomposition[END_REF][START_REF] Yannakakis | Algorithms for Acyclic Database Schemes[END_REF] and ranking enumeration while assuming to have monotonic functions. These efficient techniques generate first the join tree of the query, and based to the properties of this join tree [START_REF] Gottlob | A Backtracking-Based Algorithm for Hypertree Decomposition[END_REF], an efficient technique can be used to compute join results. So, in [START_REF] Tziavelis | Optimal join algorithms meet top-k[END_REF], the authors fusion efficient join and ranking to enumerate the k answers of queries in order of their scores (where the aggregate scoring function is the sum). First they perform for path queries (where the join tree of the query can be converted into a path), so they convert the problem of finding the k answers enumeration into a problem of finding the k shortest paths. They generalize beyond path queries. For an acyclic query, one of their algorithms computes the top-k in O(n + k * log(k)) in data complexity with n the size of data. The authors of [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF] propose a recursive version of enumeration of answers of queries in order of their scores, their approach works also with monotonic functions, for an acyclic query it runs in O(n + k * log(n)). Other top-k algorithms, in this class, are also proposed in [START_REF] Bruno | Top-<i>k</i> selection queries over relational databases: Mapping strategies and performance evaluation[END_REF][START_REF] Chang | The onion technique: Indexing for linear optimization queries[END_REF][START_REF] Das | Answering top-k queries using views[END_REF][START_REF] Hristidis | Prefer: A system for the efficient execution of multi-parametric ranked queries[END_REF][START_REF] Zhang | Boolean + ranking: Querying a database by k-constrained optimization[END_REF].

Aside from algorithm developed in [START_REF] Zhang | Boolean + ranking: Querying a database by k-constrained optimization[END_REF], that is designed for generic function (not necessary a monotonic function), all these algorithms work with monotonic aggregate scoring function. In addition, these algorithms do not work for queries with aggregation clause. In this thesis, we develop top-k algorithm for some aggregate queries (with MIN and MAX functions) and for non monotonic functions.

Conclusion

We presented in this chapter, the state of art. We divided this start of art into four parts. The first part described works concerning the handling of inconsistency in knowledge bases; the second one was about inconsistency problem fixing in relational database, mainly it was consecrated to the database repairing and consistent query answering notions; the third part was dedicated to the top-k algorithms in Disk-based algorithms class(algorithms that minimize the input/output operations on disk); and the last part have presented the top-k algorithms in Memory-based algorithms (i.e, those algorithms that load all data in main memory and minimize the number of operations in main memory).

In the next chapter, we present one of our main works that is about the introduction of a set of measures of inconsistency degrees.

Chapter 4

QUANTIFYING INCONSISTENCY

In this chapter, we propose a set of measures to quantify inconsistency degrees in relational databases. We focus on the problem of quantifying the inconsistency degrees of query answers.

A set of constraints SC is consistent if only if there exists a non empty database D such that D |= SC. We assume that the considered set of constraints, in this chapter, is consistent. This assumption will be lifted in chapter 6. The proposed measures enable to quantify the inconsistency degrees of a given tuple that can be a base tuple or a query answer. We introduce two classes of measures: tuple-based measures and constraintbased measures that we describe below in detail.

Let I be a database instance over a schema S and let DC be a set of denial constraints over S. We proceed in three steps in order to define the set of measures of inconsistency degrees.

• Identifying inconsistent tuples: We first start by identifying the inconsistent tuples of an instance I over S with respect to a set of denials constraints DC. To achieve this task, we turn each denial constraint C ∈ DC into a Boolean conjunctive query denoted Q C . We use the why-provenance (also known as lineage) of each Q C to compute the set of inconsistent tuples in I with respect to DC. The set of inconsistent tuples of an instance I with respect to a set of denial constraints DC is denoted by IncT(I, DC).

• Annotating the initial database instance: Using the why-provenance of each Boolean conjunctive query obtained from each denial constraint, we convert the instance I into a K-instance by annotating each consistent tuple in I with the value 1 and each inconsistent tuple t ∈ IncT(I, DC) with id(t)

× C 1 id × • • • × C p id , where C 1 , . . . , C p ∈ DC and t appears in why-provenance of C i with i ∈ [1, n].
• Defining inconsistency degrees of query answers: then, given an UCQ Q over the instance I, we use polynomial provenance semi-ring to annotate the query answers. The latter provenance is the most informative form of provenance annotation [START_REF] Green | Containment of conjunctive queries on annotated relations[END_REF] and hence is exploited in our setting in order to define different inconsistency degrees for query answers.

In the next section, we illustrate our approach to quantify inconsistency degrees. # Constr. Violations d2, d2 t 2 , t 3 , t 7

(V) Constraint Id Denial Constraint C 1 ← D(x, y, z) ∧ S(x, y, u) ∧ z > u C 2 ← D(x, y, z) ∧ V(x, y, u) ∧ z > u C 3 ← S(x, y, z) ∧ V(x, v, z) Set of denial constraints(DCs) Q ex (y, u) ← D(x, y, z) ∧ S(x, y, z 1 ) ∧ V(x, u, v) Query (Q ex )
C 1 × C 2 × C 3 C 2 1 × C 2 2 × C 3 a 1 d2, d2 t 2 , t 4 , t 7 C 1 × C 2 × C 3 C 2 1 × C 2 2 × C 2 3 a 2 d2, d2 {t 2 , t 6 , t 7 } C 1 × C 2 × C 3 C 1 × C 2 2 × C 3 a 3 d4, d4 {t 1 , t 5 , t 8 } 1 1 a 4

Illustrative Example

Consider a relational database instance I in Figure 4.1 consisting three relations D, V and S with a corresponding number of denial constraints IC and a query Q ex . In each relation in I, the first column is the patient identifier PID, the second column is the desease reference RefID and the third column is the Date of a given event. Notice that the schema of the three tables is the same solely for illustration purposes and to maximize the number of joins across the tables. In fact, our methods are generalizing to relations with an arbitrary schema. The denial constraint (C 1 ) imposes to have any diagnosis for a patient's disease before surgery for the same disease concerning the same patient. The constraint (C 2 ) and (C 3 ) establish that a patient cannot be diagnosed a given disease for which he/she has been administered a vaccine on a previous date 1 . Finally, a conjunctive query Q ex extracts pairs of diseases for which the same patient underwent surgey and was administered a vaccine. The tuples in the relations highlighted in red are those that violate one or more constraints (C 1 ), (C 2 ) or (C 3 ).

Before evaluating the query Q ex , we annotate each tuple in the databases instance I with an unique identifier. When applying the why-provenance to the tuples augmented with their identifiers, and for each answer tuple of query Q ex , the corresponding possible derivations in terms of tuple identifiers are shown (see Table 4.1). We can notice that each answer tuple contains bold tuple tuple identifiers. By counting the number of bold identifiers, we can compute the inconsistency degree of the tuple. For instance, the answer tuple {R 1 , R 2 } has inconsistency degree equal to 3, whereas the answer tuple {R 7 , R 4 } will have inconsistency degree equal to 3 or 2, depending on whether we favor a greater or smaller number of derivating inconsistent tuples, and so on. We can also obtain duplicates in the provenance column that might be taken into account in the counting or not. These considerations led us to precisely define twelve measures of inconsistency degrees under set-and bag-semantics and to provide prac-tical methods to compute them starting from plain database instances. We tackle these questions in the remainder of the thesis.

In the next section, we shall detail the proposed three-step approach.

Identifying inconsistent tuples

Let I be an instance over a database schema S and let DC be a set of denial contraints over S. We first convert the set denial constraints DC into a set of boolean conjunctive queries denoted Q DC as follows. For each constraint C ∈ DC of the form:

← R 1 (u 1 ) ∧ ... ∧ R n (u n ) ∧ φ(u 1 , . . . , u n )
we generate a boolean conjunctive query Q C :

Q C () ← R 1 (u 1 ) ∧ ... ∧ R n (u n ) ∧ φ(u 1 , . . . , u n ) Example 4.1.
The set DC of denial constraints depicted in Figure 4.1 leads to the following set of boolean conjunctive queries:

Q C 1 () ← D(x, y, z) ∧ S(x, y, u) ∧ z > u Q C 2 () ← D(x, R2 , y) ∧ V(x, R2 , z) ∧ y > z Q C 3 () ← D(x, R4 , y) ∧ V(x, R4 , z) ∧ y > z
It is easy to verify that an instance I violates the set of denial constraints DC iff at least on boolean conjunctive query from Q DC evaluates to true over the instance I (i.e., ∃C ∈ DC, Q C (I) = {<>}, where the empty tuple <> denotes the true value of a boolean query). The lineage of the empty tuple <> enables the identification of the set of all contributing source tuples in violation, and hence all the tuples that "contribute" to make the instance I inconsistent w.r.t. DC. We shall use the provenance semirings [START_REF] Green | Containment of conjunctive queries on annotated relations[END_REF] to compute it.

Let P (Γ) be the powerset of the set of tuple identifiers Γ. Consider the following provenance semiring: (P (Γ) ∪ {⊥}, +, ., ⊥, ∅), where ∀S, T ∈ P (Γ) ∪ {⊥}, we have ⊥ + S = S + ⊥ = S, ⊥.S = S.⊥ = ⊥ and S + T = S.T = S ∪ T if S =⊥ and T = ⊥. This semiring consists of the powerset of Γ augmented with the distinguished element ⊥ and equipped with the set union operation which is used both as addition and multiplication. The distinguished element ⊥ is the neutral element of the addition and the annihilating element of the multiplication.

We convert the instance I over the schema S into a K-instance, denoted by I LP , with K = P (Γ) ∪ {⊥}. The K-instance I LP is defined below. Definition 4.1 (Lineage provenance database). Let I be an instance over a database schema S and let DC be a set of denial contraints over S. Let K = P (Γ) ∪ {⊥}. The K-instance I LP , called lineage provenance database from I, is constructed as follows: Using the provenance semirings, we define below the inconsistent tuples of a given instance w.r.t. a set of denial constraints.

• ∀R i ∈ S a corresponding K-relation is created in I LP , • A K-relation I LP (R i ) ∈ I LP is populated as follows: I LP (R i )(t) = {id(t)} i f t ∈ I(R i ) I LP (R i )(t) = ⊥ otherwise Example 4.2.

Definition 4.2 (Inconsistent tuples)

. Given an instance I and a set of denial constraints DC, the set of inconsistent tuple identifiers, denoted by IncT(I, DC), is defined as follows

IncT(I, DC) def = Q∈Q DC Q((I ) LP )( ) Consequently, a tuple t ∈ I is inconsistent w.r.t. DC if id(t) ∈ IncT(I, DC).
In the following, we define the notion of violated constraints by a tuple from input database.

Definition 4.3 (Violated constraints)

. Given an instance I and a set of denial constraints DC, the set VC(I, DC, t) of constraints of DC violated by a tuple t ∈ I is defined as follows:

VC(I, DC, t) = {C ∈ Υ | t ∈ Q C (I LP )(<>)} Example 4.3.
Consider the set of boolean conjunctive queries Q DC of Example 4.1 which is obtained from the set of denial constraints of the hdb database. The execution of each query Q C from Q DC over the lineage provenance database hdb LP of Figure 4.3 leads to the answer true (i.e., the tuple <>), if it is violated, annotated with the set of tuples from database hdb that involve in violation of C, i.e.,:

• Q C 1 (hdb LP )(<>) = {t 2 , t 3 , t 4 } • Q C 2 (hdb LP )(<>) = {t 2 , t 7 } • Q C 3 (hdb LP )(<>) = {t 4 , t 7 }
So, the set of inconsistent tuples is the following: incT(hdb, DC) = {t 1 , t 17 , t 2 , t 18 , t 3 , t 19 , t 7 , t 10 , t 6 , t 11 , t 5 , t 13 }

The violated constraints by tuple t 2 are VC(I, DC, t 1 ) = {C 1 , C 2 }, that are violated by t 7 are VC(I, DC, t 7 ) = {C 2 , C 3 }.

In the next section, we show how the final instance is annotated.

Annotation of Database

In the next section, we will show how to use the provenance polynomials to define the inconsistency degrees of query answers. To achieve this task, we first need to convert the instance I into a N[Υ ∪ Γ]-instance, denoted I Υ∪Γ . As shown in the following definition, an instance I Υ∪Γ is derived from I by tagging each tuple t ∈ I with a monomial with variables in Υ ∪ Γ. These monomials, during query evaluation, are propagated to query answers thus enabling to identify the inconsistent tuples used to computed a given answer as well as the constraints violated by this last one. Definition 4.4 (I Υ∪Γ instance). Let I be an instance over a database schema S and let DC be a set of denial constraints over S.

PID RefD

Let K = N[Υ ∪ Γ]. The K-instance I Υ∪Γ is constructed as follows: ∀R i ∈ S a corresponding K-relation is created in I Υ∪Γ . A K-relation I Υ∪Γ (R i ) ∈
I Υ∪Γ is populated as follows:

I Υ∪Γ (R i )(t) = 0 i f t / ∈ I Υ (R i ) t d id × ∏ C id ∈Υ C l id otherwise with l = 1 if C id ∈ VC(I, DC, t
) or l = 0 otherwise; and t id is identifier of t considered as a variable and d = 1 if t ∈ IncT(I, DC) or d = 0 otherwise.

Hence, an annotation I Υ∪Γ (R i )(t) of a tuple t is equal to 1 if the base tuple t is consistent (i.e., VC(I, DC, t) = ∅), otherwise it is equal to a monomial expression that uses as variables the identifiers of the constraints violated by t (i.e., the elements of VC(I, DC, t)).

Example 4.4. Continuing with our example, the hdb Υ instance obtained from the hospital database hdb is depicted in Figure 4.3. We illustrate below the computation of the annotations of the tuples t 1 (a consistent tuple) and t 2 (an inconsistent tuple). From the previous example, we have VC(I, DC, t 1 ) = ∅ and hence the annotation of t 1 is computed as follows:

hdb Υ (R i )(t 1 ) = 1 because t 1 /
∈ IncT(I, DC). For the tuple t 2 , we have VC(I, DC, t 2 ) = {C 1 , C 2 } and hence: hdb

Υ (R i )(t 2 ) = t 2 × C 1 1 × C 1 2 × C 0 3 = t 2 C 1 C 2 .
Constraint-based formula, denoted Cs(P) :

N[Υ ∪ Γ] → N[Υ]
is a function that takes as input a polynomial of variables from Υ ∪ Γ and returns a polynomial of variables from Υ where each variable from Γ takes value 1.

Tuple-based formula, denoted T p(P) :

N[Υ ∪ Γ] → N[Γ]
is a function that takes as input a polynomial of variables from Υ ∪ Γ and returns a polynomial of variables from Γ where each variable from Υ takes value 1.

Example 4.5.

Consider Γ = {t 1 , t 2 , t 3 , t 4 , t 5 } and Υ = {c 1 , c 2 , c 3 , c 4 }. Let P = t 2 1 c 1 t 3 + c 3 c 4 c 2 + t 1 t 2 be a polynomial of variables from Γ ∪ Υ, then • Cs(P) = c 1 + c 3 c 4 c 2 + 1 • T p(P) = t 2 1 t 3 + 1 + t 1 t 2
In the sequel, we assume that the relations of an annotated instance I Υ∪Γ are augmented with an attribute prov that stores the annotations of the base tuples. As an example, Figure 4.3 shows the annotated relations of the instance hdb Υ∪Γ together with their respective prov columns. Now, it is ready to define the measures of inconsistency degrees. In the next section, we define the twelve measures of inconsistency degrees (shown in figure 4.4). Single Occ. Multi Occ.

TBS TBM

Single Occ. Multi Occ.

Min Max Min Max

TSS min TSSmax TSM min TSMmax

Set Seman. Bag Seman.

Single Occ. Multi Occ.

CBS CBM

Single Occ. Multi Occ.

MIN MAX

CSM min CSMmax

MIN MAX

CSS min CSSmax

Figure 4.4: The various quantification of inconsistency that can be obtained along with their criteria.

Query answers inconsistency

Given a query Q, we evaluate Q over the N[Υ ∪ Γ]-instance I Υ∪Γ and use the provenance polynomials semiring in order to annotate each answer t of Q. The computed annotations, expressed as polynomials with variables from the set Υ ∪ Γ consisting of the identifiers of tuples and identifiers of constraints, are fairly informative as they allow to fully record how the constraints are violated by base tuples that contribute to each answer and how inconsistent tuples are used to compute these answers. Such annotations are hence exploited to compute the various inconsistency measures needed for query answers.

Example 4.6. Continuing with the example, evaluating the query Q ex over hdb Υ∪Γ and computing its polynomial provenance leads to the following annotated answers:

Q ex (hdb Υ )( d2, d2 ) = t 2 t 3 t 7 C 2 1 C 2 2 C 3 + t 2 t 4 t 7 C 2 1 C 2 2 C 2 3 + t 2 t 7 C 1 C 2 2 C 3 Q ex (hdb Υ )( d4, d4 ) = 1.
The monomial t 2 t 3 t 7 C 2 1 C 2 2 C 3 that appears in the annotation of the answer d2, d2 of Q ex encodes the fact that this answer can be computed from inconsistent base tuples t 2 , t 3 , t 7 that lead to the violation of the constraints C 1 and C 2 twice and to the violation of the constraint C 3 once.

Hence, the polynomial expression Q(I Υ∪Γ )(t) fully records the inconsistency of an output t in terms of violations of constraints, the inconsistent tuples used to compute it and therefore can be used to quantify the inconsistency degrees of a query outputs. Consider a polynomial P = Q(I Υ∪Γ )(t) of an output t of a given query Q. Each monomial M from P gives an alternative way to derive the output t.

Let I, Q, DC be an instance database, an union of conjunctive queries, a set of denial constraints with identifiers the set Υ, respectively. It is straightforward to notice that in bag semantic answers, ∀t ∈ Q(I ) then Q(I Υ∪Γ )(t) is a monomial.

We categorize the inconsistency measures into two classes: Tuple-based measures, which quantify inconsistency by using exclusively inconsistent tuples.

Constraint-based measures, the measures in this class quantify inconsistency using exclusively violated constraints.

These measures of inconsistency are described below.

Definition of measures

Given an UCQ query Q, we evaluate Q over the instance I Υ∪Γ in order to compute the answers of Q as well as the provenance polynomials semiring annotations associated with each answer. The annotations, which come in the form of polynomial expressions, are then exploited to define several inconsistency measures for query answers. Let I, Q and DC be, respectively, an instance, an UCQ query and a set of denial constraints over a database schema S. Let t ∈ Q(I ) be an answer of the query Q over the instance I.

Let K = N[Υ ∪ Γ].
Applying the query Q to the K-instance I Υ∪Γ , enables to compute the provenance annotation Q(I Υ∪Γ )(t) = P associated with each answer t ∈ Q(I ). This tuple based annotation consists in a polynomial expression P over the set of variables Γ. Recall that the variables that appear in P correspond to identifiers of inconsistent tuples (i.e., elements of IncT(I, DC)). Hence, the polynomial P fully documents how inconsistent source tuples contribute in the computation of the output t. This polynomial also encodes the violated constraints and their occurrence violations. In particular, each monomial M ∈ M(P) gives an alternative way to compute the output t. Based on the polynomial annotation P of a tuple t, different measures can be defined in order to quantify the inconsistency degree of t depending in particular on how one deals with the following three issues:

• Considering query answers semantics, either bag semantics or set semantics, different measures can be developed depending on query answers semantics. When set semantics of query answers is considered, a query answer is computed in several alternative ways. Opposite to the case of bag semantic where a query answer is compute from only one alternative. So, in the case of set semantics, the measures defined consider all the alternative ways while measures in the case of bag semantics have to consider only one alternative way.

• How to deal with a base tuple that contribute more than one time in the computation of the same query answer t? We define two cases: single occurrence, in which a contribution of a source tuple in the computation of an answer is counted at most once, and multiple occurrence, where the exact number of contributions of a source tuple is taken into account when quantifying the inconsistency degree of a given answer.

• What kind of measures to consider? Either tuple-based measures or constraintbased measures.

The combination of the previous dimensions leads to the following twelve measures of inconsistency, as reported in table 4.2. In the rest of this chapter, we assume that t is an answer of Q from a database instance I in presence of a set of denial constraints DC and P = Q(I Υ∪Γ )(t). We assume the following notations: T p = T p(P) and C s = Cs(P).

• Set semantic of query answers. In this semantic, as a given answer t is computed from different ways then |M(P)| ≥ 1, i.e the provenance polynomial of t is a polynomial composed from different monomials.

-Single occurrence, in this semantics, the quantification of an inconsistency degree from a monomial M ∈ M(P) is achieved by counting the number of variables in M (since duplicate contributions are not counted, the exponents of the variables are dropped). The set semantics leads to two measures depending on how alternatives are dealt with: * MIN alternative: is the alternative that considers the way to compute the answer with a minimum inconsistency. Depending to the class of measures, we have the following two measures:

• Tuple-based measure: this measure allows to compute the given answer with the possible minimum number of inconsistent tuples. Hereafter, this measure is denoted by TSS min and it is formally defined as follows:

TSS min (t, I, Q, DC) = min M∈M(T p )
Var(M)

• Constraint-based measure: this measure quantifies inconsistency by considering the alternative way to compute a given answer containing the minimum possible violated constraints. Hereafter, this measure is denoted by CSS min . It is formally defined as follows:

CSS min (t, I, Q, DC) = min M∈M(C s ) Var(M)
Example 4.7. Continuing our running example, the valuation of the query Q ex of Figure 4.1 is processed as illustrated in Table 4.5. Consider the anno-

tation Q ex (hdb Υ )( d2, d2 ) = C 2 1 C 2 2 C 3 t 2 t 3 t 7 M 1 + C 2 1 C 2 2 C 2 3 t 2 t 4 t 7 M 2 + C 1 C 2 2 C 3 t 2 t 7 M 3
.

This annotation conveys the information about the violated constraints by each of the three possible ways to derive the output d2, d2 as an answer to the query Q ex . It shows also the inconsistent tuples used to compute the output d2, d2 , also the violated constraints. We have T p = t 2 t 3 t 7 + t 2 t 4 t 7 + t 7 and

C s = C 2 1 C 2 2 C 3 + C 2 1 C 2 2 C 2 3 + C 1 C 2 2 C
3 , and TSS min ( d2, d2 , I, Q, DC) = 1 CSS min ( d2, d2 , I, Q, DC) = 3 since we have only t 7 that is necessary as inconsistent tuple to compute d2, d2 and C 1 , C 2 , C 3 are violated. * MAX alternative: this alternative considers the way to compute the answer with a maximum inconsistency. Considering the class of measures, we have the following measures:

• Tuple-based measure: this measure takes the alternative way to compute answer with the maximum number number of inconsistent tuples. We denote this measure by TSS max and it is formally defined as follows.

TSS max (t, I, Q, DC) = max M∈M(T p )
Var(M)

• Constraint-based measure: it considers the alternative way to compute a given answer with the possibly large number of violated constraints. We denote this measure by CSS max . It is formally defined as follows -Multiple occurrence. In this semantics, the quantification of an inconsistency degree from a monomial M ∈ M(P) is achieved by computing the weight of M. Hence, if an inconsistent source tuple is used n times in the monomial M or a constraint is violated n times in the monomial M, it will then be counted n times in the quantification of the inconsistency degree from M. The multiple occurrence leads to four measures depending on how alternatives are dealt with: * The MIN alternative shows the option of minimum inconsistency while considering multiple occurrence. Two measures can be defined depending to the classes of measures.

CSS max (t, I, Q, DC) = max
• Tuple-based measure: counts the number of inconsistent tuples used to compute the given answer with the minimum number of use of inconsistent tuples. Denoted by TSM min , it is formally defined as follows:

TSM min (t, I, Q, DC) = min M∈M(T p ) W(M)
• Constraint-based measure: takes as inconsistent degrees the number of times the constraints are violated in order to compute the given answer when the minimum number of times constraints are violated. Denoted by CSM min , it is formally defined as follows:

CSM min (t, I, Q, DC) = min M∈M(C s ) W(M)
Example 4.9. Considering example 4.7, we have TSM min ( d2, d2 , I, Q, DC) = 1 and CSM min ( d2, d2 , I, Q, DC) = 4 since the at least t 7 is used to compute answer and C 1 , C 2 , C3 are violated one time, two times, one time respectively. * The MAX alternative corresponds to the pessimist option opposite to Min alternative, i.e, in this option, we consider the maximum number of violations of constraints or the maximum use of inconsistent source tuples contribute in computation of an answer.

• Tuple based approach: counts the maximum number of times inconsistent tuples are used in different derivations to compute the given answer, this measure is denoted TSM max and is defined as follows

TSM max (t, I, Q, DC) = max M∈M(T p ) W(M)
• Constraint based approach: counts the maximum number of times the constraints are violated among alternative ways to compute the given answer, it is called CSM max and it is defined as follows Example 4.11. Under bag semantics, each derivation corresponds to a distinct answer annotated by a single monomial. This means that the answer d2, d2 is computed three times leading to three answers, a 1 = a 2 = a 3 = d2, d2 , each of which annotated, respectively, with one of the monomials M 1 , M 2 and M 3 . For this example, consider CBM and CBS. The inconsistency degrees of these three answers can then be computed as follows: CBS(a i , Q, I, DC) = 3, for i ∈ [1,[START_REF] Ziawasch Abedjan | Data profiling: A tutorial[END_REF], and CBM(a 1 , Q, I, DC) = 5, CBM(a 2 , Q, I, DC) = 6 and CBM(a 3 , Q, I, DC) = 4. We have also TBM(a 1 , Q, I, DC) = TBS(a 1 , Q, I, DC) = 3.

CSM max (t, I, Q, DC) = max M∈M(C s ) W(M)
A summary of the definitions of these measures is reported in table 4.2. Given a query Q and an instance I and a set of denial constraints DC, Q(I Γ∪Υ ) can be computed in polynomial time in data complexity [START_REF] Deutch | Circuits for datalog provenance[END_REF][START_REF] Green | Provenance semirings[END_REF]. Hence, all these measures of inconsistency degree of answers of a query Q over I (Q(I DC )) can be computed in polynomial in the size of the database instance I.

We consider TBA be the set of measures of inconsistency degrees from tuple-based measures class and CBA be the set of measures from constraint-based measures.

This approach goes beyond the traditional methods that give only information about if a tuple is consistent or inconsistent. So, our approach extends these traditional methods and enables us to compare tuples deeply according to their inconsistencies, each one to the other.

Given a conjunctive query Q, each measure of inconsistency degree of tuple based approach as defined above is bounded by the size of Q (i.e, |Body(Q)|). Also, in the case where Q is a self-join free query the set semantics and the bag semantics coincide. The lemma 4.1 shows these two properties. Lemma 4.1. Let I, Q and DC be respectively an instance, a conjunctive query and a set of denial constraints, for each tuples t ∈ Q(I ) is in form a × x 1 × ... × x m with a ∈ N and {x 1 , ..., x n } is the set of variables (identifiers of inconsistent tuples). There is no repetition, thus the bag semantics and set semantics match one with another.

While our approach is orthogonal to that of CQA in general (as explained in Section 3), our notion of consistency is much stronger than the notion of consistent answers in CQA as stated by the following lemma (lemma 4.2). Lemma 4.2. Let I, Q, DC, α be an instance, an union of conjunctive query and a set of denial constraints, a measure of inconsistency degrees among measures defined above, respectively. ∀t ∈ Q(I ) we have:

α(t, Q, I, DC) = α(t, Q, I, DC) = 0 ⇒ t is a CQA.
Lemma 4.2 is straightforward to prove as any answer that has inconsistency degree equal to 0 is computed from tuples that do not violate any constraint. As these tuples do not involve any violation, they belong to all the repairs of database regardless of the repair semantics. Clearly, the set of CQA can be larger by including the tuples that involve violations and leveraging a given repair semantics.

Example 4.12. Consider the following database instance I with an example of constraint and query:

DC = {C 1 : ← R(x, y, z), R(x, y 1 , z 1 ), y = y 1 } Q(z) : -R(x, y, z) R A B C Prov 1 a 1 C 1 t 1 2 b 2 C 1 t 2 1 c 1 C 1 t 3 3 a 3 1 t 4 2 g 4 C 1
t 5 Consider repair by deletion that is the most repair semantics considered with class of denial constraints [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. The following set of repairs are obtained:

• Rep 1 = {t 1 , t 2 , t 4 } • Rep 2 = {t 1 , t 5 , t 4 } • Rep 3 = {t 3 , t 2 , t 4 } • Rep 4 = {t 3 , t 5 , t 4 }
As t 4 does not violate any constraint in DC, then it belongs to all the repair sets. The set of consistent query answers of Q over I in presence of DC is:

CQA(Q, I, DC) = { 1 , 3 }
since these two answers can be computed over any repair among {Rep 1 , Rep 2 , Rep 3 , Rep 4 }. Now, consider the measure CSS min (any measure can be chosen and the same analyses are done). Our approach returns the query answers, as follows: { 1 , 2 , 3 , 4 } with their inconsistency degrees

• CSM min ( 1 , Q, I, DC) = 1 • CSM min ( 2 , Q, I, DC) = 1 • CSM min ( 3 , Q, I, DC) = 0 • CSM min ( 4 , Q, I, DC) = 1
As one can note, in our case only 3 is consistent. It is also in the set of consistent query answers. But, opposite to the CQA approach, all the query answers are considered and returned, each one with its inconsistency degrees.

Conclusion

This chapter has presented the measures of inconsistency proposed in this thesis leveraging why-provenance and polynomial semiring provenance. We have categorized these measures into two classes: tuple-based measures and constraint-based measures. These proposed measures of inconsistency are intuitive. They also enable the comparison of tuples, each one to the other, according to their inconsistency degree. Their theoretical complexities are polynomial in data complexity.

The next chapter presents the different top-k algorithms developed to rank query answers and enumerate them in a specific order of their inconsistency.

Chapter 5

INCONSISTENCY-DRIVEN QUERY ANSWERING

In this chapter, we study top-k ranking of inconsistency-aware tuples as defined below. For this purpose, we leverage the set of measures of inconsistency introduced in the Chapter 4. We consider as input an annotated instance I Υ∪Γ , where each base tuple t of a relation R is annotated with the monomial I Υ∪Γ (R)(t) (c.f. Definition 4.4). Let α be one of the previous measure of inconsistency degrees defined above, the main idea is to use α as a scoring function over the results of a query Q where the score of an output t of Q is given by α(t, Q, I, DC). The goal is then to rank the answer tuples while taking into account the inconsistency degrees of the base tuples contributing to the answers. The fundamental computation problem is then to be able to efficiently enumerate (part of) query answers in a specific order w.r.t. their inconsistency degrees. We focus on one particular instance of this problem where the goal is to return the query results with the top k scores, hereafter called inconsistency-aware top-k ranking.

Informally, a top-k query Q is a query enabling to compute the first k answers of Q with the highest/lowest scores. These scores are computed using an aggregate scoring function. Depending on the order of the top-k, either k answers with the highest scores or the k answers with lowest scores, we can define separately two types of top-k query: Bottom up top-k(look for the k answers with lowest scores) and Top down top-k queries (look for the k answers with highest scores). Below, we define formally a top-k query in the context of measures of inconsistency degrees. In the rest of paper, we assume that ι ∈ {↑, ↓}. Definition 5.1 (Top-k queries). Let I, Q and DC be respectively a database instance, a conjunctive query and a set of denial constraints over the same database schema. Let k be an integer, let α be one of measure of inconsistency degrees defined above. The Bottom up top-k (resp. Top down top-k) query answers of a query Q using the inconsistency measure α, denoted by Q k,α↓ (I) (resp. Q k,α↑ (I)), is defined as follows:

(i) Q k,α ι (I) ⊆ Q(I ), (ii) |Q k,α ι (I)| = Min(k, |Q(I)|), and (iii) ∀(t 1 , t 2 ) ∈ Q k,α ι (I) × (Q(I) \ Q k,α ι (I)), we have: • α(t 1 , Q, I, DC) ≤ α(t 2 , Q, I, DC) for Bottom up top-k • α(t 1 , Q, I, DC) ≥ α(t 2 , Q, I, DC) for Top down top-k
Condition (i) and (ii) ensure that a top-k query Q k,α ι (I) computes at most k answers of Q(I ) while condition (iii) ensures that the computed answers are the best answers in Q(I ) w.r.t. the inconsistency measure α. The function α is called the scoring function of the top-k problem. We use the notation Q k,α instead of Q k,α ι , when the orders do not matter.The following example illustrates a top-k query over our running example.

Example 5.1. Assume k = 1 and α = CBM. Continuing with the database hdb and the query Q ex as in Figure 4.1, we have:

Q k,α,↓ ex (hdb) = { d4, d4 } and Q k,α,↑ ex (hdb) = { d2, d2 }.
The complexity of evaluation of a top-k query is mainly depending on the nature of the scoring function [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF]. The scoring functions can be divided into two main classes: those functions that are monotonic and those ones that are non-monotonic.

(x) ≤ f (y) ∧ f (z) ≤ f (v) ⇒ f (x • z) ≤ f (y • v)
The aggregate scoring operator • is used to aggregate scores of tuples used to compute an answer with either join( ) or intersection(∩) operators. As example of monotonic function with an aggregate operator, we have the identity function from natural numbers set (i.e, identity : N → N such that identity(x) = x with x ∈ N) that is monotonic with addition (+) as aggregate score operator; since identity(

x) = x ≤ identity(y) = y ∧ identity(z) = z ≤ identity(v) = v ⇒ identity(x + z) = x + z ≤ identity(y + v) = y + v.
Any function that is not monotonic is called a non-monotonic function.

Lemma 5.1. Let MS = {CBM, CSM min , CSM max , TBM, TSM min , TSM max } and N MS = {CBS, CSS min , CSS max , TBS, TSS min , TSS max }. A scoring function that associates to each tuple t a score computed using a measure of inconsistency degrees from MS (respectively, N MS) is monotonic w.r.t. + (respectively, non monotonic).

The proof of the above lemma is trivial since the measures in MS can be reduced to the identity function from N with sum (+) as aggregate operator; however, the measures in N MS are equivalent to cardinal function from subsets of violated constraints or subsets of tuples that involve in violation of constraints (Card : 2 Υ → N for constraint based approach measures or Card : 2 Γ → N for tuple based approach measures) with the set union as aggregate operator.

In the rest of this chapter, we use the terms score and inconsistency degrees equivalently.

Consider t an answer of a query Q over a database instance I. The set of derivations of t is the minimum (under inclusion operator) subsets from I from which t can be computed using Q. Denoted by deriv(t, Q, I), the set of derivations of t is formally defined as follows:

deriv(t, Q, I) = {S ⊆ I : t ∈ Q(S) and ∃S ⊂ S and t ∈ Q(S )}
It is trivial to see that when the bag semantics query answers is considered, the set of derivations of an answer is always a singleton.

Definition 5.3 (Order Compatible (O.C) )

. Let α, I, Q, DC be a measure of inconsistency degrees, an instance, a conjunctive query, and a set of denial constraints, respectively. There exists a naive algorithm enabling to compute the top-k answers of a given query Q with their scores regardless of the class of Q and the scoring function. This naive algorithm computes all the answers of the given Q then sorts them and chooses the k first ones. We shortly note this algorithm NA. The NA algorithm computes a large number of query answers that do not have any utility. It is, then, an efficient top-k algorithm.

The rest of this chapter is organized as follows:

• section 5.1 presents the different dimensions of the problem and the cost model mainly used.

• section 5.2 is dedicated to the top-k algorithms developed for constraint-based measures.

• section 5.3 presents top-k algorithms developed for tuple-based measures.

• section 5.3 concludes this chapter.

Cost-based query answers enumeration

This section discusses two dimensions of the top-k query answering problem: query answers semantics and the query language. Then, it introduces a cost model, consisting to a new cost function and a new class of top-k algorithms, evaluating the top-k algorithms.

Problem Dimensions

Mainly the problem is to enumerate the query answers in order w.r.t. their inconsistency degrees. For the designing of an algorithm to fix this problem, the following dimensions have to be analyzed: Query answers semantics and Query language.

Query answers semantics

We investigate two semantics of query answers: bag semantics and set semantics.

In bag semantics of query answers: each query answer is computed in one alternative way with its score(i.e, ∀t :answer, |deriv(t, Q, I)| = |{S 1 }| = 1). As, for each query answer t there exists only one possible derivation, then the belonging of t to the top-k answers, once it is computed, is less harder than the case where there exits many possible derivations.

In the case of set semantics of query answers, many alternatives (finite derivations) exist to compute the same query answer arising in many scores for the same answer(i.e, ∀t :answer, |deriv(t, Q, I)| = |{S 1 , . . . , S p }| ≥ 1 with p ∈ N * ). Each derivation S i , with i ∈ 1, . . . , p, gives a possible inconsistency degree of t (that is IC i = α(t, Q, S i , DC)). So, we need another function f to aggregate these possible inconsistency degrees of t to obtain the inconsistency degree of t (that is f (IC 1 , . . . , IC p )). So, it is harder to decide the belonging of a query answer t, computed from a derivation d, to the top-k answers based only from this derivation d of t.

So, a top-k algorithm for set answers semantic can be used for bag answers semantic since bag semantic is a special case of set semantic (i.e, the case where the set of derivations is a singleton). But, as we show in the rest of this chapter, it is harder to design a top-k algorithm for set semantic than bag semantic. The following example (example 5.2) illustrates this distinction.

Example 5.2. In this example, we assume that there exist three denial constraints DC = {C 1 , C 2 , C 3 }. We consider below two relations R 1 and R 2 , of an annotated instance I. We consider the conjunctive query Q(z) : -R 1 (x), R 2 (x, z). The column prov contains the set of violated constraints.

R 1 A prov 0 C 1 t 1 1 C 1 C 3 t 2 2 C 1 C 2 t 3 R 2 A B prov 0 a 1 t 4 1 a C 2 C 3 t 5 2 b C 2 t 6
The goal is to enumerate first the most consistent query answers.

• Consider now bag semantics query answers and the measure CBS (any measure of bag semantics query answers can be chosen). The query answers is then:

Q(I ) = [ a : C 1 , a : C 1 C 2 C 2 3 , b ] : C 1 C 2 2 ;
we denote by a i the identifier of the answer at position i in Q(I ), so Q

(I ) = [a 1 , a 2 , a 3 ]; we have Q(I Υ )(a 1 ) = C 1 , Q(I Υ )(a 2 ) = C 1 C 2 C 2 3 and Q(I Υ )(a 3 ) = C 1 C 2 2 . So, we have CBS(a 1 , Q, I, DC) = 1, CBS(a 2 , Q, I, DC) = 3 and CBS(a 3 , Q, I, DC) = 2.
Once a 1 , a 2 , a 3 computed, each one from only one derivation (a 1 from [t 1 , t 4 ], a 2 from [t 2 , t 5 ] and a 3 from [t 3 , t 6 ]), the order a 1 , a 3 , a 2 (most consistent answers first) can be established based on CBS measure.

• For set semantics, Q(I ) = { a , b }. We have Q(I Υ )( a ) = C 1 + C 1 C 2 C 2 3 and Q(I Υ )( b ) = C 1 C 2 2 .
Consider the measure CSS max , then CSS max ( a , Q, I, DC) = 3 and CSS max ( a , Q, I, DC) = 2. The top-2 query answers according to CSS max are then [ b , a ]. As one can easily note, a is computed from two derivations {d 1 = [t 1 , t 3 ], d 2 = [t 2 , t 4 ]}. Depending on the derivation considered the order [ b , a ] can be permitted. Assume that a is computed first from d 1 and we decide to establish order between b and a according to CSS max , then we obtain the following order: [ a , b ] since based only to d 1 the inconsistency degrees of a with CSS max is equal to 1. This leads to an incorrect result. So, for set semantics, it is difficult to rely only on one derivation of query answers to fix order in which query answers are computed according to a measure.

Query language

In the rest of the thesis, we consider the relational algebra language. The expressiveness of conjunctive queries is equivalent to that of relational algebra queries. Depending on the operators of relational algebra used in the query Q, the algorithm used to enumerate query answers in order of their scores can be more complex. An algorithm that enumerates query answers in order of their score can be designed in analyzing the following groups of operators: Selection (σ), Projection (π), Union (∪): In this case, the algorithm simply consists of accessing tuples in the right order according to their scores.

(z) : -R 2 (x, z), x > 0 ≡ π(σ A>0 (R 2 )).
The set of query answers is { a , b } and the inconsistency degrees of a and b are 2 and 1, respectively.

Join ( ), Intersection (∩):

For the case of join and intersection, an answer is computing by joining a set of tuples. Each tuple has its score, so we need an aggregate scoring function • to aggregate these different scores. An algorithm that enumerates answers in a specific order of their score, has to consider the nature of this aggregate scoring function. Since the difficulty of designing an algorithm, that enumerates in a specific order the query answers according to their inconsistency degree, depends to the fact that a measure of inconsistency α is monotonic or non-monotonic w.r.t. •.

Cost models

We introduce a new class of algorithms called SBA and a new cost function. The SBA algorithms defines a set of algorithms that focus mainly and only on the scoring column to evaluate the top-k query. The new cost function enables us to better compare algorithms in SBA than the classical I/O cost function in literature [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF]. In fact, the classical I/O cost model is sensitive to the non determinism caused by the read of tuples having the same score. As the class of algorithms considered (SBA) does not have any information about join attributes, the order in which these tuples(having the same score) should not have an improve on the cost of the algorithm.

are read can have influence on the classical I/O cost.

Semi-blind algorithms

In this section, when we mention prov attribute so we refer to the attribute that contains the annotation value, i.e, the set of constraints violated by the concerned tuple in monomial form. We define S A as a database schema where each table R has a set of attributes A. Let I 1 and I 2 be two relational instances over S A , we define equivalent instances under attributes A:

I 1 ≡ A I 2 iff ∀R ∈ S A , π A (I 1 (R)) = π A (I 2 (R)) with π A (R) the projection over table R on attributes A.
Let Q(X) ← R 1 (X 1 ), . . . , R n (X m ) and I be respectively a conjunctive query and an instance over schema S {prov} . Let AL be an algorithm that allows to compute the answers of Q k,α (I), with α ∈ {CBS, CBM}. A join test J of AL when processing Q k,α over an instance I has the following form J = t 1 . . . t m where t i ∈ I(R i ) with i ∈ [1, m]. A score of a join test is defined as follows: α(J) = α(t 1 . . . t m ). We define jPath(AL, Q, I) as the sequence of joins test performed by the algorithm AL when evaluating Q k,α over I. The intuition is that jPath(AL, Q, I) enables to capture the behavior of the algorithm AL when it evaluates Q k,α over I. Formally, jPath(AL, Q, I) = [J 1 , ..., J n ], where J i = t i 1 . . . t i m , with t i j ∈ I(R j ) and j ∈ [1, m]. We define label(J i ) def = π prov (t i 1 ), . . . , π prov (t i m ) . We are now ready to give the formal definition of the class of Semi-Blind Algorithms (SBA), the algorithms that use only information from the prov column when processing inconsistency-aware queries. Definition 5.4 (SBA algorithms). Let Q k,α be a top-k query, let I 1 , I 2 be two instances, and let AL be an algorithm such that: jPath(AL, Q, I 2 ) = [J 1 , ..., J n 2 ] and jPath(AL, Q, I 1 ) = [J 1 , ..., J n 1 ]. The algorithm AL belongs to the class SBA iff:

I 1 ≡ {prov} I 2 ⇒ label(J i ) = label(J i ), for i ∈ [1, max(n 1 , n 2 )]
According to this definition, an algorithm AL ∈ SBA will have a similar behavior when evaluating a query Q k,α over different instances that are equivalent under prov, i.e., AL will explore the same sequence of join tests but may stop earlier or later depending on the success or failure of the join tests. The outcome of this latter test is related to the content of the join attributes of each specific input instance and remains independent from the prov column. As one can easily notice, TopINC belongs to SBA. Indeed, it only relies on the information given by the prov column without exploiting any auxiliary information.

Region-based cost function

A natural metric to measure the performance of an algorithm AL is to compute the number of tuples of the input relations accessed by AL, denoted cost(Al, Q, I).

Let J = t 1 . . . t m , we denote by tuple(J) = {t 1 , . . . , t m } the set of tuples involved in a join test J. Consider an algorithm AL with jPath(AL, Q, I 1 ) = [J 1 , ..., J n 1 ].

Then, the cost of AL is given by: cost(Al, Q, I) = | n 1 i=1 tuple(J i )|. The following theorem states that there exists no algorithm in the class SBA that is optimal w.r.t. the cost metric defined above. Theorem 5.1. Let Q k,α be a top-k query. Then, we have: ∀Al 1 ∈ SBA,c∃Al 2 ∈ SBA and an instance I such that, cost(Al

1 , I, Q) > cost(Al 2 , I, Q).
Proof. W.l.o.g, assume that m = 2 (i.e., Q is a join between two relations R 1 and R 2 ). Take two integers l > 1, p > 1 such that k ≤ l * p. We build an instance I 1 as follows:

• The relation I 1 (R 1 ) contains two subsets of tuples (the l-tuples and the p-tuples): l tuples t l 1 , . . . , t l l with π prov (t l i ) = π prov (t l j ), ∀i, j ∈ )). Consider an algorithm Al 1 ∈ SBA with jPath(Al 1 , Q, I) = [J 1 , ..., J n 1 ]. We exhibit the following cases regarding the first test join J 1 :

• Case when J 1 = t p 1 t p 2 or J 1 = t p 1
t l 2 (i.e., Al 1 starts reading a p-tuple from R 1 ). We construct an instance I 2 such that I 2 ≡ prov I 1 and all the answers of Q over I 2 are exactly those answers obtained by joining l-tuples of I 2 (R 1 ) with p-tuples from I 2 (R 2 ), i.e., any other join test between tuples of I 2 (R 1 ) and tuples of I 2 (R 2 ) will evaluate to false. Clearly, Al 1 is not optimal to evaluate Q k,α over I 2 because Al 1 starts to process join test that does not lead to any output answer as a result of the fact that label(jPath(Al 1 , Q, I 2 )[1]) = label(J 1 ) (since I 2 ≡ prov I 1 ) and hence Al 1 reads at least one useless tuple (the p-tuple t p 1 which, by contruction of I 2 , do not contribute to any answer). It is easy to see that a round robbin algorithm that alternate reading l-tuples from R 1 and p-tuples from R 2 and performing join tests between the tuples loaded in the memory is optimal. Indeed, to maximize the generated answers for a given cost s (i.e., reading s base tuples), the best strategie is to read s/2 base l-tuples from R 1 and s/2 base p-tuples from R 2 (or inversely) 1 , which enables to compute the maximal number of s/2 × s/2 answers. The behavior of such an algorithm Al 2 is given by jPath(Al 2 ,

Q, I) = [J 1 , . . . , J k ] with J 1 = t 1 l t 1 p , J 2 = t 2 l t 1 p , J 3 = t 1 l t 2 p , J 4 = t 2 l t 2 p , J 5 = t 3 l t 1 p , J 6 = t 3 l t 2 p . . .
Since, Al 2 reads the minimal number of base tuples to compute k answers from I 2 and Al 1 reads at least one useless base tuple, we can conclude that cost(Al

1 , I 2 , Q) > cost(Al 2 , I 2 , Q).
• Case when J 1 = t l 1 t l 2 or J 1 = t l 1 t P 2 (i.e., Al 1 starts reading an l tuple from R 1 ). This case is the dual of the first one and can be proved following the same reasoning while inverting the roles of p-tuples and l-tuples when building I 2 and Al2.

The intuition behind the above theorem 5.1 is that the SBA algorithms need to make a non-deterministic choice among the join tests that have equivalent score. We illustrate this case by relying on a corner case of an instance Î containing exclusively consistent tuples. Consider a query Q over n inputs R 1 , . . . R n such that |Q( Î )| = 1. Consider now the evaluation of the query Q 1,CBS by SBA algorithms. Since all the join tests among the tuples of the input relations will have the same score, an SBA algorithm needs to make a non-deterministic choice among the elements of R 1 × . . . × R n to decide in which order the join tests will be performed. Hence, the best algorithm Al would luckily pick the right tuples in the first round of choice which leads to an optimal cost: cost(Al, Î, Q) = n. The worst-case algorithm Al might end up with the least good cost after exploring the entire cartesian product of the inputs, which leads

to cost(Al, Î, Q) = n ∑ i=1 |R i | (i.e.
, the algorithms Al needs to read the entire inputs).

Consequently, we argue that it is not worthwhile to distinguish between SBA algorithms w.r.t. to the order of exploring join tests with equivalent score (since this is a non-deterministic choice). We formalize this notion using regions, defined as maximal rank join algorithms [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF] is to process the tuples of the relations involved in a given query in a specific order by considering at each step the most promising tuples at first. However, when the scoring function is not monotonic with respect to the join operator, which is the case for CBS due to single-occurrences, it is not straightforward to identify the order in which tuples should be processed. The core intuition of our top-k ranking algorithm consists of using an index based on the inconsistency measures to access the most promising tuples at each step of query processing. More precisely, we build for each relation R, an associated index, denoted ind(R), whose nodes are labeled by a subset of the constraints. More precisely, each node B of Ind(R) is labeled with label(B) ⊆ DC. A node B stores the set of tuples's ids of R, denoted B(R), that violate exactly the set of constraints label(B), i.e., the set B(R) = {t ∈ R | VC(I, DC, t) = B}. We call B a bucket of the index Ind(R) and the set B(R) the bucket content.

Example 5.4. In our example, the buckets of the index are labeled with subsets of the constraints DC = {C 1 , C 2 , C 3 }. For instance, a bucket B 0 , with label(B 0 ) = ∅, will store the consistent tuples B 0 (D) = {t 1 }, B 0 (S) = {t 5 , t 6 } and B 0 (V) = {t 8 } of the relations D, S and V. The labels of the buckets and the content of the buckets are given below. We now describe the Algorithm in detail. Let Q be a query Q(u) ← R 1 (u 1 ), . . . , R m (u m ). In order process the query Q k,α , with α ∈ {CBS, CBM}, the algoritm TopINC (c.f., Algorithm 1) takes as input: the query Q k,α , the indexes ind(R i ), with i ∈ [1, m], one for each input relation and the set ViolC of the violated constraints obtained by unioning the labels of all the buckets in the indexes. The algoritm uses as many temporary buffers HR i , i ∈ [1, m] as the number of indexes. Each temporary buffer contains the bucket contents. In addition, the algorithm uses a vector jB of size m storing the ids of the buckets that need to be joined during the course of the algorithm. The algorithm TopINC follows a level-wise sequencing of the iterations, where each level denotes the inconsistency degree of the answers computed at this level (c.f., lines 4-8 of algorithm 1). Level 0 means that consistent tuples are processed while the subsequent level l indicates the number of constrainst that are considered for the violated tuples. When processing a given level l, the algorithm resets the variable curVSet, used to keep track of the violated constraints while exploring the input relations at level l, and makes a recursive call to the IterateJoin procedure (line 7). For each level l, the IterateJoin procedure (Algorithm 2) explores the input relations sequentially from R 1 to R m (lines 11 to 14). For each input relation R p , IterateJoin uses the index ind(R p ) to identify the buckets of R p that are worthwhile to consider for the join (i.e., the buckets to be loaded in jB[p]), i.e., those buckets whose label size's is less than l (line 5). The relevant bucket ids of input relations are loaded in the jB buffer (line 13 of algorithm 2) and when R p is the last input relation (i.e., p = m) (line 15) a join is performed between the buffers of jB (lines 17-20 of the algorithm 2) in order to compute the answers with inconsistency degree equal to the current level l. Note that the variable curVSet will contain duplicate occurrences if α = CBM (line 10) and single occurrences if α = CBS (line 7). It enables us to keep track of the current level of inconsistency while exploring the inputs. When intermediate inputs are explored, the IterateJoin algorithm ensures that |curVSet| does not exceed the current inconsistency level l (line 5 and line 11). When the last input is processed, a join is performed between the buckets in jB only if |curVSet| = l (line 15) which ensures that the computed answers have l as inconsistency degree. Example 5.6. We assume that the input relations are processed in this order: D, S and V. We illustrate the processing of query Q 2,CBS ex (I) by TopINC. Figure 5.2 exemplifies the iterations of the algorithm. The gray cells, in each step, denote the newly read tuples in that step. The final result (Level 3) is reported at the bottom of the Figure 5.2. Starting from level 0, the selected buckets are jB = [B 0 , B 0 , B 0 ], thus leading to join the contents of these buckets only at the very beginning. The contents of HV(B 0 ), HS(B 0 ) and HD(B 0 ) are shown in Figure 5.2. The first answer corresponding to the join of the above buffers is found (i.e, res = [ d4, d4 ]). The TopINC continues to read in selected buckets in jB. It then tries to read in B 0 of V but no additional tuples, then it moves to read in B 0 of V. Next, the tuple 02, d2, 5 is loaded in HV(B 0 ) but no additional answer is found. As there is no additional answers (because k=2) and all tuples are read in selected buckets, TopINC jumps to the next level, i.e, the level 1. At this level, the first selected buckets are jB = [B 0 , B 1 , B0], thus leading to read the only one tuple of bucket B 1 of relation V into HV(B 1 ). But no additional answer is found and no others buckets in level 1 can be selected bringing TopINC to level 2. Finally, TopINC processes level 2 and then level 3 as shown in Figure 5.2 and halts when it reaches |res| = 2.

B B 0 B 1 B 2 B 3 B 4 B 5 B 6 B 7 l(B) ∅ {C 1 } {C 2 } {C 3 } {C 1 , C 2 } {C 1 , C 3 } {C 2 , C 3 } {C 1 , C 2 , C 3 } B(D) {t 1 } ∅ ∅ ∅ {t 2 } ∅ ∅ ∅ B(S) {t 5 , t 6 } {t 3 } ∅ ∅ ∅ {t 4 } ∅ ∅ B(V) {t 8 } ∅ ∅ ∅ ∅ ∅ {t 7 } ∅ Each index ind(R)
The following two lemmas state the correctness and the worst case complexity of TopINC, respectively. Lemma 5.2. Let α ∈ {CBM, CBS}. The algorithm TopINC computes correctly Q k,α (I).

Proof. The TopINC algorihtm proceeds one level at a time. It starts from inconsistency degree 0 to upper inconsistency degrees. At each inconsistency degree d fixed, it looks for all the joins of buckets (from join relations) where the union of their labels has cardinality d; the join is only performed among the tuples within the buckets found. It stops processing when k answers are found otherwise TopINC continues to look for the remaining joins of buckets for the same inconsistency degree d; if there exists no other join of buckets that leads to inconsistency degree d, the TopINC moves forward to inconsistent degree d + 1. Hence, this processing ensures that the K answers output by TopINC are correct. Proof. This lemma 5.3 is a consequence of the level-wise approach followed by TopINC which ensures that query answers are computed in the ascending order of their inconsistency degree. Hence, TopINC strictly computes the answers that belong to the output (and the algorithm stops when k answers are computed, hence the spatial complexity in O(|I | + k * s) with the maximal size of an answer). The time complexity O(n m ) is due of the fact that tuples are read one by one according to their scores; with every reading of one tuple, a join test is done to search a new answer. So, one can easily denote that the join algorithm can quickly become a nested loop algorithm: so the worst complexity is O(n m ) with n = |I| and m the size of the input conjunctive query Q.

Lemma 5.3. Let Q(X) ← R 1 (X 1 ), . . . , R m (X m )
i := i + 1;
Unsurprisingly, and like most of state of the art top-k join algorithms that do not use specific knowledge related to the join attributes (e.g., see [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF][START_REF] Schnaitter | Optimal algorithms for evaluating rank joins in database systems[END_REF]), the worst case time complexity of TopINC is in O(|I | m ), with m the number of input relations in Q. Interestingly, the previous lemma also provides a tighter upper bound regarding the space complexity. This lemma is a consequence of the level-wise approach followed by TopINC which ensures that query answers are computed in the ascending order of their inconsistency degree. Hence, TopINC strictly computes the answers that belong to the output (and the algorithm stops when k answers are computed).

The following theorem shows the optimality of TopINC in the SBA algorithms.

Theorem 5.2. For any instance I and any top-k conjunctive query Q k,α , we have:

cost ∇ (TopINC, Q, I) ≤ cost ∇ (AL, Q, I), ∀AL ∈ SBA Proof. Let Q k,α
, with α ∈ {CBM, CBS}, be a top-k query over an instance I. Assume that there exists an algorithm AL ∈ SBA that outputs Q k,α (I) with cost ∇ (AL, Q, I) < cost ∇ (TopINC, Q, I). The intuition behind our proof is that if TopINC explores a region Z that is not explored by AL then AL is not correct (i.e., it do not correctly compute the top-k answers). Note that, when TopINC starts performing join tests with inconsistency degree d, it fully explores the region (i.e., performs all the possible join tests with inconsistency degree d) before moving to another region. In addition, TopINC processes

R 1 X Y Z 0 1 a 1 0 1 b C 1 R 2 X z 1 0 5 1 2 6 C 3 0 1 C 2 C 3 1 3 C 1 C 2 R 3 Y z 2 1 b 1 4 c C 1 C 3 3 d C 2 R 4 z 1 W 5 a 1 3 b C 2 1 a C 3 Q(x, y, z, z 1 , z 2 , w) : -R 1 (x, y, z), R 2 (x, z 1 ), R 3 (y, z 2 ), R 4 (z 1 , w) a. R 1 (x, y, z) R 2 (x, z 1 ) R 3 (y, z 2 ) R 4 (z 1 , w) b. R1 KEY VALUE 0, 1, a : 1, 1,
buckets = [[1, C 1 ], [1, C 3 , C 2 C 3 , C 1 C 3 ], [1, C 1 C 3 , C 2 ], [1, C 2 , C 3 ]] Level = 0 comb = [1, 1, 1, 1] KEY VALUE 0, 1, a : 1 KEY VALUE 0 0, 5 : 1 KEY VALUE 1 1, b : 1 KEY VALUE 5 5, a : 1 Res = { 0, 1, a, 5, b, a } level = 1 comb = [1, 1, 1, C 2 ] KEY VALUE 0, 1, a : 1 KEY VALUE 0 0, 5 : 1 KEY VALUE 1 1, b : 1 KEY VALUE 3 3, b : C2 Res = { 0, 1, a, 5, b, a } comb = [1, 1, 1, C 3 ] KEY VALUE 0, 1, a : 1 KEY VALUE 0 0, 5 : 1 KEY VALUE 1 1, b : 1 KEY VALUE 1 1, a : C3 Res = { 0, 1, a,
|I| δ + k).
This algorithm can be effective in using for CBS than TopINC if a large main memory is available and the database can be entirely and quickly loaded in this main memory.

TopMultiSet algorithm

The algorithm TopMultiSet is designed to compute the k answers of given query in I that are the most consistent (or inconsistent) with respect to the measures of inconsistency degrees CSM min (or CSM max ). It is based on the algorithm developed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF]. The algorithm designed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF] assumes a monotone scoring function, and enumerates answers in order of their scores. It is designed in a case of a bag semantics of query answers. The is composed to two parts: a preprocessing part (performed by the function called preprocess) that associate some data structures on each node during tree building from the hypergraph that represents the conjunctive query, and an enumeration part (performed by the function called enum) that allows to enumerate answers in order of their scores.

Each node no of the tree represents an input relation or a join result of subset of input relations (intermediary result), denoted rel(no). We denote by parent(no) the node parent of no. Let comVarP(no) the common variables between the node no and its parent. The node no contains a subset of variables from the input query denoted var(no). It contains a map structure, denoted map(no), containing the input data of the relation that this node represents. The keys values of the map(no) is the set of tuples obtaining by making projection on comVarP(no) and in rel(no). Given a key ke, the value corresponding in the map(no) is a priority queue containing all the tuples in rel(no) that have projection value, on comVarP(no) and in rel(no), equal to ke.

The tuples in the priority queue are ordered according to a global score (i.e, score obtained by aggregating score of tuples in join) of tuples. Let child(no) be the child nodes of the node no. Consider t a tuple, we denote par t.score the score of t and the global score of t is denoted by t.global. The global score of a tuple t in a left node is equal to the score of the tuple(i.e, when t is a leaf node then t.score = t.global). For any tuple t in a internal node n1, we have

t.global = t.score + ∑ n0∈child(n1) map(n0)[t[comVarP(n0)]].top.global
with t[V] the projection value of set of variables in V; and top calls on the priority queue gives the tuple with the larger/smaller global score.

After the preprocessing, the first answer can be already enumerated. Once an answer is enumerated, the tree is updated to prepare the next answer. The update of the tree is done as follows: from the leafs to the root of the tree, for each node n0 let t be the tuple used in the current answer; t is in a priority queue Qe; let [n 1 , . . . , n p ] the child nodes of n0, then t is joined with [map(comVarP(n 1 )).top, . . ., map(comVarP(n p )).top]; t is replaced by p other copies of t such that the i th is joined with [map(comVarP(n 1 )).top, . . . , map(comVarP(n i-1 )).top, next(map(comVarP(n i )).top), map(comVarP(n i+1 )).top, . . . , map(comVarP(n p )).top]

where next(map(comVarP(n i )).top) is the top element in the priority queue after deleting of the top element of the priority queue. If the next top element of map(comVarP(n i ) is null, i.e, it does not exist a new for the top element then the i th copy of t is ignored. After this update of the tree, a new answer can be computed, if the root node is not empty.

The TopMultiSet algorithm needs the satisfaction of the order compatibility between the top-k order and the scoring function. It performs such that during the enumeration of an answer, its duplicate instances are directly removed, i.e, an answer is computed once. The pseudo code of this algorithm is given in algorithm 4. First, a preprocessing is done to generate the join tree with all the necessary data structures by the preprocessing algorithm designed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF], as mentioned by the line 1 of algorithm TopMultiSet. The algorithm enables, in an iterative way, to enumerate one by one the answer in order of their score developed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF] is used to return at each step the next best answer. As the enumeration algorithm developed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF] is designed

R 2 (z, z 1 , z 2 ) R 1 (x, z 1 ) R 3 (y, z 2 )
a.

R2

KEY VALUE e, 1, 1 : 0, e, 2, 2 : 0, e, 3, 1 : 2

R1 KEY VALUE 1 a, 1 : 1 2 a, 2 : 1 3 a, 3 : 2 R3 KEY VALUE 1 b, 1 : 0, c, 1 : 1 2 b, 2 : 2 b. R2 KEY VALUE [ e, 1, 1 : 0 : 1 : [r 1 1 , r 1 3 ], e, 2, 2 : 0 : 3 : [r 2 1 , r 3 3 ], e, 3, 1 : 2 : 4 : [r 3 1 , r 1 3 ]] R1 KEY VALUE 1 [r 1 1 = a, 1 : 1 : 1 : []] 2 [r 2 1 = a, 2 : 1 : 1 : []] 3 [r 3 1 = a, 3 : 2 : 2 : []] R3 KEY VALUE 1 [r 1 3 = b, 1 : 0 : 0 : [], r 2 3 = c, 1 : 1 : 1 : []] 2 [r 3 3 = b, 2 : 2 : 2 : []]
c. • R 2 = { e, 1, 1 : 0, e, 2, 2 : 0, e, 3, 1 : 2}

• R 3 = { b, 1 : 0, b , 2 : 2, c, 1 : 1}
The value after the «:» gives the score of the tuple. The score means the number of constraints violated by the tuple. Now consider the following conjunctive query

Q(x, y, z) : -R 1 (x, z 1 ), R 2 (z, z 1 , z 2 ), R 3 (y, z 2 )
The goal of this example is to find the top-2 answers that is the most consistent answer w.r.t. the measure CSM min . As CSM min is compatible with this order of top-k, we can compute correctly the top-2 using TopMultiSet algorithm.

The join tree of Q is depicted in the figure 5.5.(a), the tree with data of Q is depicted in the figure 5.5.(a). After that, the preprocessing step runs and the first answer is directly computed as shown in 5.5.(c). In the tree 5.5.(b), after the first «:» we have the score (i.e, number of constraints violated) of the tuple, and after the second «:» we have the total best score aggregated from the children nodes (global score). The array after the last «:» contains the addresses of tuples joined with the current tuple. It is interesting to keep that since a tuple t used in a child node is removed from its priority queue Qe. But the tuple t keeps a link with the next best element of Qe.

The illustration of the algorithm TopMultiSet is done in figure 5. [START_REF] Amezian | Optimization of answer set programs for consistent query answering by means of first-order rewriting[END_REF]. The first answer is then a, b, e : 1. As we need to compute the two first consistent answers, the algorithm TopMultiSet continues to run. The join tree 5.6.(a) shows the state of the join tree 5.5.(c) after computation of the first answer a, b, e : 1 . Once the answer a, b, e : 1 is computed, the current tree 5.6.(a) on which this answer is compute is divided into three other trees (tree 5.6.(b1), tree 5.6.(b2) and tree 5.6.(b3)). In the tree 5.6.(b1), the tuples with projection value on the first column equal to a are removed; in 5.6.(b1) and 5.6.(b3) are removed tuples with projection value on the first column equal to e and tuples with projection value on the first column equal to b , respectively. Among these new trees only the tree 5.6.(b3) can give new answers, it is depicted in 5.6.(c) after dangling tuples eliminations. Then the next answer is a, c, e : 2.

Lemma 5.8. The algorithm TopMultiSet computes correctly the k most consistent (resp. inconsistent) answers w.r.t the measures CSM min , TSM min (resp. CSM max , TSM max ) Proof. Assume that there are two a 1 and a 2 (a 1 = a 2 ) such that the degree of inconsistency of a 1 by CSM min or by TSM min is strictly greater than that of a 2 and a 1 is in the set of top-k consistent answers computed by TopMultiSet w.r.t the measures {CSM min , TSM min } but a 2 is not in this set. That means that:

1. a 1 is computed from a join tree different from the join tree of a 2 2. a 1 is computed from the same join tree than a 2 If (1), it is absurd since the join trees are sorted in a priority queue according to their first element. If (2) also, it is absurd because in the tree join the first element is returned using the same technique as in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF]. Then, the algorithm computes exactly the correct answers. Also by the partition strategy, there is no redundant answer in the answers returned by the TopMultiSet algorithm.

Lemma 5.9. The data complexity of TopMultiSet running is O(

(|I | δ + log(|I |)) * k)
Proof. The maximal intermediary result generating during the join tree building is |I| δ and log(|I |) is for the internal priority queue in the tree join to find the first element of the join tree. For each answer computed, at most |I| δ + log(|I |) operations are done. So, the complexity is bounded by

(|I| δ + log(|I |)) * k

TopIncSet algorithm

Considering, the measures CSS min and CSS max , we obtain function that are not monotonic opposed to CSM min , TSM min , CSM max , TSM max that are monotonic. So, we design a new algorithm based on TopIncMem algorithm to handle the problem of top-k answers w.r.t. CSS min (for the most consistent answers) and w.r.t. CSS max (for the most inconsistent answers).

We proceed as in the case of TopMultiSet algorithm that takes as kernel the algorithm of enumerating developed in [START_REF] Deep | Ranked enumeration of conjunctive query results[END_REF]. The TopIncSet algorithm takes as kernel the algorithm TopIncMem. When an answer is computed, in the same way as in Top-IncMem, the algorithm of partition is used to partition the current join tree (i.e, the tree used to generate the answer) into m other problems (trees). The Different trees are kept in a set data structure, contrary to the case of TopMultiSet where they are kept in a priority queue. The choice of a set rather than a priority queue is the fact that we can not know the best answer in the join tree easily. The algorithm TopIncSet runs as follows: for each combination of violated sets found (as done in algorithm TopIncMem), all the join trees generated by the partitioning operation are visited in an iterative way. Once a tree is chosen, the current combination is used to compute the next answers of the input query.

As one can easily note, this algorithm enable correctly to compute the k first answers that are the most consistent w.r.t. the measure CSM min and the k most inconsistent answers w.r.t. to CSS max .

Algorithms for tuple-based measures

This section presents top-k algorithms for tuple-based measures. They can be also categorized into two classes: Memory-based algorithms and Disk-based algorithms. These algorithms and measures for which they are designed are depicted in figure 5.7.

TupIncRank algorithm

The TupIncRank algorithm computes the top-k answers that are the most or less inconsistent with respect to the measure TBM. The algorithm TupIncRankcan be used with TBS in the case where the input query is a free self join conjunctive query. As input, TupIncRank algorithm takes an annotated instance database, a conjunctive query and an integer k(that is the number of the first inconsistent/consistent answers of the query). The database is annotated, in a way that each inconsistent tuple is annotated by 1 and each consistent tuple is annotated by 0.

The algorithm TupIncRank works simply as follows. It maintains a set noted by incSet (as shown in line 7), this set contains all the identifiers of relations that have to be inconsistent in the next join performing. Any relation out of this set has its part entirely consistent considered in the next joins to do. The set incSet starts with empty set, in other word, in the next join only consistent parts of relations, in join, have to considered. The algorithm TupIncRank iterates, in a descending order according to the number of inconsistent relations considered, the lattice formed by the subsets of the set of relation identifiers in join. For example to have all the answers of a query Q that have inconsistency degrees equal to 2, we have to do join with 2 relations with their parts entirely inconsistent, so the cardinality of incSet has to be two. Once the value of incSet is found, TupIncRank read one by one the tuples from relations parts considered (as in line 9 and line 17). At each step of read of new tuple the join is performed with the set of tuples already read (at line 13 and at line 24). In line 9, readNext function is used. ReadNext function takes a relation R i and a binary value (0 or 1: InconsParts[i] value) and read the next tuple in R i with inconsistency 1 or 0 according to InconsParts[i] value. This new tuple is added into the buffer HR i [InconsParts [i]]. Once, TupIncRank found the k answers, its stops query processing and outputs the k answers. Let's illustrate TupIncRank algorithm in the example 5.10.

Example 5.10. Continuing with our illustrative database used in the previous examples. The goal of this illustration is to find the 2 first answers that are the most consistent w.r.t the measure TBM and TBS. By R [1] we mean the set of tuples read in R. The annotated database obtained is the following: With the query Q ex

• IncSet = ∅ TBS ≡ TBM ≡ 0 HD Key Value 0 t 1 HS Key Value 0 t 5 HV Key Value 0 t 8 Q({D[0], S[0], V[0]}) → TopK = [ 04, 04 ] HD Key Value 0 t 1 HS Key Value 0 t 5 ,t 6 HV Key Value 0 t 8 Q({D[0], {t 6 }, V[0]}) → TopK = [ 04, 04 ] • IncSet = {D} TBS ≡ TBM ≡ 1 HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 HV Key Value 0 t 8 Q({D[1], S[0], V[0]}) → TopK = [ 04, 04 ] • IncSet = {S} TBS ≡ TBM ≡ 1 HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 1 t 3 HV Key Value 0 t 8 Q({D[0], S[1], V[0]}) → TopK = [ 04, 04 ] HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 1 t 3 ,t 4 HV Key Value 0 t 8 Q({D[0], {t 4 }, V[0]}) → TopK = [ 04, 04 ] • IncSet = {V} TBS ≡ TBM ≡ 1 HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 1 t 3 , t 4 HV Key Value 0 t 8 1 t 7 Q({D[0], S[0], V[1]}) → TopK = [ 04, 04 ] • IncSet = {D, S} TBS ≡ TBM ≡ 2 HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 1 t 3 , t 4 HV Key Value 0 t 8 1 t 7 Q({D[1], S[1], V[0]}) → TopK = [ 04, 04 ] • IncSet = {D, V} TBS ≡ TBM ≡ 2 HD Key Value 0 t 1 1 t 2 HS Key Value 0 t 5 , t 6 1 t 3 , t 4 HV Key Value 0 t 8 1 t 7 Q({D[1], S[0], V[1]}) → TopK = [ 04, 04 , 02, 02 ]
The running of TupIncRank algorithm is stopped since two answers are found.

Theorem 5.3. The algorithm TupIncRank computes correctly the top-k answers that are the most consistent w.r.t measures TBM and TBS.

Proof. We proof this theorem by absurd . Let Q(X) : -R 1 (X 1 ), . . . , R n (X n ), φ(X 1 , . . . , X n ) be a query. Consider the two answers t 1 and t 2 of Q with inconsistency degrees with measures TBM(also with TBS) equal to a 1 and t 2 , respectively, such that a 1 > a 2 . So there are S 1 ⊆ {1, . . . , n} and S 2 ⊆ {1, . . . , n} such that |S 1 | = a 1 and |S 2 | = a 2 . We have also,

t 1 ∈ Q({R i [1] : i ∈ S 1 } ∪ {R i [0] : i ∈ {1, . . . , n}/S 1 }) and t 2 ∈ Q({R i [1] : i ∈ S 2 } ∪ {R i [0] : i ∈ {1, . . . , n}/S 2 }). Assume that TupIncRank computes t 1 before t 2 . If t 1 is computed before t 2 by TupIncRank then S 1 is explored by TupIncRank before S 2 .
That is absurd since the lattice formed by the set of relations in join is iterated in order of their size.

Theorem 5.4. Consider the problem of computing of the k first answers that are the most consistent w.r.t measures TBM and TBS(case where query is fSJ CQ), then 1. the algorithm TupIncRank is optimal in the class of SBA with the most measure cost ∆ 2. no additional answer is computed outside of the k first answers that are the most consistent w.r.t TBM and TBS

Proof. Let's consider Q(X) := R 1 (X 1 ), . . . , R n (X n ), Φ(X 1 , ..., X n ) as the input query.
The algorithm TupIncRank is level-wise algorithm. It iterates the lattice formed by the set of name/identifiers of relations in join (i.e, the set {R 1 , . . . , R n } 2 ). Assume that there is an algorithm Al ∈ SBA that computes the k first consistent answers of Q for measures TBM and TBS with p 1 visited regions and TupIncRank computes the same set of answers of Q with p 2 visited regions such that p 1 < p 2 . When an algorithm in SBA start to visit a region, all the regions are crossed before starting to visit an other region and no index on join attributes is available. As a region matches a set of join tests with the same score (inconsistency degrees), in the case of TBS and TBM a region corresponds to the cardinality of number of relation totally inconsistent in join. The algorithm TupIncRank iterates the lattice of relations in join from empty set to the set of all relation (i.e, in ascending order). Each set of relations SR selected means that relation in SR have to be completely inconsistent and those are out of this set are completely consistent. So, if Al crosses less regions than TupIncRank after acclaiming the top-k answers then Al skipped and ignored some regionsimplies that Al does not correctly the top-k answers. So, either any algorithm of SBA than TupIncRank is incorrect either it crosses more regions or equal than TupIncRank after acclaiming the top-k results.

The TopINCDE and TopMultiSet algorithms can be used to process top-k algorithm with TSM min , TSM max measures and TSS min , TSS max measures if the query is free self join.

A top-k algorithms can be used to fix some filtering problems such as: compute the first answers that have the inconsistency/inconsistency degrees greater than or less than or equal a given value.

Conclusion

We designed a set of algorithms to perform top-k query with our proposed measures as scoring functions. We explain the different dimensions to consider for designing a top-k algorithm for these measures. We categorize these algorithms according to their cost models. We shown the optimality of some of these algorithms while given their theoretical complexities. In the next chapter, we present our approach to fix inconsistency in the case where the set of constraints are inconsistent.

Chapter 6

PRESENCE OF INCONSISTENCY IN SET OF CONSTRAINTS

In the previous chapters, we assume that the set of constraints considered is consistent. We present in this chapter preliminary results considering a context in which the set of denial constraints are inconsistent. In particular, we define in this context a set of measures quantifying inconsistency of query answers.

Let DC be a set of denial constraints defined from schema S.

The set DC is inconsistent if only if: ∃I = ∅, an instance database over the schema S, such that I |= DC. Example 6.1. Consider a schema S = {R(A, B, C)} and the following set of denial constraints on S:

• C 1 : ← R(x, y, z), x ≤ y • C 2 : ← R(x, y, z), z ≥ y • C 3 : ← R(x, y, z), z ≤ x then the set {C 1 , C 2 , C 3 } is inconsistent
because there is no instance from S (different from empty set) that satisfies this set of constraints. Since there are no three real numbers x, y, z such that x < y, y < z and z < x.

In the following, first, we define some measures of inconsistency degrees based on the set of measures defined in chapter 4. In the second part, we introduce a top-k algorithm, to compute the k first answers that are the most/less inconsistent answers, that is also based on the TopINC algorithm.

Fixing inconsistency problem

One way to handle inconsistency of query answers in presence of inconsistent set of constraints DC is to consider the set of maximal consistent subsets of constraints from DC. The inconsistencies of tuples (in database instance) or query answers are computed w.r.t a maximal consistent subset of DC. We denote by MC(DC) the set of maximal consistent subsets of a set of constraints DC. We define, in the following, formally this notion of set of maximal consistent subsets of constraints. In this thesis, we assume that this set exists and it is finite for any inconsistent set of constraints considered. We do not study the computation problem of MC(DC). The problem of satisfiability of set of denial constraints (i.e, checking if a set of denial constraints is consistent) is studied in [START_REF] Baudinet | Constraint-Generating Dependencies[END_REF]. Example 6.2. Consider the set of constraints considered in the example 6.1. The set of maximal consistent subsets of DC is : MC(DC) = {S 1 , S 2 , S 3 } where S

MC(DC

1 = {C 1 , C 2 }, S 2 = {C 1 , C 2 }, S 3 = {C 2 , C 3 }.

Strong Consistent Query Answers (SCQA)

Given a database D and a set of denial constraints DC. If DC is inconsistent, it is not possible to find a repair of D. Since by definition an inconsistent set of constraints DC is a set of constraints for which there is no non empty instance that satisfies it. Hence, it is impossible to handle inconsistency by repairing data as done in literature [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. As we can not define the notion of repair in the context of inconsistent set of constraints, what about the CQA [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF] handling ? As the notion of repair does not exist, so the notion of CQA also does not exist.

In this section, we define a new semantic of query evaluation, based on the idea of CQA, in a context of inconsistent set of denial constraints. This notion, called strong consistent query answers, is based on MC(DC). For each maximal subset of consistent constraints, we compute the consistent query answers using one of semantic of repair defined in literature. Once, these consistent query answers are computed for each M ∈ MC(DC), the strong consistent query answers is obtained by doing intersection these consistent query answers. The strong consistent query answers is useful since it means that no matter the maximal consistent set of denial constraint from DC, these answers can be obtained. The main challenge behind SCQA is its computation problem. Even the special case where |MC(DC)| = 1, the computation problem of SCQA remains intractable(in data complexity) in general [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]. Also, there exists some particular cases where SCQA is always empty as shown in theorem 6.1. Theorem 6.1. Let DC be an inconsistent set of constraints and let I be a database instance. For any full conjunctive query Q, we have:

SCQA(DC, Q, I) = ∅ Proof. Let Q(X) : -R 1 (X 1 ), . . . , R m (X m ), φ(X 1 , .
. . , X m ), DC, I be respectively a full conjunctive query, a set of denial constraints and a database instance. As the query Q is a full conjunctive query then each answer A corresponds to an unique set {R 1 (A 1 ), . . ., R m (A m )}. Assume now that SCQA(DC, Q, I) = ∅ and assume that A ∈ SQCA(DC, Q, I). This means that for each S ∈ MC(DC) there exists a repair R that contains at least the elements from {R 1 (A 1 ), . . . , R m (A m )}. As this repair exists for each S ∈ MC(DC) then S∈MC(DC) S = DC is satisfied at least by the set {R 1 (A 1 ), . . ., R m (A m )}. Absurd since DC is inconsistent.

We can consider the computation problem of SCQA by maximal consistent subset of DC. Given a maximal consistent subset S of DC, we use the classical techniques [START_REF] Bertossi | Query Answering in Inconsistent Databases[END_REF] to compute the CQA w.r.t S. So, SCQA can be computed with the same data complexity than the existing algorithms to compute CQA [START_REF] Bertossi | Query Answering in Inconsistent Databases[END_REF].

Quantifying inconsistency degrees of query answers

As preliminary work, we define below inconsistency degrees of query answers under bag semantics in a context where the set of denial constraints is inconsistent. The idea behind these new measures is to quantify inconsistency of a query answer t for each maximal consistent set of constraints. And then, we have to use an aggregate function to aggregate these different inconsistency degrees to obtain a global inconsistency degrees of t. We call this type of measure a relative measure. Definition 6.2 (Relative measure). Let Q be a conjunctive query, DC be a set of denial constraints and I be a database instance. Let α ∈ {CBS, CBM, TBS, TBM}; let f : R p → R with p ∈ N * , an aggregate function. The relative measure of inconsistency degrees for an answer t ∈ Q(I ), based on α and f , is formally defined as follows R f α (t, Q, I, DC) = f (α(t, Q, I, S 1 ), . . . , α(t, Q, I, S p )) with MC(DC) = {S 1 , . . . , S p }. • CBS(t 1 , Q 1 , I, S 1 ) = 0

• CBS(t 1 , Q 1 , I, S 2 ) = 0 • CBS(t 1 , Q 1 , I, S 3 ) = 1
• Consider the aggregate function sum then R sum CBS (t 1 , Q, I, DC) = sum(0, 0, 1) = 1 • With the aggregate function min then R min CBS (t 1 , Q, I, DC) = min(0, 0, 1) = 0

Query answers ranking by inconsistency degrees

In this section, we show how to modify TopINC algorithm to work with the relative measures R f CBS .

Top-k algorithm with R f CBS

The algorithm designed in this section considers only the relative measure R f CBS , i.e, the relative measure that is based on CBS measure and any other aggregate function f . It is denoted by RTopINC. The algorithm RTopINC has the same data complexity than TopINC. In the rest of this chapter, we consider DC the set of denial constraints and we assume that MC(DC) = {S 1 , . . . , S p }. We use f as an aggregate function.

With the algorithm RTopINC, we proceed in two steps. The first step consists to build an index. This index, denoted orderVio(DC, f ), is computed once, i.e, it is independent from input query. In the second step, the top-k query is evaluated by the algorithm TopINC using orderVio(DC, f ).

Building of orderVio(DC, f)

We define formally OCBS(S, f , DC), where S ⊆ DC, as follows:

OCBS(S, f , DC) = f (|S ∩ S 1 |, . . . , |S ∩ S p |)
Informally, we define orderVio(DC, f ) as list of elements of 2 DC (i.e, the power set of DC). Elements of orderVio(DC, f ) are ordered w.r.t measure R f CBS . Formally orderVio(DC, f ) is defined as follows

orderVio(DC, f ) = [E 1 , . . . , E 2 |DC| ], ∀i, j ∈ [1, 2 |DC| ], i f i < j then OCBS(E i , f , DC) ≤ OCBS(E j , f , DC)
where no E i (i ∈ 1, . . . , Z |DC| ) is repeated in orderVio(DC, f ). This index has exactly the same size than the algorithm TopINC. Example 6.5. Continuing with the previous example, we assume min as aggregate function.

In the following, we compute the OCBS for each subset of constraints:

• OCBS(∅, f , DC) = min(CBS(∅ ∩ S 1 ), CBS(∅ ∩ S 2 ), CBS(∅ ∩ S 3 )) = min(0, 0, 0) = 0 • OCBS({C 1 }, f , DC) = min(|{C 1 } ∩ S 1 |, |{C 1 } ∩ S 2 |, |{C 1 } ∩ S 3 |) = min(1, 1, 0) = 0 • OCBS({C 2 }, f , DC) = min(|{C 2 } ∩ S 1 |, |{C 2 } ∩ S 2 |, |{C 2 } ∩ S 3 |) = min(1, 0, 1) = 0 • OCBS({C 3 }, f , DC) = min(|{C 3 } ∩ S 1 |, |{C 3 } ∩ S 2 |, |{C 3 } ∩ S 3 |) = min(0, 1, 1) = 0 • OCBS({C 1 , C 2 }, f , DC) = min(|{C 1 , C 2 } ∩ S 1 |, |{C 1 , C 2 } ∩ S 2 |, |{C 1 , C 2 } ∩ S 3 |) = min(2, 1, 1) = 1 • OCBS({C 1 , C 3 }, f , DC) = min(|{C 1 , C 3 } ∩ S 1 |, |{C 1 , C 3 } ∩ S 2 |, |{C 1 , C 3 } ∩ S 3 |) = min(1, 2, 1) = 1 • OCBS({C 2 , C 3 }, f , DC) = min(|{C 2 , C 3 } ∩ S 1 |, |{C 2 , C 3 } ∩ S 2 |, |{C 2 , C 3 } ∩ S 3 |) = min(1, 1, 2) = 1 • OCBS({C 1 , C 2 , C 3 }, f , DC) = min(|{C 1 , C 2 , C 3 } ∩ S 1 |, |{C 1 , C 2 , C 3 } ∩ S 2 |, |{C 1 , C 2 , C 3 } ∩ S 3 |) = min(2, 2, 2) = 2 So orderVio(DC, min) is the following orderVio(DC, f ) = [∅, {C 1 }, {C 2 }, {C 3 }, {C 1 , C 2 }, {C 1 , C 3 }, {C 2 , C 3 }, {C 1 , C 2 , C 3 }] Algorithm RTopINC
The RTopINC takes three parameters: an integer k, a query Q(X) : -R 1 (X 1 ), . . ., R m (X m ), φ(X 1 , . . . , X m ) and an annotated instance I. This algorithm assumes the availability of the structure orderVio(DC, f ). The RTopINC algorithm is presented in algorithm 8. The RTopINC algorithm iterates on the elements in the list orderVio(DC, f ).

For each element S in orderVio(DC, f ), RTopINC looks for the set of answers that violate exactly S. The array ind(I (R)) in algorithm 8 contains the set of possible violated subsets of constraints by tuples in R. By R 1 [E 1 ] in algorithm 8, we mean all the tuples that violate exactly E 1 .

As one can easily note, the algorithm RTopINC is optimal in term of the number of tuples read on disk and in the class of semi-blind algorithms. Theorem 6.2. For any instance I and any top-k conjunctive query Q k,R f CBS , we have:

cost ∇ (RTopINC, Q, I) ≤ cost ∇ (AL, Q, I), ∀AL ∈ SBA

Conclusion

This chapter has presented preliminary results regarding the problem of inconsistency in relational database in the context of a set of inconsistent set of constraints. We have generalized the notion of consistent query answers to strong consistent query answers.

Chapter 7

Empirical Evaluation

In this chapter, we are going to show efficiency of our approach by empirically evaluate the different algorithms. First, we show the feasibility of our measures in practice with many queries in many different datasets. In the second part, we evaluate efficiency of our top-k algorithms. During all experiment, we use the following datasets. The most large of these datasets are real-world datasets, only few of these datasets are synthetic datasets. Stock, this dataset contains the market data of the United States. It mainly informs about the market trend on a time interval, i.e. the minimum price, the maximum price, the initial selling price of the interval period and the end price of the market of the same interval period. It also specifies the sales quantity of the market on the period. Hospital, registered a set of health data about admissions in many hospitals. Food, this dataset registered the set of food inspections done, mainly in New York city, in restaurants. Adult, contains data about some adult and their marital status in some countries in world (USA, India, Iran, ...). Tax, is a synthetic dataset. An other synthetic dataset, that we call synthetic is added, this dataset is randomly generated. Some complementary information about these datasets are displayed in table 7.1. In Table 7.1, the column Inc denotes the percentage of inconsistency per relation, whereas #Tup and #Rel denote the number of tuples and relations in the dataset, respectively. Finally, #Cons indicates the number of denial constraints per dataset. The column #atom gives interval of number of atoms for the constraints of a given dataset. The column Syn indicates the type of dataset (synthetic or not). All the queries used are described as follows: Q 1 to Q 5 are on the Hospital dataset and they contain one join; Q 6 to Q 9 are on the Tax dataset and they contain one join; Q 10 to Q 14 are on the synthetic dataset; Q 10 , Q 11 have a join across three tables, Q 12 , Q 13 have a join across four tables and Q 14 has a join across five tables.

We have implemented our framework in PostgreSQL 10 by leveragingPLSQL and JDK 11. All the experiments have been executed on a DELL Core i7 2.5 GHz laptop with 16 GB RAM running Linux OS.

Our approach of treatment of inconsistency degrees suppose existing of a set of denial constraints and availability of set of conjunctive queries for each dataset. So, we used Metanome [1], that is a tools allowing generation of a set of denial constraints from a dataset. Metanome implements a set of algorithm of discovery of constraints (functional dependency constraints and general denial constraints) developed by many works [START_REF] Chu | Discovering denial constraints[END_REF][START_REF] Eduardo | Discovery of approximate (and exact) denial constraints[END_REF]. Also, we use denial constraints generated by Metanome to convert into a of conjunctive queries that are used as set of conjunctive queries.

Measures Computation

In order to gauge the overhead of running a query Q with inconsistency degrees, we have employed our 14 queries and measured the overhead per each tuple in the answer (Table 7.2.a) as well as the total overhead for the complete output of the query (Table 7.2.b). The obtained results are reported in Table 7.2. The greater is the size of the output of a query the larger is the overhead of query execution with inconsistency degrees. The columns query and #answers in Table 7.2.a are the total query runtime of the original query on an inconsistency-free database instance and the size of query answer, respectively. Depending to the size of output of the queries, the overhead ranges between 2ms and 6m, respectively for queries Q 4 and Q 12 . (respectively, yellow and red cells in Table 7.2.a). The difference can be explained by looking at the size of the answer set of Q 4 and Q 1 that are 50 tuples and 15M tuples, respectively. These overhead are, however, not trustworthy to understand the overhead of our approach, since they concern the entire output set of queries, whereas our algorithms (developed in chapter 5) returns the top-k results tuple by tuple. Thus, one should look at the overhead per tuple in Table 7.2.b. We can observe that the overheads per tuple are reasonable in all cases, and range between 5 microseconds and 293 microseconds (yellow and red cells in Table 7.2.b, respectively).

Qualitative Study

We have designed an experiment devoted to show the utility of our inconsistency measures on real-world inconsistent data. We chose two real-life datasets, namely Adult, used and containing census data, along with and Food Inspection including information about inspections of food establishments in Chicago. The features of the two datasets are shown in Table 7.1 Table 7.2.b reports the constraints of Adult, namely A 1 and A 2 , that have been derived using Holoclean [START_REF] Rekatsinas | Holoclean: Holistic data repairs with probabilistic inference[END_REF]. While A 1 indicates that men who have 'married' as marital status are husbands, A 2 expresses the dual constraint for women.

A 1 :← Adult(A,MS,Re,S,. . . )∧ S='Female' ∧ Re='Husband' A 2 :← Adult(A,MS,Re,S,. . . ) ∧ S='Male' ∧ Re='Wife' A 3 :← Adult(A,MS,Re,S,. . . ) ∧ Re='Husband' ∧ MS='Marr-civ-sp.' (b) Constraints on Adult. In addition, we handcrafted a third constraint A 3 establishing that adults who are not in a family should not have 'married' as marital status. This third constraint allows to capture violated tuples that overlap with the tuples violated by the two former constraints. We also built meaningful denial constraints for the second dataset as shown in Table 7.2.c. The constraint F 1 (respectively, F 2 ) states that a licence number, which is a unique number assigned to an establishment, uniquely identifies the legal name of the establishment (respectively, its risk category). The constraint F 3 states that if a given establishment has been inspected for 'consultation' at a date d, one cannot expect to have an inspection of a different type prior to d for the same establishment. This is because the attribute Inspection type takes the value 'consultation' when the inspection "is done at the request of the owner prior to the opening of the establishment."

F 1 : ← Inspection(I 1 ,FT 1 , V 1 , Re 1 , L 1 , . . .) ∧ L 1 = L 2 ∧ Inspection(I 2 ,FT 2 , V 2 , Re 2 , L 2 , . . . ) ∧ N 1 = N 2 F 2 : ← Inspection(I 1 ,FT 1 , V 1 , R 1 , L 1 , . . . ) ∧ Inspection(I 2 ,FT 2 , V 2 , R 2 , L 2 , . . . ) ∧ L 1 = L 2 ∧ R 1 = R 2 F 3 : ← Inspection(I 1 ,FT 1 , V 1 , R 1 , L 1 , D 1 , . . . ) ∧ Inspection(I 2 ,FT 2 , V 2 , R 2 , L 2 , D 2 , . . . ) ∧ IT 1 = consultation ∧ IT 2 = consultation ∧ D 2 < D 1 (
We report in Table 7.2.d the considered queries for the two datasets. The query AQ1 on Adult finds all couples of male and female living in the same country and earning the same income. The query FQ1 on Food Inspection retrieves the licenses of establishments in a specific area that were subject to three inspections: the first one having either a failing inspection or a violation related to "food and non-food contact surface", followed by an inspection issued as a response to a complaint and then a non-failing normal inspection.

Table 7.3.a. shows the violations of constraint for the two datasets. We can notice that there are different kinds of tuples returned by AQ1 as illustrated in Table 7.3.b. The majority of the results (276M tuples) are consistent, thus both CBS and CBM are equal to 0, while the remaining answers exhibit 1 or 2 as inconsistency degrees. Most of the inconsistent tuples violate one constraint at a time (in the order A 3 , A 1 and A 2 ) while the rest of the tuples violate two constraints. For this dataset, in the majority of the cases a constraint is violated at most once and hence CBS and CBM measures are not discriminating, except for the 23 answers where violations occur twice (5th line of Table 7.3.b). These tuples are captured when running TopINC for top-100 tuples starting from the most inconsistent ones as illustrated in Table 7.3.c. Note that, while CBM does not distinguish between the 71 most inconsistent answers of AQ1 (answers with CBM = 2 corresponding to the first four rows of Table 7.3.c), the CBS measure provides a different ranking for the 23 answers of the 4th row of this Table.

We show in Table 7.3.d the inconsistency degrees of the answers when evaluating query FQ1 on the second dataset. Note that for this query the CBS degrees vary from 0 up to 3 while the CBM degrees range from 0 up to 9. We observe now that many answers are not distinguishable under CBS while they exhibit a wider range of CBM degrees (e.g., CBM varies from 1 to 3 for answers having CBS = 1). This again shows that CBS and CBM provide the user with two different types of information, both being useful to carry out the ranking.

Finally, we show by means of examples the remarkable difference between our approach and CQA 1 . Note that as we already pinpointed in chapter 4 (lemma 4.2), these are complementary approaches. Table 7.3.e shows three CQA-consistent answers for query FQ1. First, we note that all our consistent answers (i.e., with CBS = CBM = 0) are also CQA-consistent as stated in Lemma 1. The converse is not true as it can be observed in Table 7.3.e where the answer 34183 is CQA-consistent but not consistent in our framework (with CBS and CBM = 0). On another note, we can notice that the CQA approach does not distinguish between the three CQA-consistent answers of Table 7.3.e. In particular, the information that the CQA-consistent answer 34183 is computed using inconsistent base tuples (violation of F 1 ) is not conveyed by CQA.

Top-k Algorithms Evaluation

This section is dedicated to the evaluation of some algorithms of top-k developed in chapter 5.

TopINC Performance vs. Baseline.

We have implemented a baseline algorithm leveraging PostgreSQL, where all answers of a query are computed beforehand and then sorted (ORDER BY) and filtered (LIMIT k). Figure 7.3 shows the performance of TopINC (with k varying from 10 to 300) as opposed to the aforementioned baseline algorithm. We have chosen five queries as representatives of different datasets and join sizes ranging from one join (Q 1 ,Q 2 , Q 8 ) and three joins (Q 11 ) to five joins (Q 14 ). The algorithm TopINC (blue bar) can be up to 2 8 times faster than the baseline approach as shown in Figure 7.3.a. There is only one query, i.e. the most complex query Q 14 , for which TopInc has lower performance compared to the baseline, starting from a value of k ≥ 200. The reason for that is the fact that TopInc for higher values of k and higher number of joins in the query will inspect more buckets and try to perform more joins that will likely produce no answers. Furthermore, notice that in all these experiments the baseline turns to have advantageous with respect to TopInc, as it leverages the query planning of Postgres and opportunistically picks the most efficient join algorithm. Despite these advantages, our approach is still superior in terms of performance in the majority of the cases. In Figure 7.4, from 7.4.f to 7.4.j, we measure the memory consumption of our approach for the same queries. We observe that TopINC always consumes less memory than the baseline.

We also ran another experiment on synthetic datasets to study the impact of other parameters on the performance of TopINC. The results are reported in Figure 7.5.

Precisely, we wanted to study the dependency of TopINC on the following parameters: the number of answers to be returned (k), the number of violated constraints (DC), the size of search space formed by DC (i.e, the number of subsets of constraints violated by base tuples) and the exact size of output of Q (i.e, |Q(I)|).

In these results, we focused on a relatively simple query Q containing a join between two synthetic relations (of size 1000 each one) and we kept constant the value of k (equal to 20). We ran this experiment with varying number of denial constraints DC from 10 to 30, respectively in Figures 7.5.a, 7.5.b and 7.5.c. In each of these plots, we vary the selectivities of Q and the size of the search space of the algorithm. One can see that TopINC outperforms the baseline in all cases and is particularly advantageous with larger query outputs and smaller search space.. The underlying reason is that the greater is the output size of the query, the larger is the probability to find answers within the first combinations scanned within the search space.

TupIncRank Performance

In this section, we compare the TupIncRank algorithm to the naive algorithm, the baseline algorithm and the rankJoin algorithm developed in [START_REF] Ihab | Supporting top-k join queries in relational databases[END_REF], that is one of the best top join algorithms. We compare the running time of rankJoin to our TupIncRank since this last one works for monotone function TBM and TBS (in the case where the query is a free self join conjunctive query).

In this last experiment, we consider the database Rand1 that is a synthetic database. The Rand1 database is composed to four relations generated randomly. No set of denial constraints is considered in this database, so we randomly associate to each 1 or 0 as annotation (in colum incbag) to specify its inconsistency nature. As the TupIncRank algorithm, that is designed to the measures TBM and TBS, only needs to have the database annotated by 0 (consistent) or 1 (inconsistent), this nature of the database is enough. The database Rand1 contains one million of tuples, each relation contains 250000 tuples.

SO, first we compare the running time of these algorithms, then the number of tuples read from input relations by each algorithm after acclaiming the top-k algorithm and the number of additional answers computed by each algorithm outside the top-k answers. So, we consider the two following queries (QX1 and QX2). We vary the value of k from 20 to 200 with step equal to 20 between two consecutive value of k. This interval is randomly chosen, these algorithms remain with similar behavior with other values of k.

QX1(X 1 ) : -R(a, b, c, d, e, f ), T(a, c 1 , e 1 , j, f ), c < c 1 ∧ b ≥ j ∧ e <> e 1 QX2(X 2 ) : -G(d, e, f , k), S(g, h, e, j, k 1 ), ∧ f <> k With X 1 = a, b, c, d, e, f , c 1 , e 1 , j and X 2 = d, e, f , k, g, h, j, k 1 .
The queries QX1 and QX2 have 1518203018 and 11175284 answers, respectively, when evaluated over Rand1.

The figure 7.6 shows the performance of TupIncRank algorithms compared to some top-k algorithms that work with a monotonic scoring function. RANKJOIN algorithm that is one of the best top join algorithms in literature. The TupIn-cRank algorithm is best than RANKJOIN since RANKJOIN starts with a preprocessing phase that sorts first the input relations instead of the TupIncRank algorithm scans just the relation with selectivity (consistent tuples first and then inconsistent tuples). This experiment shows the non usability of the naive algorithm in practice, as one can denote the naive algorithm is not present in figure 7.6.(b) because it takes more than four days to run for ten different values of k. The running time of TupIncRank algorithm is also compared to the running time of baseline algorithm (The execution of the query in Postgresql with ORDER BY and LIMIT clauses).

The figure 7.7, we show the number of tuples read in input relations by different relations. We show that the naive algorithm reads all the input tuples before acclaiming the top-k answers. But, the RANKJOIN and TupIncRank algorithms have the same number of tuples read before acclaiming of the top-k answers. These two last algorithms read less than three thousand tuples before acclaiming of top two hundred answers instead of the naive and the baseline algorithm that read one million of tuples before acclaiming of the top-k answers.

We are also interested by the number of additional answers computed outside the top-k answers. In this direction, the figure 7.8 compares the naive algorithm, RANKJOIN algorithm and TupIncRank algorithm in term of additional computed answers. Our algorithm (TupIncRank) computes always exactly only the top-k answers without any additional answer (so, the number of additional answers is always 0) opposed to the RANKJOIN algorithm that, some times, computes some few additional answers since the maximum bound remains smaller than the bound of the last of the k first answers computed, so the RANKJOIN can not stop the running otherwise the current set of answers can be incorrect (can contain answers that are not in the top-k answers, for example the last one in this set). So, these additional answers computation is unavoidable. As the figure 7.8 shows, the naive algorithm computes more than one million answers as additional set of answers.

Conclusion

We extensively evaluated our approach. First, we empirically shown the running time of the preprocessing phase. We have noticed that this step can take more but as it is done only one time, it is reasonable. In the second part, we evaluated the overhead that measures of inconsistency can add on the queries processing time. We also done a qualitative experiment of these measures and compared our approach with CQA approach. In the last section, we confronted the performance of some of our algorithms, developed in chapter 5, to the baseline algorithm (algorithm of top-k implemented in Postgresql) and naive algorithm. Our algorithms remain the best.

In the next chapter, we are going to describe the new tool, called INCA, that enables profiling of inconsistency in whole of the database and the query answers. • Inconsistency-aware profiling of top-k and threshold queries allowing to display inconsistency degrees (according to the four aforementioned measures CBS, CBM, CSS min and CSM min ) and violation distributions of the result tuples.

These scenarios can be seamlessly applied to any data science pipeline. Whereas a swathe of data profiling and data discovery tools exist for a variety of constraints (from functional dependencies to denial constraints) as extensively documented in the literature [START_REF] Ziawasch Abedjan | Data profiling: A tutorial[END_REF], to the best of our knowledge INCA is the first system to (1) enable inconsistency-aware data profiling leveraging the constraint-based view of the violations; (2) allow inconsistency-aware top-k and threshold query execution building on the inconsistency measures. These features pave the way to clear-cut use cases, such those underpinning explainable and selective data cleaning as well as quality-driven ranking of query results.

This chapter is organized as follows: the section 8.1, we briefly describe INCA system, section 8.2 is consecrated to the description of INCA implementation and in section 8.3 we present a user case with some database described in previous chapter.

Overview of INCA

The system INCA is in a form of a web application. It is composed from many components. In the following, we describe the architecture of INCA system.

Architecture of INCA System

The INCA system architecture is depicted in figure 8.1. The system INCA comes equipped with a range of methods that enable to efficiently analyze a given dataset and collect inconsistency-based statistics and information based on the inconsistency degrees computed at the preprocessing step. We describe in the sequel the main components of INCA.

• The Preprocessing module is in charge of annotating base tuples with monomial expressions encoding the constraints violated by each base tuple.

• The Data I-Profiling (Inconsistency-based Profiling) module enables a better understanding of data inconsistencies. Based on the annotations computed at the preprocessing step, it offers a set of tools to extract and aggregate information about inconsistent data. In particular, it encompasses a dashboard which provides insights into various dimensions of data inconsistencies, e.g., percentage of consistent/inconsistent data, distribution of data values in the columns that cause constraints violations, histograms of inconsistent tuples distribution w.r.t. constraints, and so forth. This module includes an I-Explore (Inconsistency-based data exploration) tool, which can be used to identify and summarize the portion of the data causing the inconsistency.

• The Query I-Profiling module allows inconsistency-aware query processing w.r.t. the four inconsistency measures defined above. In particular, it provides the following main functionalities:

computing query answers together with their associated inconsistency degrees, This module implements the TopINC algorithm and its specific index [START_REF] Issa | Evaluating top-k queries with inconsistency degrees[END_REF].

Input

Implementation of INCA

The system INCA is implemented in JAVA. The back-end part is implemented using SpringBoot framework in an MVC structuring. The front-end is implemented in HTML, CSS and JAVASCRIPT. To describe graphically the analyze of inconsistency, we use ChartJS that is a JAVASCRIPT library to make graphical representations. As data source, we allow only Postgresql database manager. We adopt to separately develop the useful functions as service web (in back-end by SpringBoot) and the user interface (front-end). This separation allows a quick and an easy maintenance. The complete code base of INCA is available on Github1 .

User interaction with INCA

The audience will be able to use INCA to execute the following main steps:

• identifying inconsistent base tuples using why-provenance and annotating the initial database with inconsistency degrees,

• examining data inconsistencies using I-Profile and I-Explore and

• running inconsistency-aware top-k and threshold queries.

In the rest of this section, we focus on presenting the functionalities of INCA using Food Inspection, a dataset which includes information about inspections of food establishments in Chicago. The dataset Food Inspection is a long with a five meaningful denial constraints manually set up. In the following, we demonstrate step by step the diverse tools contained in INCA.

Annotating the initial database

Users can access INCA through a GUI. The first step is to connect to the Postgresql server and select one of the provided databases. The user can then select the constraints to be considered in the scenario from a list of predefined denial constraints.

The user has the possibility to update, delete or create new denial constraints. Once an input database and its associated set of constraints have been selected, the user can launch the annotation process. As a result, each tuple in the database is annotated with a monomial, which encodes the constraints violated by the tuple. For each table, the generated annotations are stored in a new column, named prov and the number of violations are stored in column violation. Each monomial is encoded as an integer whose binary representation indicates the violated constraints.

Data I-profiling

In the second step of our demonstration, users will use the Data I-profiling module to analyze the annotated data and collect statistics and information about data inconsistencies. Throughout the entire process, the users can decide to disable some constraints and perform the analysis only on the selected subset of the constraints.

Figure 8.3 depicts the GUI of the I-Exp.C tool that enables an inconsistency-based exploration by constraint. In the scenario, the user starts by selecting a constraint that will be analyzed. The «Constraints Correlation» section displays information about the correlation of the selected constraint with the other constraints in terms of proportion of common tuples that violate the two constraints.

The user is also assisted by a graphical query builder in order to build queries that show a flexible distribution of the violations and to identify values that lead to most violations w.r.t. the selected constraint.

The last Data I-Profiling functionality enables the user to explore subsets of constraints. The GUI of this module is depicted in Figure 8.4. After a user selects a subset of constraints to be analyzed, statistics about number of violations and number of constraints violated per each tuple are displayed.

Inconsistency-aware query answering

In this third step, we allow a user to explore the querying capabilities of INCA using the Query I-Profiling module. Two main classes of queries are supported by INCA:

• Top-K query, i.e. a conjunctive query that uses as parameters an integer k and an operator o ∈ {<, >} and outputs the k best answers w.r.t. the considered measure α and the operator o. In the sequel, a top-k query is denoted Q k,o,α .

• Threshold query, i.e. a conjunctive query that, given an integer s and an operator op ∈ {=, <, >, ≤, ≥}, outputs all the answers having their inconsistency degree d w.r.t. α satisfying the condition: d op s. In the sequel, a threshold query is denoted Q s,op,α . The system INCA enables to show the maximum and the minimum inconsistent degrees that the set of answers of a query can have depending to the set of measures of inconsistency degrees selected.

The GUI of the Query I-Profiling module is depicted in Figure 8.5. As input, the user provides the following parameters:

• the subset of constraints to be considered, the format of a denial constraint is as follows: constraint is composed from two parts and the parts are separated by " : ", the first part is the list of relations in the denial constraint (each one is followed by an alias) and the second part is a conjunction of built-in atoms from predicates {≤, ≥, <, >, =, =} and the set of attributes of relations in the first part and constants (example: Person t 1 , Person t 2 : t 1 .id = t 2 .id AND t 1 .name = t 2 .name that is the denial constraint ¬(Person(id, name1, . . .), Person(id, name2, . . .), name1 = name2): with one person is associated only one name);

• the input query, that is a conjunctive query in SQL format and each relation in join is associated to an alias;

• the type of query (i.e., top-K query vs. threshold query) with its associated parameters; and

• the inconsistency measure α to consider (α ∈ {CBM, CBS, CSM min , CSS min }).

For both classes of queries, the Query I-Profiling module returns the output of the query, together with the inconsistency degree associated with each answer. Additional statistical information is computed and displayed as show in Figure 8.5: distribution of answers by inconsistency level and by subset of violated constraints.

To assist users in specifying the parameter s of a threshold query Q s,op,α , INCA shows the range of possible values for s by computing the min and max inconsistency degrees of the answers of the associated conjunctive query Q. Interestingly, INCA uses the TopINC algorithm to efficiently compute the min and max bounds without computing the whole output of the associated conjunctive query Q.

The Query I-Profiling module enables also to analyze query outputs w.r.t. multiple inconsistency measures at a time. In this case, the module provides a synthetic view to summarize the collected information as illustrated in Figure 8.5 for example showing the combined analysis of CBM and CBS.

Conclusion

In this chapter, we presented the system INCA that contains a set of tools enable to characterize inconsistency. Profiling of inconsistency in whole database and query answers are done by INCA. After extensively described the system INCA, we performed a demonstration using a real dataset (food inspection) with meaningful set of denial constraints.

Chapter 9

CONCLUSION AND PERSPECTIVES

In this thesis, we have addressed the problem of inconsistency in relational databases. For this purpose, we defined a set of measures to quantify inconsistency levels of base tuple and we investigated how to propagate them to query answers. We have grounded the computation of inconsistency degrees in why-provenance annotations and polynomial provenance annotations. In addition, we have designed novel top-k algorithms suitable for the above measures while proving their optimality. These proposed algorithms are derived from a base algorithm, called TopINC. We designed experiments to evaluate empirically the performance of the TopINCalgorithm. We developed a tool (called INCA) that can be used for data profiling in the context of inconsistency database.

In the following, we give some perspectives that can be derived following the work conducted in this thesis.

• It would be interesting to extend our work to more expressive query languages as for example negation and aggregation. For example, in the case of the presence of negation in the query the connection between provenance and inconsistency degrees of base tuples remains unclear and raises intriguing research questions.

• Explore more inconsistency handling in the case where the constraints are inconsistent. One interesting research problem would be to design an efficient algorithm to handle the top-k problem for the measure R f CBM . It would also be interesting to enhance the approach proposed in this thesis so that the orderVio(DC, f ) list is eliminated or not entirely materialized. Finally, we envision to explore additional measures of inconsistency degrees, taking account the inconsistency of constraints, in the case of set semantic of query answers.

• It remains open whether it is possible to design efficient top-k algorithms, that go behind the naive algorithm for the following measures of inconsistency degrees -TBS when the query is a self-join conjunctive query -TSS min , TSS max , TSM min , TSM max , CSM min , CSM max , CSS min , CSS max without any particular condition on these measures

• From the practical point of view, it would be useful to conduct a comparative study of measures of inconsistency degrees to identify in what application context a given measure is more adequate.

• Another research direction would be to explore the properties of the proposed measures, in the spirit of [START_REF] Livshits | Properties of Inconsistency Measures for Databases[END_REF], as for example the Reliability that ensures that any measure of inconsistency gives an inconsistency value greater than zero when any tuple in the database is inconsistent.

1. 1

 1 Framework aware inconsistency in relational database . . . . . . . . . . 4.1 A hospital database hdb with a set of denial constraints (DCs) and a query Q ex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Lineage provenance databases hdb LP obtained from the hospital database hdb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 The K-instances hdb LP (without prov column) and hdb Υ (without lprov column). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 The various quantification of inconsistency that can be obtained along with their criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Answers of query Q ex over hdb Γ and their inconsistency degrees for each respective inconsistency measure. . . . . . . . . . . . . . . . . . . . . . . .List of Tables1.1 Measures with their associated top-k algorithms . . . . . . . . . . . . . . 4.1 Annotated answers of query Q ex . . . . . . . . . . . . . . . . . . . . . . . 4.2 Different proposed measures of inconsistency with their formal definitions. The notation α ≡ β means α(t, I, Q, DC) = β with α a measure of inconsistency and β its definition . . . . . . . . . . . . . . . . . . . . . . . 5.1 Algorithms with their characteristics; n is the size of the database instance, m is the size of the query and k is the number of answers to compute; δ <= n measures the number of intermediary answers (it is 1 if the query is acyclic) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Datasets used in our empirical evaluation. . . . . . . . . . . . . . . . . . . 7.2 Real-world datasets with their denial constraints. . . . . . . . . . . . . . 7.3 Results of the qualitative study. . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1

Figure 1 . 1 :

 11 Figure 1.1: Framework aware inconsistency in relational database

Example 2 . 1 .

 21 Consider the relational schema education consisting of the following relations education = {Student, Course} and the domain D is from the (infinite) set of strings. We have Attr(Student) = {Register_Number, Name, Pre f _Course} and Attr(Course) = {Course_ID, title}. An example of a database instance from education and D is Student records students with their preferred courses and the second relation (Course) records courses.

Figure 4 . 1 :

 41 Figure 4.1: A hospital database hdb with a set of denial constraints (DCs) and a query Q ex .Answers Contrib. tuples

Figure 4 .

 4 2 shows the lineage provenance database hdb LP obtained from the hospital database hdb by annotating each tuple t ∈ hdb with a singleton set {id(t)} containing the tuple identifier. The column lprov contains the annotation of each tuple.

Figure 4 . 2 :

 42 Figure 4.2: The Lineage provenance databases hdb LP obtained from the hospital database hdb

Figure 4 . 3 :

 43 Figure 4.3: The K-instances hdb LP (without prov column) and hdb Υ (without lprov column).

  Provenance polynomial of an output t: E = Q(I Υ∪Γ )(t)Constraint-based : P = Cs(E)Tuple-based : P = Tp(E)Set Seman. Bag Seman.

Figure 4 . 5 :

 45 Figure 4.5: Answers of query Q ex over hdb Γ and their inconsistency degrees for each respective inconsistency measure.

Example 5 . 3 .

 53 Consider Example 5.2 and the query Q 1

Figure 5 . 1 :

 51 Figure 5.1: Algorithms for constraint-based measures

  is defined as an ordered list of the nodes containing fragments of R, where nodes are ordered with respect to the cardinality set of their labels, i.e., B ≤ B iff |label(B)| ≤ |label(B )|.

Example 5 . 5 .

 55 The following indexes are associated with the relations D, S and V of our example database:Ind(D) = [B 0 , B 4 ], Ind(V) = [B 0 , B 6 ] and Ind(S) = [B 0 , B 1 , B 5 ].

Algorithm 1 : 2 3 / 4 level:=0 ; 5 while 6 curVSet := ∅ ; 7 IterateJoin

 1234567 TopINC Input : ViolC: set of violated constraints Q k,α : a top-k query over R 1 , . . . , R m with α ∈ {CBM, CBS} ind(R 1 ), . . . , ind(R m ) : indexes of the input relations Output: Res: k best answers w.r.t. α Data structures: HR 1 , . . . , HR m : input buffers; jB : an array of size m 1 begin Res=[] be an empty list ; * Contr. violated by current answer */ l ≤ |ViolC| ∧ Res.size < k do

Figure 5 . 2 :

 52 Figure 5.2: Illustraive example of TopINC

  be a conjunctive query, let s = |X| and let k be an integer. A query Q k,α is evaluated by the TopINC in time O(n m ) and in space O(|I | + k × s).

1 ,

 1

Figure 5 . 3 :

 53 Figure 5.3: Example of Data to illustrate top-k Memory-based algorithms (a.). Tree example (b.). Tree with data (c.)

Algorithm 4 : 5 T 6 / 7 Ans 8 / 9 Res.add(Ans); 10 nextTrees 11 for T" ∈ nextTrees do 12 Queue

 456789101112 TopMultiSet Input : Q: conjunctive query, I: annotated database instance, k: integer, Attr: set of attributes projected in Q Output: Res: k most consistent answers of Q(I) (or inconsistent) w.r.t CSM min , TSM min (or CSM max , TSM max ) 1 T := preprocess(Q, I); 2 Queue := [T]; 3 /* a priority queue, elements in Queue are ordered by their first element */ 4 while Res.size < k do := Queue.pop(); * The best tree, i.e, tree with the best first element, is removed and returned */ := enum(T ); * The next best element in T is returned */ := partition(T , Ans, Attr);

Figure 5 . 5 :

 55 Figure 5.5: Join tree with data for TopMultiSet algorithm and the preprocessing step

Lemma 5 . 10 .

 510 The algorithm TopIncSet runs O(|I | δ * k) in data complexity.

Figure 5 . 7 :

 57 Figure 5.7: Algorithms for tuple-based measures

  ) = {S ⊆ DC : S = ∅ and S |= DC and ∀S 1 , S ⊂ S 1 ⊆ DC ⇒ S 1 |= DC }

Definition 6 . 1 (Example 6 . 3 .Q 6 •

 61636 SCQA). Let DC, Q, I be a set of constraints, a query and a database instance on the same schema, respectively. The strong consistent query answers of Q, denoted SCQA(DC, Q, I), is defined as follows :SCQA(DC, Q, I) = S∈MC(DC) CQA(S, Q, I)with CQA(S, Q, I) the consistent query answers of Q (with any semantic of database repair) over I on which the set of constraints S are applied. Consider the maximal consistent set of the previous example 6.2 (S 1 , S 2 , S 3 ). Consider the following instance with the query Q. We consider the deletion repair semantic [9(z) : -R(x, y, z)The repair according to the maximal subsets {S 1 , S 2 , S 3 } are the following • For S 1 we have { 10, 9, 6 } So CQA(S 1 , Q, I) = For S 2 we have { 3, 2, 6 , 5, 7, 8 } So CQA(S 2 , Q, I) = { 6 , 8 }• For S 3 we have { 5, 7, 6 , 5, 7, 8 } So CQA(S 3 , Q, I) = { 6 , 8 } So, the strong consistent query answers of Q evaluated over I in presence of the set of constraint DC is SCQA(DC, Q, I) = { 6 }.

Example 6 . 4 . 1

 641 Based on the previous example (example6.3). The database annotated is the following I Consider the query Q 1 (x, y, z) : -R(x, y, z) and the measure of inconsistency CBS. Consider the answers t 1 = 10, 9, 6 .

Figure 7 . 1 :

 71 Figure 7.1: Transformation of an instance into a N[Υ ∪ Γ]-instance

Figure 7 . 3 :

 73 Figure 7.3: TopINC performance vs baseline (α = CBS): Runtime

Figure 7 . 4 :Figure 7 . 5 :

 7475 Figure 7.4: TopINC performance vs baseline (α = CBS): Memory footprint

Figure 7 . 7 :

 77 Figure 7.7: Performance comparison between TupIncRank and other algorithms in memory used

Figure 7 . 8 :

 78 Figure 7.8: Performance comparison between TupIncRank and other algorithms in additional computed answers

Figure 8 . 1 :

 81 Figure 8.1: Architecture of INCA computing top-k answers w.r.t. inconsistency degrees (i.e., k most or less inconsistent answers),computing query answers having an inconsistency degree below a given threshold (threshold queries).

Figure 8 .

 8 2 depicts the Simple statistics dashboard, which shows statistics on the number and proportions of violations as well as the violations per constraint or per subset of constraints. The «Proportion of violations» section of the dashboard informs the user about the percentage of inconsistent and consistent tuples, respectively, using a pie chart. The three other sections of the dashboard show the distribution of violations of constraints according to the input database. The board entitled «Distribution of violations» shows the percentage of tuples violating the same number of constraints. The board «Violation by Constraint» and «Violations by Subset of Constraints» expose the percentage of tuples violating the same constraint and the same subset of constraints, respectively.

Figure 8 . 2 :

 82 Figure 8.2: Simple statistics

Figure 8 . 3 :

 83 Figure 8.3: Inconsistency Exploration by Constraint

Figure 8 . 4 :Figure 8 . 5 :

 8485 Figure 8.4: Inconsistency exploration by subset of constraints

6 PRESENCE OF INCONSISTENCY IN SET OF CONSTRAINTS

  6.1 Fixing inconsistency problem . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Strong Consistent Query Answers (SCQA) . . . . . . . . . . . . . 6.1.2 Quantifying inconsistency degrees of query answers . . . . . . . 6.2 Query answers ranking by inconsistency degrees . . . . . . . . . . . . . . 6.2.1 Top-k algorithm with R f CBS . . . . . . . . . . . . . . . . . . . . . . 6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TopINC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 IterateJoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 TopIncMem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 TopMultiSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 partition(T , Ans, Attr) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 TupIncRank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	List of Algorithms
	1

7 performJoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 RTopINC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 1 . 1 :

 11 Measures with their associated top-k algorithms

	Measure Monotonic	Top-k algorithms
	CBM	NA, TopIncMem, TopINC
	CBS	NA, TopINC
	CSM min CSM max	NA, TopMultiSet, TopINCDE
	CSS min CSS max	NA, TopIncSet, TopINCDE
	Tuple-based measures
	TBM	NA, TupIncRank
	TBS	NA
	TSM min TSM max	NA, TopMultiSet, TopINCDE
	TSS min TSS max	NA

  w) be the query. By GYO algorithm Q is acyclic. The hypergraph H(Q) = (V, HE) where V = {x, u, x 2 , y, z, v, w} and HE = {{x, y, z}, {u, y, w}, {x 2 , v, w}}.

							u, y, w
	x	z	y	u	w	x 2 v
				H(Q)		x, y, z	The tree of Q	x 2 , v, w

Table 4 .

 4

1: Annotated answers of query Q ex

  Considering example 4.7, we have TSS max ( d2, d2 , I, Q, DC) = 3 and CSS max ( d2, d2 , I, Q, DC) = 3 since the maximal number of inconsistent tuples used is 3 (t 2 , t 3 , t 7 or t 2 , t 4 , t 7 ) and C 1 , C 2 , C3 are violated.

M∈M(C s ) Var(M) Example 4.8.

Table 4 . 2 :

 42 Different proposed measures of inconsistency with their formal definitions. The notation α ≡ β means α(t, I, Q, DC) = β with α a measure of inconsistency and β its definition • Bag semantic of query answers, in this semantics, each answer is computed in one processing manner. It corresponds to the semantics of SQL language. For this semantic, given an answer t of an union of conjunctive queries Q evaluated over an instance I in the presence of a set of denial constraints DC, Q(I Υ∪Γ )(t) is a monomial, so P is a monomial. In this case, we count one time a violation, either constraints violations or violations of base tuples. * Tuple based approach, counts the number of inconsistent tuples used to compute answer. It is called TBS and it defined as follows TBS(t, I, Q, DC) = Var(T p ) * Constraint based approach, counts the number of constraints violated by base tuples used to compute answer. It is denoted CBS. CBS(t, I, Q, DC) = Var(C s ) Constraint based approach, it counts the number of violated constraints, with repetition, by answer. It is called CBM. CBM(t, I, Q, DC) = W(C s )

		Tuple-based measures		Constraint-based measures
		Multi-occurrence	Single-occurrence	Multi-occurrence	Single-occurrence
	Set Sem.	TSM min ≡ min M∈M(T p )	W(M) TSS min ≡ min M∈M(T p )	Var(M) CSM min ≡ min M∈M(Cs)	W(M) CSS min ≡ min M∈M(Cs)	Var(M)
		TSM max ≡ max M∈M(T p )	W(M) TSS max ≡ max M∈M(T p )	Var(M) CSM max ≡ max M∈M(Cs)	W(M) CSS max ≡ max M∈M(Cs)	Var(M)
	Bag Sem.	TBM ≡ W(T p )	TBS ≡ Var(T p )	CBM ≡ W(C s )	CBS ≡ Var(C s )

Example 4.10. Considering example 4.7, we have TSM max ( d2, d2 , I, Q, DC) = 3 and CSM max ( d2, d2 , I, Q, DC) = 6 since the at most t 2 , t 3 , t 7 are used to compute answer and C 1 , C 2 , C3 are violated two time, two times, two times respectively.

-Single occurrence.

-Multiple occurrence. We count exactly the number of violations, either constraints violations or violations of base tuples. * Tuple based approach, called TBM, counts the number of inconsistent tuples (with repetition) used in computation of answer.

TBM(t, I, Q, DC) = W(T p ) *

  Definition 5.2 (Monotonic function w.r.t. aggregate operator •). Let A, B be two sets such that B is totally ordered. Let f be a function from A → B. Let x, y, z, v ∈ A and let • an intern operator in A called the aggregate scoring operator, respectively. The function f is monotonic w.r.t •, if and only if f

•

  The measure α is Order Compatible with Bottom up top-k, denoted O.C ↑ , if only if α(t, Q, I, DC) = min • α is Order Compatible with Bottom up top-k, denoted O.C ↓ , if only if α(t, Q, I, DC) = max The Order Compatible property enables to exploit algorithms of top-k designed to measures in bag semantics for the cases of set semantics. Let's denote by A = {CSS min , CSM min , TSS min , TSM min } and B = {CSS max , CSM max , TSS max , TSM m By definition we have: 1. The measures in A are O.C ↑ 2. The measures in B are O.C ↓

	S∈deriv(t,Q,I )	α(t, Q, S, DC)
	S∈deriv(t,Q,I )	α(t, Q, S, DC)

  The prov values are choosed such that they satisfy the following condition: α(π prov (t l 1 ) × π prov (t p 1 )) < min(α(π prov (t l 1 ) × π prov (t l 1 ), α(π prov (t

	π prov (t	p i ) = π prov (t	[1, l] and p tuples t j ), ∀i, j ∈ [1, p]. We take π prov (t p p 1 ) = π prov (t l 1 ).	p 1 , . . . , t	p p with
	• The relation I 1 (R 2 ) contains two subsets of tuples (the l-tuples and the p-tuples): l tuples t l 1 , . . . , t l l with π prov (t p 1 ) = π prov (t l i )∀i ∈ [1, l] and p tuples t p 1 , . . . , t p p with
	π prov (t l 1 ) = π prov (t

p i ), ∀i ∈ [1, p]. p 1 ) × π prov (t p 1

  TopIncMem illustration the first one, i.e, l 1 ≤ l 2 . Absurd. So, TopIncMem computes correctly the first answers that are the most consistent with respect to the measure of inconsistency CBS. The algorithm TopIncMem runs in a complexity O(2 |Q| * |DC| × |I| δ + k) (so, O(|I | δ + k) in data complexity) where Q is the input query, I the input database instance, DC the input set of denial constraints and δ the tree fractional width of Q, respectively. The spacial complexity is O(2 * |I| δ + k). Proof. For each R i relation in join, the index size (size of ind(R i )) is bounded by the size of the set of subsets formed from DC, so the size is 2 |DC| . To find the combinations of a given level, we have to search in the space ind(R 1 ) × . . . × ind(R m ) with m = |Q|, so if all the combinations are visited then we have visited 2 |DC| * . . . * 2 |DC| = 2 |Q| * |DC| combinations. For each combination, the algorithm filters the join tree and computes the answers corresponding to the current level, this operation can be done in |I| δ corresponding to the largest intermediary result. So the theoretical complexity is bounded by 2 |Q| * |DC| * |I| δ + k with k the set of number of answers kept (so, the data complexity is

	Lemma 5.7.

5, b, a } . . . . . .

Figure 5.4:

Queries on Adult and Food Inspection.

		c) Constraints on Food Inspection.
	AQ1:SELECT * FROM adult a1, adult a2 WHERE a1.sex = 'Male' AND a2.sex =
	'Female'AND a1.country = a2.country AND a1.income = a2.income
	FQ1:Select t2.license From inspection t1, inspection t2, inspection t3 where
	(t1.results = 'Fail' or t1.violations like '%food and non-food contact %')
	and t1.license=t2.license and t1.license=t3.license and t2.results = 'Fail'
	and t2.inspection_type = 'Canvass' and t3.inspection_type='Complaint'
	and	t1.inspection_date<t3.inspection_date	and	t3.inspection_date
	<t2.inspection_date and t1.zip >= 60666 and t2.zip > 60655 and
	t3.zip > 60655
		(d)

Table 7 . 2

 72

: Real-world datasets with their denial constraints.

  The TupIncRank algorithm remains the best no matter the query. It largely exceeds in performance the

		TopInc	Baseline		TopInc	Baseline
	Runtime (ms)	2 9 2 12 2 15 2 18	Runtime (ms)	2 7 2 9 2 11 2 13
		10 50 100 150 200 250 300 K	10 50 100 150 200 250 300 K
		(a) Q 1 TopInc	Baseline		(b) Q 11 TopInc	Baseline
	Runtime (ms)	2 9 2 12 2 15	Runtime (ms)	2 14 2 8 2 10 2 12
		10 50 100 150 200 250 300 K	10 50 100 150 200 250 300 K
		(c) Q 2	TopInc	Baseline	(d) Q 8
		Runtime (ms)	2 12 2 14
			10 50 100 150 200 250 300 K
			(e) Q 14

Table 7 . 3 :

 73 Results of the qualitative study.

i.e., ⊕ (resp. ⊗) is associative and commutative and 0 (resp. 1) is its neutral element.

Notice that there are exceptions to the last two constraints when a second shot of a vaccine is somministrated or when the immunization offered by a vaccine did not work properly. These cases would be covered by associating probabilities to the constraints, which we do not consider in our work for the time being.

This is because the optimum of the function f (x) = sxx

, for a constant s, is given by x = s/2.

We consider repair by deletion and symmetric set difference as measure of minimality[START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF].

https://github.com/oussissa123/INCA

Acknowledgements

O.SBA E-k-answers Complexity

Table 5.1: Algorithms with their characteristics; n is the size of the database instance, m is the size of the query and k is the number of answers to compute; δ <= n measures the number of intermediary answers (it is 1 if the query is acyclic)

sub-sequences of join tests with equivalent score, and we define a new metric based on the number of regions explored by the algorithm. The region-based cost enables us to get ride of lucky choices when comparing the performances of SBA algorithms. Below, we define the notion of a region. Let jPath(AL, Q, I) = [J 1 , ..., J n ]. A region of jPath(AL, Q, I) is a maximal subsequence of jPath(AL, Q, I) made of join tests with equal inconsistency degree. More formally, a sequence [J l , ..., J p ], with l ≤ p, is a region of jPath(AL, Q, I) = [J 1 , ..., J n ] iff l, p ∈ [1, n], and: (i) α(J i ) = α(J j ), ∀i, j ∈ [l, p], and (ii) α(J l-1 ) = α(J l ) and α(J p+1 ) = α(J p ). We define Regs(Al, Q, I) to be the set of regions of jPath(AL, Q, I). We define the cost model cost ∇ (Al, Q, I) as the number of regions explored by the algorithm Al during processing of query Q over I:

We call this cost model REGION-BASED COST FUNCTION. The introduced cost model cost ∇ (Al, Q, I) conveniently prevents an algorithm to compute an answer that can be dropped after to the top-k answers, thus avoiding more useless I/O operations.

In the following sections, we present the different top-k algorithms. A summary of these algorithms is depicted in table 5.1. The columns O.SBA, E-k-answers, Complexity mean that the algorithm is optimal in SBA with region-based cost function; the algorithm computes exactly k answers without computation of any additional answer; and the data complexity of the algorithm, respectively.

Algorithms for constraint-based measures

This section presents top-k algorithms for constraint-based measures. These algorithms can be divided into two classes: Memory-based algorithms and Disk-based algorithms. These algorithms and measures for which they are designed are depicted in figure 5.1.

Disk-based algorithms

An algorithm is in the class of Disk-based if it only optimizes the input/output operations on disk.

TopINC algorithm

In this section, we present our top-k ranking algorithm, called TopINC, for top-k queries under both inconsistency measures CBM and CBS. A general idea behind existing the regions sequencially in increasing order of their inconsistency degrees (i.e, starting from region of inconsistency degree 0 to upper degrees of inconsistency). Let Z be the region having the biggest inconsistency degree, noted d z , among the regions explored by AL. Two cases occur: (i) either AL has exhaustively explored all the regions with inconsistency degree < d z and in this case cost ∇ (AL, Q, I) ≥ cost ∇ (TopINC, Q, I) (because TopINC will also explore the same regions or a subset of them), or (ii) AL skips some regions with inconsistency degree < d z . In this case, one can prove that AL is incorrect. Indeed, since AL ∈ SBA, one can build an instance I ≡ prov I such that AL outputs incorrect answers when it evaluates Q k,α over I .

TopINCDE algorithm

We propose TopINCDE algorithms to evaluate top-k queries w.r.t set semantics query answers while optimizing the input/output operations on disk. The algorithm Top-INCDE is designed to work with measures CSS min , CSS max , CSM min , CSM max .

The main idea of TopINCDE is to use any top-k algorithm(called the kernel algorithm) designed in a context of bag semantics answers; then, we use this algorithm to enumerate query answers in order of their inconsistency degrees and eliminate the duplicate answers on the fly. The kernel algorithm can be TopINC algorithm or any top-k algorithm in bag semantics.

But, one needs additional conditions with measures to enable TopINCDE to compute correctly the top-k answers for these measures. This condition is about order compatibility between measure and the top-k order. In fact, if a measure is not order compatible with the top-k order needed, TopINCDE gives an incorrect set of answers. The following example(example 5.7) illustrates this scenario.

Example 5.7. Consider the following instance I already annotated with the set of denial constraints DC = {C 1 , C 2 , C 3 }:

Q(x, y) : -R(x, z), S(y, z) Consider the measure α = CSM max and the measure α 1 = CSM min . Compute the top-2 the most consistent (i.e, the bottom up top-2 ) answer of query Q considering

The algorithm TopINCDE computes the top-2 answers in this order

TopINCDE can not compute correctly the top-2 answers consistent answers with α.

Lemma 5.4. Let α be a measure of inconsistency degrees, so

Proof. Trivial. The algorithm TopINCDE takes as kernel the algorithm TopINC with eliminating of duplicate on the fly. As α is order compatible with the top-k category, when an answer, that is not yet computed, is computed then the current score is its true score and one can keep it in the top-k answers. So, when the order compatibility of a scoring function α is checked TopINCDE computes correctly the set of the top-k answers if and only if TopINC runs correctly. We shown in 5.2 that TopINC runs correctly, so Top-INCDE correctly computes the k answers when the property of order compatibility is checked.

The following theorem shows that TopINCDE visits fewer regions than any other algorithm in SBA.

Lemma 5.5. Let Q, I be a conjunctive query and an instance, respectively. For any algorithm

Proof. As TopINCDE is based on TopINC, it iterates the regions one by one based on their scores and when the k answers are found the running of the algorithm is stopped. So any other algorithm in SBA that computes the top-k answers (in set semantic of query answers) goes through at least the number of regions visited by TopINCDE -trivial-.

Then, the optimality of TopINCDE in SBA with cost ∇ as cost measure.

The main deficiency of this new algorithm (TopINCDE) is the fact that additional answers (the duplicate answers) can be computed and thrown out later.

The TopINCDE has the same time theoretical complexity than TopINC.

Memory-based algorithms

The class of Memory-based algorithms focuses on optimizing operations in main memory. Most of existing Memory-based top-k algorithms are based on monotonic function [START_REF] Ihab | A survey of top-k query processing techniques in relational database systems[END_REF]. Also, these algorithms consider only full conjunctive query. We propose, in this section, Memory-based top-k algorithms that are either based on non monotonic function or extend full conjunctive query with projection. We assume that any query in this section is an equi-conjunctive query. The algorithms in this class take advantage from efficient techniques developed to evaluate efficiently the join operation.

TopIncMem algorithm

The TopIncMem algorithm is a top-k algorithm developed to work with CBS measure. We apply the same principle as in the case of TopINC but we assume that the database is loaded in main memory. The algorithm is depicted in algorithm 3.

The algorithm TopIncMem takes as input a tree (denoted by T) corresponding to the join tree of the input conjunctive query and the input database. We associate with each node of the tree, the underling index of the relations used to build this node. As in the case of TopINC, it is denoted by buckets. The buckets represents the set of violated set of constraints by each node of the tree.

During the building of the tree, on each node is associated a map structure with keys from the set of join attribute values between the node and its parent. This map builds a local index which is used to accelerate the join. The algorithm TopIncMem is levelwise algorithm. Each level corresponding to the value of inconsistency degrees with CBS. It start by the level 0. Given a level l, Top-IncMem looks for the combinations of violated sets for each node such that the cardinality of their union corresponds to this l (done by the function bucketComb in line 4). After that, for each combination taken, the tree is filtered according to this combination (shown in line 6) and after that the Yannakakis's algorithm can be used to enumerate query answers in this filtered tree. Only query answers that violate these constraints are computed (in line 7). Proof. By absurd. Assume that there is an answer a 1 in the set answers computed using TopIncMem such that there exists an answer a 2 that is not in the set of answers returned by TopIncMemand the degrees of inconsistency of a 2 is less than that of a 1 , i.e, CBS(a 1 , Q, I, DC) = l 1 > CBS(a 2 , Q, I, DC) = l 2 . The TopIncMem algorithm explores all the combinations of violated constraints, such that the cardinality of the union of each combination gives the current level and the answers corresponding to this level are computed by filtering the join tree. As the level start from 0 to the number of constraints, it means that when an answer (as a 2 ) is not yet computed any other already computed answer by TopIncMem(as a 1 ) has an inconsistency degrees less than that of for a full conjunctive query (or in a context of bag semantics of query answers), at each step we separate the problem into m(with m the size of Q) other join trees and these join trees are sorted according to their first best element in a priority queue as the line 10 of algorithm TopMultiSet shows. Then, in the next round, the best tree (the tree that has the answer of Q with the best score) is popped (in line 6) from Queue and its first element is returned as shown in line 8 of algorithm TopMultiSet. Using dynamic programming techniques [START_REF] Tziavelis | Optimal join algorithms meet top-k[END_REF], the function Partition allows to separate the problem into at most m other problems. This separation enables to avoid computation of duplicate answers. Consider VarPro the set of variable in projection; let T be the array of nodes of the tree and let m 1 = |T|; let dropDup(t, var, no) be a function that removes all the tuples, which have projection value on variable var equal to t, from the node no; consider keepLast(t, var, no) a function that keeps only the tuples, which have projection value on variable var equal to t, from the node no. Assume that the current answer computed is t. The function Partition works as follows: convert T into m 1 other arrays of nodes(that are other trees); the i th tree, denoted T i , is:

In the following example, we illustrate the algorithm TopMultiSet.

Example 5.9. Consider the following instance.

• R 1 = { a, 1 : 1, a, 2 : 1, a, 3 : 2}

a.

b1. (for R 1 )

c.

Add in topK k -topK.size answers from Q({S 1 , . . . , S rel-1 , {tup}, S rel+1 , . . . , HR m }) ; rel := ((rel + 1)%(rels.size + 1)) + 1;

Measures Evaluation

This section evaluate our measures, we evaluate the running time of the annotation phase, the running time to compute each measure and a qualitative study.

Database Annotation

This preprocessing of data can take more running time. It is done once, only when there are some update in database. The approach that consists to do that once is interesting in the case of data warehouse. Because, in data warehouse, there are less updates. So, in the following, we evaluate our approach, begin with the conversion of the set of denial constraints into conjunctive, the evaluation of these converted denial constraints to compute the why-provenance until the annotation phase of each tuple in the database. Before annotation four columns, vioset, viobag, inc and incbag containing the set of violated constraints in binary format for set answers semantics measures with constraint-based approach, the number of violated constraints for bag semantics answers with constraint-based approach, a monomial (either 1 or identifier of the tuple) for set semantics answers and tuple-base approach and 1 either 0 for bag semantics answers and tuple-based approach, respectively, are added on each relation. Once, the why-provenances of each obtained conjunctive query is computed, each tuple in the instance is annotated through its four columns. This empirical evaluation is done only for STOCK, HOSPITAL, TAX, SYNTHETIC data since these databases contain more large set of denial constraints. Figure 7.1 shows the runtimes for each dataset while varying the number of constraints. We can observe that the runtimes of the K-instance transformation linearly scale with the number of constraints for all datasets. They range between tens and thousands of seconds, depending on the dataset. We observed the highest runtimes only with one dataset (Tax), which has fifty denial constraints and took approximately 1h to transform 100000 tuples. Such a transformation is part of the pre-processing and only done one time for the annotated instances, thus it remains quite reasonable.

One can also notice that there is a huge gap between runtimes of transformation of Tax (Figure 7.1.a) and Hospital (Figure 7.1.b) despite the fact that these two datasets have similar characteristics. The observed gap is due to the fact that the constraints in the dataset Tax are more sophisticated than the constraints in the dataset Hospital (i.e., with larger built-in atoms). As quantifying the level of inconsistency of base tuples is crucial for numerous data curation, data science and machine learning tasks, so it is useful to have a tool allowing to manage inconsistency by quantifying its degrees. INCA quantifies inconsistency of database tuples and queries answers tuples. It makes also profiling of inconsistency in database and in queries answers. Based on our knowledge, there is no tool that allows to make profiling of inconsistency. Whereas cleaning is a prominent step of data preprocessing workflows, it might be difficult to choose the repairing parameters and values in all cases, especially when applying updates to the underlying data [START_REF] Arioua | User-guided repairing of inconsistent knowledge bases[END_REF]152] or when the underlying data is sensitive or cannot be modified in situ. It is often the case in real-world applications involving data science workflows in which domain-specific data needs to be assessed from a quality viewpoint.

In particular, in INCA, we first leverage why-provenance [START_REF] Buneman | Why and where: A characterization of data provenance[END_REF] in order to identify the inconsistent base tuples of a relational instance with respect to a set of DCs. Then, we rely on provenance polynomials [START_REF] Green | Provenance semirings[END_REF] in order to propagate the annotations of inconsistencies from the base tuples to the answer tuples of Conjunctive Queries (CQs). Ultimately, these annotations can be used in conjunction with data cleaning steps to provide explainable results enriched with provenance-based information about inconsistency. Building upon the computed annotations, we use (choose) four measures of inconsistency degrees, which consider single and multiple violations of constraints both in the context of bag answers semantics (CBS and CBM measures) [START_REF] Issa | Evaluating top-k queries with inconsistency degrees[END_REF], and set answers semantics (CSS min and CSM min measures). The system INCA implements TopINC that efficiently execute top-k and threshold queries on top of the annotated data, respectively aiming at computing the top-k most (in-)consistent results and the results satisfying an inconsistency threshold. With this tool, we engage the user in the following scenarios with INCA:

• Precise statistics of the number and proportions of violations as well as the violations per constraint or per subset of constraints in a given database.

• Inconsistency-aware profiling of the underlying data encompassing inconsistencyaware data exploration by constraint and set of constraints.

• Value grouping allows to show a flexible distribution of the violations and to identify values that lead to most violations.