=Paper= {{Paper |id=Vol-3340/64 |storemode=property |title=Coverage-based Queries: Nondiscrimination Awareness in Data Transformation |pdfUrl=https://ceur-ws.org/Vol-3340/paper64.pdf |volume=Vol-3340 |authors=Chiara Accinelli,Barbara Catania,Giovanna Guerrini |dblpUrl=https://dblp.org/rec/conf/itadata/AccinelliCG22 }} ==Coverage-based Queries: Nondiscrimination Awareness in Data Transformation== https://ceur-ws.org/Vol-3340/paper64.pdf

Coverage-based Queries: Nondiscrimination
Awareness in Data Transformation
Chiara Accinelli∗ , Barbara Catania and Giovanna Guerrini
University of Genoa, Italy

Abstract
When people-related data are used in automated decision making processes, social inequities can be
amplified. Thus, the development of technological solutions satisfying nondiscrimination requirements,
in terms of, e.g., fairness, diversity, and coverage, is currently one of the main challenges for the data
management and data analytics communities. In particular, coverage constraints guarantee that a dataset
includes enough items for each (protected) category of interest, thus increasing diversity with the aim
of limiting the introduction of bias during the next analytical steps. While coverage constraints have
been mainly used for designing data repair solutions, in our study we investigate their effects on data
processing pipelines, with a special reference to data transformation. To this aim, we first introduce
coverage-based queries as a means for ensuring coverage constraint satisfaction on a selection-based
query result, through rewriting. We then present two approximate algorithms for coverage-based query
processing: the first, covRew , initially introduced in [3], relies on data discretization and sampling;
the second, covKnn is a novel contribution and relies on a nearest neighbour approach for coverage-
based query processing. The algorithms are experimentally compared with respect to efficiency and
effectiveness, on a real dataset.

Keywords
nondiscrimination, data transformation, coverage, rewriting

1. Introduction
Today, we are surrounded by information that is increasingly being used to make decisions that
could have an impact on people’s lives. It is therefore very important to understand the nature
of this social impact and take responsibility for it. To this aim, the development of responsible
and nondiscrimination-aware technological solutions is one of the main challenges in data
management and analytics and the satisfaction of ethical requirements is becoming a crucial
element for asserting the quality of a dataset [9]. More precisely, nondiscrimination-aware data
decision systems should take humans in the loop in all the data processing steps, from acquisition
to wrangling and analysis: from one hand, they must ensure transparency and interpretability,
for tracing the whole process; from the other, they should guarantee nondiscrimination with
respect to protected groups of individuals. This is achieved by characterizing groups of interests
in terms of sensitive attributes, like, e.g., gender or economical status, and relying on the

ITADATA2022: The 1𝑠𝑡 Italian Conference on Big Data and Data Science, September 20–21, 2022, Milan, Italy
∗
Corresponding author.
Envelope-Open chiara.accinelli@dibris.unige.it (C. Accinelli); barbara.catania@dibris.unige.it (B. Catania);
giovanna.guerrini@dibris.unige.it (G. Guerrini)
Orcid 0000-0002-6626-9470 (C. Accinelli); 0000-0002-6443-169X (B. Catania); 0000-0001-9125-9867 (G. Guerrini)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
specification of properties, like fairness, i.e., lack of bias [14], diversity, i.e., the degree to which
different kinds of objects are represented in a dataset [8], and coverage [4], guaranteeing a
sufficient representation of any category of interest in a dataset.
A significant ongoing research effort [8, 18] aims at a holistic treatment of nondiscrimination
along the stages of the data processing life-cycle, rather than as a constraint on the final result:
the sooner you spot the problem fewer problems you will get in the last analytical steps of the
chain. Approaches have been proposed both with reference to front-end (e.g., OLAP queries [13],
set selection [19], ranking [21]) and back-end stages (e.g, dataset repair during data acquisition,
with a special focus on coverage in [4, 5, 12] and causal fairness [15]). We refer the reader to
[7] for a short survey.
In our work, we are interested in nondiscrimination constraints defined in terms of coverage.
Indeed, it is well known that the quality of a classifier depends not only on the used algorithm
but also on the number of instances, i.e., the coverage, of each group in the dataset [16]. While
coverage constraints have been mainly used for repairing raw datasets before any transformation
[4, 5, 12], we investigate their effects on the data processing pipeline, with a special reference
to data transformed through query execution.

Example 1. Consider the StudentPerformance dataset1 and suppose we want to predict who,
among the best students, has parents with a high level of education (e.g. from graduation upwards),
through a classification task. The information about the lunch at school allows us to deduce
information about the economical status of the student family, thus lunch can be taken as sensitive
attribute. Suppose we would like to train a model which accuracy does not deeply depend on the
economical status of the student family, assuming that the lower the accuracy difference between the
considered student groups the lower the model discriminates against them. Now suppose to qualify
the best students with two selection conditions over math and reading subjects: math_score ≥ 80
AND reading_score ≥ 80 . This query returns just 13 students with free/reduced lunch out of
143 individuals. When training a Random Forest classifier on the query result, we get a model with
an accuracy equal to 0.71 and an accuracy difference equal to 0.28 (accuracy for standard lunch
= 0.78, accuracy for reduced lunch = 0.5). Thus, the insufficient number of students with reduced
lunch in the query result affects the accuracy difference of the model. Now suppose to modify
the initial query with the following one: math_score ≥ 71 AND reading_score ≥ 68 . This
query returns 74 free/reduced instances out of 350 individuals. The accuracy of the classification
model trained on this new result slightly changes (0.69) but the accuracy difference is improved
and corresponds to 0.006. The improvement is due to the higher number, i.e., the higher coverage, of
protected instances in the query result. The price to pay is a relaxation of the original query. ♦

In this paper, we present the main results we achieved for ensuring coverage constraint
satisfaction during data transformation represented in terms of selection-based queries. In order
to avoid disparate treatment discrimination [6], and similarly to what has been done in [13] for
OLAP queries and causal fairness and, more recently, in [17] for range queries and different types
of associational fairness, the input selection-based query, when executed over a given dataset
𝐼, is modified through rewriting, obtaining a new query that, when executed over 𝐼, satisfies
the given constraints and is still close to the initial request. As far as we know and according
1
It is available at https://www.kaggle.com/spscientist/students-performance-in-exams.
to [16], no other solutions addressing coverage-based rewriting have been proposed so far. More
precisely, we first introduce coverage-based queries as a means for ensuring coverage constraint
satisfaction in selection-based query results. We then present two approximate algorithms for
coverage-based query processing: the first, covRew , initially introduced in [3], relies on data
discretization and sampling; the second, covKnn , presented here for the first time, relies on a
nearest neighbour approach for coverage-based query processing. The approaches are then
experimentally compared with respect to efficiency and effectiveness, on a real dataset.
The remainder of this paper is organized as follows. Section 2 presents preliminary definitions
and the reference problem. covRew is briefly described in Section 3 while Section 4 presents
covKnn , an alternative nearest neighbour approximate approach for coverage-based query
processing. Experimental results are presented in Section 5. Finally, Section 6 discusses related
work and Section 7 concludes and outlines future work directions.

2. Problem Definition
Dataset. We assume data are represented as a collection of tabular datasets (e.g., relations in
a relational database, data frames in the Pandas analytical environment, called tables in the
following) 𝐼 ≡ {𝐼1 , ..., 𝐼𝑟 }, with disjoint schemas, for the sake of simplicity. Let 𝐴1 , ..., 𝐴𝑚 be the
attributes of 𝐼, 𝐷𝐴𝑗 denote the domain of 𝐴𝑗 . A set of discrete-valued attributes 𝒮 = {𝑆1 , ..., 𝑆𝑛 }
are of particular concern since they allow the identification of protected groups and are called
sensitive attributes. Examples of sensitive attributes are gender and race .
Data transformation operations. We focus on selection-based data transformations (or
queries) over stored or computed datasets, in data processing pipelines that might alter the
representation (i.e., the coverage) of specific groups of interests, defined in terms of sensitive
attribute values. Examples are data slicing operations in Pandas2 or ColumnTransformers in
Scikit-Learn3 . We consider boolean combinations of atomic selection conditions 𝑠𝑒𝑙𝑖 ≡ 𝐴𝑖 𝜃𝑣𝑖 ,
𝑣𝑖 ∈ 𝐷𝐴𝑖 , 𝜃 ∈ {<, ≤, >, ≥}, 𝐴𝑖 numeric attribute,4 𝑖 = 1, … , 𝑑, 𝐴𝑖 ∉ 𝒮. A selection-based query 𝑄 is
thus denoted by 𝑄⟨𝑣1 , ..., 𝑣𝑑 ⟩ or 𝑄⟨𝑣⟩, 𝑣 ≡ (𝑣1 , ..., 𝑣𝑑 ). Attributes 𝐴1 , ..., 𝐴𝑑 are called dimensions of
the selection-based query.
Coverage constraints. Conditions over the number of entries belonging to a given protected
group of interest returned by the execution of a selection-based query can be specified in terms
𝑆𝑙 ,...,𝑆𝑙
of coverage constraints [4, 12]. A coverage constraint 𝐶 has the form ↓𝑠𝑙11,...,𝑠𝑙ℎℎ ≥ 𝑘 and specifies
that the minimum number of instances with sensitive attribute 𝑆𝑙𝑖 equal to 𝑠𝑙𝑖 , 𝑖 = 1, ..., ℎ, in a
gender
query result has to be 𝑘. As an example, ↓female ≥ 10 specifies that a query result should include
at least 10 female individuals. The group a coverage constraint refers to is called protected group
and is characterized by the selection condition 𝑃𝐺 ≡ 𝑆𝑙1 = 𝑠𝑙1 ∧ ... ∧ 𝑆𝑙ℎ = 𝑠𝑙ℎ . Even if coverage
thresholds are usually application specific and should be determined through statistical analysis,
the central limit theorem suggests that the number of representative should be around 30 and,
according to [20], at least 20 to 50 instances for each group are required.
2
https://pandas.pydata.org/pandas-docs/stable/getting_started/intro_tutorials/03_subset_data.html
3
https://scikit-learn.org/stable/modules/generated/sklearn.compose.ColumnTransformer.html
4
For the sake of simplicity, selection attributes are assumed numeric. The approach can be easily extended to deal
with any other ordered domain.
(a) Input and induced queries (b) Skyline points

Figure 1: Coverage-based query properties

Definition of coverage-based queries. Let 𝐶 be a set of coverage constraints over a set of
sensitive attributes 𝑆 and let 𝑄⟨𝑣⟩ be a selection-based query. A coverage-based query 𝜉𝑄𝐶 for
𝐶 and 𝑄 is a selection-based query that, given a dataset 𝐼, stretches the result 𝑄(𝐼 ) as little as
possible so that constraints in 𝐶 are satisfied. More precisely, for each dataset 𝐼: (i) a tuple 𝑢
exists such that 𝜉𝑄𝐶 (𝐼 ) = 𝑄⟨𝑢⟩(𝐼 ); (ii) 𝑄 ⊆ 𝜉𝑄𝐶 ; (iii) all coverage constraints are satisfied by 𝜉𝑄𝐶 (𝐼 );
(iv) 𝜉𝑄𝐶 is the closest query to 𝑄 in terms of minimality, i.e., result cardinality, and proximity,
i.e., syntactic closeness. Minimality means that no other query 𝑄 ′ satisfying conditions (i)–(iii)
exists such that 𝑐𝑎𝑟𝑑(𝑄 ′ (𝐼 )) < 𝑐𝑎𝑟𝑑(𝜉𝑄𝐶 (𝐼 )); proximity means that 𝑄⟨𝑢⟩ is the closest query to
𝑄⟨𝑣⟩, according to the Euclidean distance (defined in a unit space) between 𝑣 and 𝑢, satisfying
properties (i)–(iv).
Properties. It has been proved that a coverage-based query 𝜉𝑄𝐶 satisfies the following properties:

(P1) It can be represented in a canonical form in which each selection condition has the form
𝐴𝑖 ≤ 𝑣𝑖 or 𝐴𝑖 < 𝑣𝑖 ; 𝑄⟨𝑢⟩ can thus be represented as point 𝑢 in the 𝑑-dimensional space
defined by selection attributes (see 𝑄 in Figure 1(a)).
(P2) Let 𝜉𝑄𝐶 (𝐼 ) ≡ 𝑄⟨𝑢⟩(𝐼 ). It can be proved that 𝑢 coincides with the upper right vertex of the
minimum bounding box of at most 𝑑 distinct points in 𝐼, 𝑄, and the origin of the space
(see the green triangle in Figure 1(a)). Such vertices are called induced points and the set
of all induced points corresponds to the search space for coverage-based queries.
(P3) There is a relationship between 𝑢 and the skyline of induced points corresponding to
queries that, when executed over 𝐼, satisfy 𝐶. The dominance relation, needed for the
skyline computation, is defined over selection attributes, assuming the lower the better
(see Figure 1(b)). It can be proved that 𝑢 coincides with the skyline point corresponding
to the query with the minimal cardinality at the lowest distance from 𝑄.

The problem. The problem we address concerns the design of efficient algorithms for processing
𝜉𝑄𝐶 . The designed algorithms improve the naïf approach derived from properties P1, P2, and P3,
which is inherently inefficient due to the size of the search space and the skyline computation.
We do not rely on any index data structure, so that both stored and computed datasets can be
considered. The proposed approximate algorithms are briefly described in the next sections
while an optimized precise one is currently under evaluation.
(a) Data distribution (b) Multi-dimensional grid (c) Cardinality estimates and so-
lution

Figure 2: Data representation and processing

3. Approximate Coverage-based Query Processing through
Discretization and Sampling
In order to improve the efficiency of the naïf approach, the approach proposed in [1, 2, 3]
relies on a discretized search space instead of generating and visiting the whole set of induced
points. Additionally, cardinality estimation, needed for constraint and minimality checking, is
performed through a sample-based approach. The proposed technique, called covRew , can be
applied over any dataset for which a sample is available or can be easily computed on the fly,
and relies on two main steps:

• Pre-processing. The approximate search space is generated by considering the intersec-
tion points of a grid obtained by discretizing each axis (one for each selection attribute 𝐴𝑖
in 𝑄⟨𝑣⟩, from the query value 𝑣𝑖 to the maximum value of 𝐴𝑖 in 𝐼), using standard binning
approaches (e.g., equi-width and equi-depth). Each point on the grid corresponds to a
selection-based query of type 𝑄⟨𝑎⟩, thus satisfying conditions (i) and (ii) of the reference
problem.
• Processing. Given 𝐼, 𝑄⟨𝑢⟩ such that 𝜉𝑄𝐶 (𝐼 ) = 𝑄⟨𝑢⟩(𝐼 ) is then computed by visiting the
discretized search space starting from 𝑣, one point after the other, at increasing distance
from 𝑣, checking minimality and proximity in the approximated space. The properties
of the discretized search space and the canonical form are considered for pruning the
space (algorithm covRewP in [2]), possibly increasing the number of points to be visited
at different iterations (algorithms covRewI and covRewIP in [2], depending on whether
pruning is considered together with iterations). The trade-off between accuracy and
efficiency of the proposed algorithms has been evaluated on both synthetic and real-world
datasets (see [2] for details).

Example 2. Consider the scenario introduced in Example 1. 𝑄 can be rewrit-
ten in canonical form as -math_score ≤ -80 AND -reading_score ≤ -80 .
Figure 2(a) shows the dataset projected over attributes -math_score and
-reading_score . Points are colored and shaped according to the sensitive attribute val-
ues: red crosses for free/reduced lunches and black dots for standard lunches. The result of 𝑄
in canonical form corresponds to the region at the bottom left side of the query point (-80,-80). The
space to be discretized corresponds to the green rectangle. By applying the equi-depth approach to
each axis with 4 bins, we obtain the grid in Figure 2(b). The discretized search space corresponds to
the grid intersection points: each point represents a selection-based query containing 𝑄. During the
processing step, the points of the grid are visited, under different strategies, starting from (-80, -80),
at increasing distance from it (blue numbers represent the visiting order). For each visited point
𝑄⟨𝑎⟩, we estimate the cardinality of 𝜎𝑙𝑢𝑛𝑐ℎ=𝑓 𝑟𝑒𝑒/𝑟𝑒𝑑𝑢𝑐𝑒𝑑 (𝑄⟨𝑎⟩)(𝐼 ), needed for checking constraint
satisfaction, and of 𝑄⟨𝑎⟩(𝐼 ), by relying on a sample-based approach (see the pairs of numbers
associated with each point in Figure 2(c)). The result corresponds to point 𝑢 =(-71,-65) (see Figure
2(c)): it satisfies the coverage constraint (𝜎𝑙𝑢𝑛𝑐ℎ=𝑓 𝑟𝑒𝑒/𝑟𝑒𝑑𝑢𝑐𝑒𝑑 (𝑄⟨𝑎⟩)(𝐼 ) = 79, property (iii)), has the
minimum cardinality (370), at the lowest distance from 𝑄 (property (iv)). Distances are computed
in the reference unit space (normalized values are shown in red in Figure 2(c)). Query 𝑄 is thus
rewritten into -math_score ≤ -71 AND -reading_score ≤ -65 . ♦

The number of cardinality estimations in covRew is in 𝑂(𝑛𝑑 ), where 𝑛 is the number of bins
used for the discretization of the axis and 𝑑 is the number of selection conditions. As shown
in [2], pruning strategies help in reducing such exponential complexity in real cases. On the
other hand, thanks to the sample-based approach, covRew performance does not depend on the
dataset cardinality.

4. A Nearest Neighbour Approach to Approximate
Coverage-based Query Processing
Similarly to the naïf approach derived from properties P1, P2, and P3 in Section 2, covRew works
in a space of query points to identify an approximation of 𝑄⟨𝑢⟩, needed to process the coverage-
based query 𝜉𝑄𝐶 (𝐼 ). An alternative approach could be that of computing an approximation of
𝑄⟨𝑢⟩ directly from the data instances. To this aim, we first look for the missing number of
protected group instances closest to the query point, with respect to an input distance function
𝑓, and then use them to compute the induced query representing an approximation of 𝑄⟨𝑢⟩.
𝑆𝑙 ,...,𝑆𝑙
More precisely, given one coverage constraint 𝐶 ≡↓𝑠𝑙11,...,𝑠𝑙ℎℎ ≥ 𝑘, a selection-based query 𝑄⟨𝑣⟩, and
a dataset 𝐼, the proposed approach, called covKnn , relies on four main steps:5
1. compute the set of protected group instances that are not included in 𝑄(𝐼 ), corresponding
to 𝑆𝑃𝐺 ≡ 𝜎𝑃𝐺 (𝐼 − 𝑄(𝐼 ));
2. determine the number of missing protected instances ℎ = 𝑘 − 𝑐𝑎𝑟𝑑(𝜎𝑃𝐺 (𝑄(𝐼 )));
3. identify the ℎ nearest neighbours to 𝑣, with respect to 𝑓, in 𝑆𝑃𝐺 ;
4. return the query induced by the ℎ nearest neighbours as an approximation of 𝑄⟨𝑢⟩.
It is easy to show that covKnn guarantees the satisfaction of properties (i)-(iii) of coverage-
based queries; however, minimality and proximity (property (iv)) are not necessarily satisfied by
the induced query even if they are implicitly taken into account during the nearest neighbour
computation.
5
covKnn can be easily extended to deal with a set of constraints by considering the query induced by the union of
the ℎ𝑖 missing instances for each coverage constraint 𝐶𝑖 in the input set.
One additional consideration is needed for the distance function to be used. As observed
in [11], those based on the general theory of vector p-norms, like the Euclidean or Manhattan
distances, are distances between points. They are therefore not suitable when considering
distances from boxes corresponding to a query space, as in our case, since it is not obvious
which point inside the box should be treated as the reference point. In such a context, the user
would usually prefer answers that are close to the periphery of the box. The box query distance
proposed in [11] achieves this goal. Given an input query 𝑄⟨𝑣⟩ and a database instance point 𝑎
that does not belong to 𝑄(𝐼 ), when considering selection-based queries in canonical form, it is
computed as follows:
√
√
√ 𝑑
√
√ 𝑎 − 𝑣𝑖 if 𝑎𝑖 > 𝑣𝑖
√∑(𝑑𝑖 (𝑣𝑖 , 𝑎𝑖 ))2
√ where 𝑑𝑖 (𝑣𝑖 , 𝑎𝑖 ) = { 𝑖 (1)
0 otherwise.
√ 𝑖
The box query distance can be customized to user needs by using weights. In our case, the
idea is to use weights that make the distance of a point 𝑎 to each query axis closer to the area
corresponding to the contribution of 𝑎 to the induced query, for that axis. To this aim, we use
the Inverse Aspect-Ratio weights presented in [11].

Example 3. Consider the scenario introduced in Example 1. Under covKnn , the processing proceeds
in this way: (i) the search space 𝑆𝑃𝐺 is first computed (see the white space in Figure 3(a)): it contains
342 points out of the 1000 points of the whole dataset; (ii) assuming that 𝑄(𝐼 ) contains 13 protected
group instances, the number of missing instances is determined as ℎ = 70-13 = 57; (iii) the 57 nearest
neighbour points to the query point (-80, -80) in 𝑆𝑃𝐺 are computed, using the box query distance
(green points in Figure 3(a)); (iv) the induced query of the detected points is then computed (see
Figure 3(b)): it corresponds to the query -math_score ≤ -70 AND -reading_score ≤ -69 . ♦

In covKnn , no cardinality estimate is required (minimality is not checked and the coverage
constraint is satisfied by the induced query by construction). The complexity is 𝑂(𝑚𝑑), where
𝑚 is the cardinality of 𝑆𝑃𝐺 since, for each instance in 𝑆𝑃𝐺 , the distance from 𝑄 is computed
according to Eq. (1). As a final remark, we notice that the obtained result is different from the
one obtained with covRew (see Example 2): they represent two possible and potentially distinct
approximations of the coverage-based query result.

5. Experimental Evaluation
5.1. Experimental setup
All experiments were conducted on a machine with an Intel(R) Core(TM) i99900K 3.60GHz CPU
and 16GB main memory, running Ubuntu 20.04. All programs were coded in Python 3.8 and
the dataset is stored on PostgreSQL 9.6.19.1.
Dataset. The experiments refer to the Adult dataset,6 exploited for assessing many non-
discrimination data management techniques. It contains 48,842 individuals, described by six
6
https://archive.ics.uci.edu/ml/datasets/Adult
(a) Query nearest neighbour points (b) Induced query

Figure 3: Query nearest neighbours and the corresponding induced query

numerical attributes and eight categorical attributes. For our experiments, we use attributes
sex , race , and marital_status as sensitive attributes.
Queries and coverage constraints. We identified 9 selection-based queries 𝑄𝑖,𝑗 with a variable
number 𝑑 of selection conditions and selectivity %sel (see Table 1): 𝑖 corresponds to the number
of selection conditions and 𝑗 points out the selectivity (ℎ corresponds to %sel ≤ 15%, 𝑚 to 15% <
%sel < 40%, and 𝑙 to %sel ≥ 40%). We then considered many problem instances by combining
the selection-based queries with various coverage constraints, requiring a different number of
protected group instances. Table 2 presents the considered instances pointing out the cardinality
of the initial query result 𝑐𝑎𝑟𝑑(𝑄(𝐴𝑑𝑢𝑙𝑡)), the cardinality of each protected group in the initial
query result 𝑐𝑎𝑟𝑑(𝑄 ↓𝐶𝑖 (𝐴𝑑𝑢𝑙𝑡)), the missing number of protected group instances, according
to the selected coverage constraint, and the cardinality of 𝑆𝑃𝐺 (#space).
Algorithms. The experiments compare covKnn and covRewIP ; the precise algorithm derived
from the properties presented in Section 2 is used as a baseline. covRewIP is the grid-based
algorithm guaranteeing the best tradeoff between accuracy and efficiency according to [2],
executed using the equi-depth discretization, with 32 bins, applied over a random sample of size
9,604 of the 𝐴𝑑𝑢𝑙𝑡 dataset. In the covKnn implementation, we rely on a naïf top-sort approach,
in which we keep in a buffer the best 𝑘 points seen so far, for nearest neighbour computation.7
Distance function. We performed many experiments, considering many different weights
for the box query distance proposed in [11]. The reported experimental results refer to the box
query distance with squared Inverse Aspect-Ratio weights (see [11] for details).
Efficiency and effectiveness indicators. Efficiency is analyzed in terms of execution time for
determining the new query to be executed (averaged over 10 executions). For better pointing out
the impact of the dataset size, we include the time to load the dataset for covKnn (0.19 s) and to
generate and load the sample for covRewIP (0.071 s).8 Effectiveness is evaluated by comparing:
(i) the achieved semantic relaxation, called relaxation degree in [2], as the rate between the
cardinality of 𝜉𝑄𝐶 (𝐴𝑑𝑢𝑙𝑡) − 𝑄(𝐴𝑑𝑢𝑙𝑡) (i.e, the number of new tuples returned) and of 𝑄(𝐴𝑑𝑢𝑙𝑡);
(ii) the syntactical relaxation, i.e., the proximity of 𝑄⟨𝑢⟩ with respect to the initial query 𝑄⟨𝑣⟩.
The baseline approach is used only for the analysis of the accuracy since experiments, that are

7
Notice that, since the box query distance is not a metric function and since, in general, the dataset might not be
stored, we cannot rely on usual data structures, like k-d trees.
8
The time for computing the query result is not included since it is equal for both the approaches.
Table 1
Selected queries
IdQ Query d %sel
𝑄2,ℎ age ≤ 46 AND education_num ≥ 14 2 5%
𝑄2,𝑚 hours_per_week ≥ 41 AND age ≥ 38 2 16%
𝑄2,𝑙 education_num ≤ 11 AND hours_per_week ≤ 40 2 54%
𝑄3,ℎ education_num ≥ 13 AND age ≤ 34 AND hours_per_week ≤ 40 3 5%
𝑄3,𝑚 age ≤ 54 AND education_num ≥ 13 AND capital_gain ≤ 3000 3 20%
𝑄3,𝑙 age ≤ 39 AND hours_per_week ≤ 40 AND capital_loss ≤ 2500 3 40%
𝑄4,ℎ age ≤ 34 AND education_num ≥ 13 AND hours_per_week ≤ 40 AND capital_loss ≤ 1400 4 5%
𝑄4,𝑚 capital_gain ≤ 1500 AND age ≤ 34 AND capital_loss ≤ 500 AND hours_per_week ≥ 38 4 28%
𝑄4,𝑙 education_num ≤ 13 AND hours_per_week ≥ 32 AND capital_gain ≤ 450 AND age ≤ 49 4 57%

Table 2
Problem instances
IdI IdQ C 𝑐𝑎𝑟𝑑(𝑄(𝐼 )) 𝑐𝑎𝑟𝑑(𝑄 ↓𝐶𝑖 (𝐼 )) #space
[#added]
I1 𝑄2,ℎ ↓sex
female ≥ 780 2,447 730 [50] 15,462
I2 𝑄2,𝑚 ↓sex
female ≥ 1450 7,962 1387 [63] 14,805
,marital _status
I3 𝑄2,𝑚 ↓sex
female ,married −civ −spouse ≥ 280 7,962 249 [31] 2,231
_status
I4 𝑄2,𝑚 ↓marital
married −civ −spouse ≥ 5700 7,962 5,545 [155] 16,834
sex
I5 𝑄2,𝑙 ↓female ≥ 10, 600 26,504 10,525 [75] 5,667
I6 𝑄2,𝑙 ↓sex
female ≥ 11, 200 26,504 10,525 [675] 5,667
I7 𝑄2,𝑙 ↓sex
female ≥ 12, 000 26,504 10,525 [1475] 5,667
I8 𝑄2,𝑙 ↓sex
female ≥ 13, 000 26,504 10,525 [2475] 5,667
I9 𝑄3,ℎ ↓sex
female ≥ 1250 2,603 1,197 [53] 14,995
I10 𝑄3,ℎ ↓race
black ≥ 210 2,603 194 [16] 4,491
I11 𝑄3,𝑚 ↓sex
female ≥ 3100 9,186 2,960 [140] 13,232
I12 𝑄3,𝑙 ↓sex
female ≥ 8500 20,064 8,444 [56] 7,748
I13 𝑄3,𝑙 ↓sex
female ≥ 9000 20,064 8,444 [556] 7,748
I14 𝑄4,ℎ ↓sex
female ≥ 1230 2,507 1,159 [71] 15,033
I15 𝑄4,𝑚 ↓sex
female ≥ 4400 13,541 4,330 [70] 11,862
I16 𝑄4,𝑚 ↓race
black ≥ 1450 13,541 1,369 [81] 3,316
,race
I17 𝑄4,𝑚 ↓sex
female ,black ≥ 680 13,541 633 [47] 1,675
I18 𝑄4,𝑙 ↓sex
female ≥ 8650 27,606 8,594 [56] 7,598
I19 𝑄4,𝑙 ↓sex
female ≥ 9100 27,606 8,594 [506] 7,598

not reported here for space constraints, show that its average performance is worst than those
of the approximate approaches, especially for large-scale datasets.

5.2. Experimental results
Impact of the search space size on performance. From Figure 4(a), we observe that, as
expected, the time increases while increasing the size of the search space 𝑚, for a fixed number
of selection conditions. The search space size can increase by either considering queries with the
same or similar selectivity and varying the considered protected group (e.g., I3 < I2 < I4; I10