Due to the impact of analytical processes on our life, an increasing efort is being devoted to the design of technological solutions that help humans in measuring the bias introduced by such processes and understanding its causes. Existing solutions can refer to either back-end or front-end stages of the data processing pipeline and usually represent bias in terms of some given diversity or fairness constraint. In our previous work [1], we proposed an approach for rewriting filtering and merge operations in pre-processing pipelines into the “closest” operations so that protected groups are adequately represented (i.e., covered) in the result. This is relevant because any under-represented category in an initial or intermediate dataset might lead to an under-representation of that category in any subsequent analytical process. Since many potential rewritings exist, the proposed approach is approximate and relies on a sample-based cardinality estimation, thus introducing a trade-of between the accuracy and the eficiency of the process. In this paper, we investigate this trade-of by first presenting various measures quantifying the error introduced by the rewriting, due to the applied approximation and the selected sample. Then, we (preliminarly) experimentally evaluate such measures on a real-world dataset.
The impact of data on our society is getting higher and higher,
with data about people being more and more often exploited
as the basis to make decisions that might impact people’s lives.
Thus, it becomes crucial to ensure that, in the systems enabling
such data-based decisions, data are dealt with in a responsible and
non-discriminating way [
Non-discrimination can be addressed by considering specific diversity and fairness constraints. Diversity allows us to capture the quality of a collection of items with respect to the variety of its constituent elements. On the other hand, fairness can be broadly defined as the impartial treatment of individuals and of demographic groups inside data processing tasks.
Among all data processing steps, data pre-processing plays a relevant role when considering non-discrimination issues since it can introduce technical bias by exacerbating pre-existing bias that may exist in society, with an impact on the whole data lifecycle.
When considering pre-processing tasks, an often considered non-discriminating constraint is coverage. Coverage constraints guarantee that the input, or training, dataset includes enough examples for each (protected) category of interest, thus increasing diversity with the aim of limiting the introduction of bias during the next analytical steps. Coverage is quite relevant in the first data processing tasks, like data transformation, since the used transformations might change the, possibly initially satisfied, coverage of protected categories.
In this paper, we are interested in investigating solutions for detecting bias in data-preprocessing steps, defined in terms of coverage constraints, with a special reference to filtering and merge data transformations, mitigating it, and checking whether the mitigation was efective. Specifically, we focus on classical data transformation operations, often defined in terms of SelectionProjection-Join (SPJ) operations over tabular data, that can reduce the number of records related to some protected or disadvantaged groups, defined in terms of some sensitive attributes, even if such attributes are not directly used in the specification of the data transformation operation.
In this frame, the approach we developed [
In this paper, we start from this approach and we investigate its efectiveness in the detection of the optimal coverage-based solution. To this aim, we introduce three main groups of measures quantifying the error that can be generated by the used approximated and sample-based approach. The first group of measures deals with the accuracy of the discretization applied in the pre-processing step. The second group deals with the error due to the usage of the sample for the grid generation and cardinality estimations, while the third group helps the user in quantitatively evaluating specific solutions obtained through the rewriting.
The generated rewritings are then (preliminarly)
experimentally analyzed in terms of the proposed measures, on a real-world
dataset. The obtained results provide hints on how to tune
approximation and sample related parameters to achieve a good
trade-of between accuracy and performance in the context of
coverage-based rewriting, by combining new results related to
accuracy presented in this paper with results related to
performance, previously presented in [
Even if the proposed measures have been defined in the context of a specific coverage-based approach, we believe that they can be of more general value in understanding the role of approximation and sampling during data pre-processing.
The remainder of the paper is structured as follows. In Section 2, we present the overall approach to coverage-based rewriting. In Section 3, we introduce new measures to quantify, in terms of accuracy, the impact of rewriting. In Section 4, we experimentally analyze the impact of the rewriting according to the introduced measures. Section 5 discusses related work while Section 6 concludes the paper and outlines future work directions. 2
We focus on data to be transformed for further data analytical
tasks. Data can refer specific protected (minorities or historically
disadvantaged) groups and we aim at guaranteeing that each
transformation step during the pre-processing pipeline, based
on filtering or merge operations, produces a new dataset
containing enough entries for each protected group of interest. In
the following, we briefly describe input data and the proposed
technique. Additional details can be found in [
tions we are interested in correspond to monotonic Select-ProjectJoin (SPJ) queries over input tabular data that might alter the representation (i.e., the coverage) of specific groups of interests, defined in terms of sensitive attribute values. To this aim, we focus on SPJ queries that return, among the others, at least one sensitive attribute (called sensitive SPJ operations or queries). For the sake of simplicity, we assume that selection conditions are defined over numeric attributes, even if the proposed approach can be easily extended to any other ordered domain. Thus, under the considered assumptions, sensitive attributes are not included in selection conditions (typical assumption in data processing).
In the following, when needed, we denote by ⟨1, ..., ⟩
or ⟨ ⟩, ≡ (1, ..., ), where 1, ..., are the constant values
appearing in the selection conditions ≡ in .
Coverage constraints. Conditions over the number of entries
belonging to a given protected group of interest returned by the
execution of SPJ queries can be specified in terms of coverage
constraints [
Coverage constraints can be provided together with or they can already be available in the system, as any other integrity constraint. This could be useful when they represent generally valid non-discrimination rules that must be satisfied by any query execution.
The approach. Given a dataset and a set of coverage
constraints , each selected sensitive SPJ query can be rewritten
into another query , , according to what presented in [
, ≡ ⟨⟩ is the closest query to ⟨ ⟩ according to the Euclidean distance between and in the unit space, satisfying (i), (ii), (iii), and (iv) (thus, , is the coverage-based rewriting syntactically closest to the input query, thus maximizing proximity and potentially user satisfaction).
In order to compute the optimal coverage-based rewriting of
an SPJ query ⟨ ⟩, given a set of coverage constraints and an
instance , we follow the approach presented in [
Canonical form generation. We first translate the selected SPJ queries into a canonical form, in which each selection condition containing operators (>, ≥, =) is translated into one or more equivalent conditions defined in terms of operator <. For example, any predicate of the form > can be transformed into the predicate − < − . When considering canonical forms, an optimal coverage-based rewriting query is obtained from the input query by replacing one or more selection predicates ≡ < with a predicate ′ ≡ < with ≥ . ′ is called a relaxation of . Relaxed queries generated through coverage-based rewriting starting from ⟨ ⟩, , and have the form ⟨⟩, with ≥ , and can be represented as points in the -dimensional space defined over the selection attributes. Taking into account the features of the canonical form and property (ii) of the optimal rewriting, it is simple to show that the query point corresponding to the optimal rewriting must be contained in the upper right region of the reference space with respect to the point represented by the input query. (a) Data distribution (b) Data discretization (4 bins) (c) Multi-dimensional grid (d) Multi-dimensional grid visit
Example 2.1. Consider the Diabetes US dataset1 and let be the sensitive attribute. Suppose we are interested in finding people whose number of medications is less than 10 and the number of performed lab tests is less than 30. Additionally, suppose we would like to guarantee that at least 15 females are present in the query result (coverage constraint). The corresponding SPJ query is ⟨30, 10⟩, defined in SQL as SELECT * FROM Diabetes WHERE num_lab_procedures < 30 AND num_medications < 10. Figure 1(a) shows the data distribution corresponding to a small sample of size 100 taken from the Diabetes relation, projected over the attributes referenced in the query selection conditions (points are colored and shaped according to the sensitive attribute values: blue crosses for females and black dots for males). The query corresponds to point (30, 10) in such a space and the region boxed at the bottom left of point (30, 10) contains the result of .
The query is already in canonical form, so no preliminary rewriting is required. The search space for detecting coveragebased rewritings of the input query corresponds to the grey region in Figure 1(b). ^ 1https://archive.ics.uci.edu/ml/datasets/Diabetes+130-US+hospitals+for+years+ 1999-2008
Pre-processing. According to property (ii) of the coverage-based rewriting, given an input query ⟨ ⟩, any coverage-based rewriting is located in the upper right portion of the space defined by . Thus, the (unit) search space contains infinite possible coverage-based rewritings among which the optimal one should be identified. During the pre-processing step, such search space is discretized, so that an approximation of the optimal solution can be detected in the next processing step by looking at the resulting finite set of points. To this aim, we first organize the search space as a multi-dimensional grid. The grid has axes, one for each selection attribute in the canonical form of ⟨ ⟩, and each axis, starting from query values, is discretized into a fixed set of bins, by using a binning approach (e.g, equi-width, dividing each axis in a fixed number of bins of equal size, or equi-depth, in which each bin contains an equal number of instances), typical of histogram generation. Each point at the intersection of hyperplanes corresponding to bin values corresponds to a sensitive SPJ query containing ⟨ ⟩, thus satisfying condition (ii) of the reference problem. The set of grid points identified in this way is called discretized search space. The approach is approximate because a smaller query, in terms of minimality and proximity, than that identified by the algorithm, corresponding to a coverage-based rewriting of the input query, might exist but, if it lies inside one grid cell, it cannot be discovered by the algorithm. Notice that the grid is computed starting from and ( is not used).
Example 2.2. During the pre-processing step, by applying, as an example, the equi-depth binning approach to each axis of our reference example, we obtain the grid represented in Figure 1(b), considering 4 bins for each axis. The points of the resulting discretized search space correspond to the grid intersection points. Each point corresponds to a sensitive SPJ query, obtained from the input one by replacing selection constants with the grid point coordinates (see Figure 1(c)). ^
Processing. During the processing step, we visit the discretized search space returned by the pre-processing step starting from the grid point corresponding to the input query. The discretized search space is visited one point after the other, at increasing distance from . For each point , we check whether the associated query ⟨⟩ is a coverage-based rewriting of ⟨ ⟩ by estimating the query result cardinality, for each protected group referenced by coverage constraints , and the query cardinality ( ( )).
The properties of the discretized search space and of the used
canonical form are taken into account for pruning cells that
cannot contain the solution and for further improving the eficiency
of the process, by iteratively refining the size and the number of
cells during the visit and, as a consequence, by working with a
discretized search space at varying granularity [
Example 2.3. Figure 1(d) illustrates the processing approach
for the considered example. Starting from the grid point
corresponding to the input query , we estimate the cardinality of
gender on , needed for checking constraint satisfaction, and
↓
of ( ), by relying on a sample-based approach, obtaining (2, 8).
Since the constraint is not satisfied, we further visit the other
points of the discretized search space at increasing distance from
, checking constraint satisfaction and looking for the minimum
rewriting (property (iv)). The visit proceeds as pointed out in
Figure 1(d) (the order of the visit is represented by the blue numbers
associated with the top right vertex of each cell). Shaped cells
are not visited thanks to the pruning efect: if ⟨⟩ ( ) satisfies
the coverage constraints, all the points in the upper right portion
of space defined by will not satisfy conditions (iv) and (v) of
the reference problem, thus they can be discarded. The optimal
coverage-based rewriting corresponds to query ⟨43, 20⟩ (big
blue dot in Figure 1 (d)) since (43, 20) is the point at the minimum
distance from the origin such that the corresponding query
satgender
isfies the considered coverage constraint ( ↓ ≥ 15). The
input query is thus rewritten into SELECT * FROM Adult WHERE
num_lab_procedures < 43 AND num_medications < 20. ^
Sample-based estimation. The processing step, as well as
coverage constraint checking, requires fast and accurate cardinality
estimates. To make the processing more eficient, similarly to
[
Performance evaluation. The analysis of the eficiency of the
proposed coverage-based query rewriting approach has been
investigated in a previous work [
The coverage-based rewriting of the input query can be obtained by visiting the grid, produced as the result of the pre-processing step, and by verifying constraint satisfaction relying on a samplebased approach. The optimal coverage-based rewriting is therefore approximate since: (i) the grid, that corresponds to the discretized search space, might have an impact on the accuracy of the selected coverage-based rewriting; (ii) the estimation error related to the sample usage has an impact on query cardinality estimation and on constraint satisfaction.
It is therefore important to introduce some measures quantifying the error that can be generated. To this aim, in the following we discuss three groups of measures: the first group deals with the approximation error related to the usage of the grid for the discretization of the query search space; the second group deals with the approximation error related to the usage of a sample during the pre-processing and processing phases; the third concerns the error related to the detected optimal rewriting. 3.1
Due to the usage of a discretized search space, the optimal coverage-based rewriting identified by the proposed approach is the best approximation of an optimal rewriting, given the considered grid. The accuracy related to the usage of a given grid for the detection of the optimal rewriting thus corresponds to the error introduced by the discretization process.
As pointed out before, given a query ⟨ ⟩, the visit proceeds at increasing distance from the query point . When an optimal rewriting ⟨⟩ is reached, this means that the neighbours of in the discretized search space cannot be optimal rewritings (otherwise the search would have stopped before). On the other hand, another point might exist that is not included in the search space but ⟨⟩ ( ) satisfies and either it is closer to the query point than or ⟨⟩ ( ) ⊆ ⟨⟩ ( ). Such point is an optimal rewriting but, due to the approximation, it cannot be identified by the proposed approach. The approximation error for the identified approximate optimal rewriting ⟨⟩, also called grid-based accuracy, can therefore be defined as the maximum distance between and all its neighbours on the grid, preceding it in the search; the accuracy is therefore lower than or equal to the diagonal of the grid cells having as a vertex and closer to than . By considering the entire grid, we can quantify the maximum and minimum grid-based accuracy in terms of the maximum and the minimum diagonal length of grid cells (see Figure 2 for a graphical explanation).
Definition 3.1 (Grid-based accuracy). Let be the grid generated from a dataset and a query using a certain binning approach . The mimimum/maximum grid-based accuracy of , denoted by and , is defined as the minimum/ maximum diagonal length of grid cells in , normalized between 0 and 1. □
Example 3.2. Figure 2 shows the normalized cell diagonal lengths for the grid created as discussed in Example 2.2. The grid-based accuracy for this grid varies between 0.05 (dotted blue line), corresponding to queries ⟨30, 15⟩ and ⟨30, 20⟩ and 0.73 (dashed blue line), corresponding to query ⟨90, 75⟩. ^
Diferent binning approaches might lead to a diferent gridbased accuracy. In particular, when fixing the reference data interval over each axis, binning approaches based on data distribution, like equi-depth, lead to a higher variability of grid-based accuracy, since they generate smaller buckets for dense regions and larger buckets for sparse ones, as stated by the following proposition.
Proposition 1. Let be the grid generated from a dataset and a query using the equi-width approach and that generated using the equi-depth approach, with bins for each axis in both cases. Then: (i) ≤ ; (ii) ≥ . □ 3.2
The accuracy of the query rewriting approach depends on the sample data distribution for two main reasons: (i) diferent sample distributions might lead to the generation of diferent buckets and therefore of diferent grids, with an impact on both preprocessing and processing steps; (ii) the sample is used for query cardinality estimation and, as a consequence, the estimation error has an impact on the minimality property, in addition, it might lead to a wrong assessment of constraint satisfaction. Impact on (pre-)processing In order to evaluate the impact of the sample usage on grid generation, we compare the data distribution of the dataset with the data distribution of the sample , both projected over the attributes appearing in the considered query . The more similar the two distributions, the lower is the impact of the sample selection in the detection of the optimal coverage-based rewriting.
Several metrics have been proposed for quantifying the
distance between two multivariate datasets. Many of them, e.g., the
Wasserstein metric [
In our work, we consider a very simple extension of the univariate KS metric, obtained by averaging the KS distance computed for each query attribute. The distance computed between two datasets and is denoted by (, ). This approach is suitable since, similarly to what we have proposed for the search space construction, where we rely on an aggregation of unidimensional histograms instead of a multidimensional histogram, it aggregates distances defined on each single attribute.
In order to investigate the impact of the KS distance for a sample on the identification of the optimal rewriting, it is useful to introduce some metrics, quantifying the diference in using instead of the initial dataset for the detection of the optimal coverage-based rewriting. Such metrics compute the average diference, in terms of minimality, proximity, and solution distance, between the optimal rewritings , and , , obtained by processing the sample and the original dataset , respectively, on a random set of queries , uniformly distributed in the query search space: • Average minimality diference (property (iv) of the optimal rewriting). It quantifies how much diferent , and , are, in average, with respect to their result set cardinalities when they are executed over the input dataset (thus, it quantifies, in average, the diference in the relaxation of the original query over the initial dataset):
| (, ( ))− (, ( )) | .
(, ) ≡ ∈ ( ( )) • Average proximity diference (property (v) of the optimal rewriting). It quantifies how much diferent , and , are, in average, with respect to their Euclidean distance () from the input query , in the unit space, further normalized between 0 and 1 (thus, it quantifies, in average, how far the two optimal rewritings are with respect to the original query): (, ) ≡ ∈ | (, , ) − (, , ) |. • Average solution distance: It quantifies how much diferent , and , are, in average, in terms of their Euclidean distance in the unit space, further normalized between 0 and 1 (thus, it quantifies, in average, how far the two optimal rewritings are, without taking the input dataset and the original query into account): (, ) ≡ ∈ (, , , ).
dence related to the considered sample (see Section 2) have an impact also on coverage constraint satisfaction. A constraint ≡ ↓ ≥ is satisfied on if ( = ( ( ))) ≥ . Since the sample-based estimation of ( = ( ( ))) might lead to an error of × ( ), in order to guarantee that the constraint is also satisfied by the input dataset , we can mod ify the constraint, when evaluated over the sample, as: ↓ ≥ + ( × ( )). This consideration makes the proposed samplebased approach reasonable for coverage constraints in which ( ) has the same order of magnitude as . Notice that, by changing the constraint as proposed above, we increase the probability of constraint satisfaction on the input dataset at the price of reducing proximity of the optimal rewriting with respect to the input query (since the optimal query will be further away from the initial one).
Let be a sample of dataset and , = ⟨⟩ be the
optimal solution obtained from , given a query ⟨ ⟩ and a set of
coverage constraints . It could be useful to introduce some
additional measures to evaluate the quality of the obtained
opti
mal rewriting , with respect to the discretized search space
identified by the chosen dataset , taking into account both the
applied relaxation with respect to the original query and the
approximation error, in line with what we have proposed for
grid-based and sample-based accuracy. To this aim, we propose
the following three measures:
• Grid-based accuracy of , . According to what discussed
in Subsection 3.1, it can be computed as the maximum
distance between and all its neighbours on the grid,
preceding it in the search (thus, the maximum diagonal
of the cells of the grid having as a vertex and closer to
than ).
• Relaxation degree. Similarly to [
|, ( ) |−| ( ) | .
| ( ) | • Proximity. It can be computed as the Euclidean distance between the optimal coverage-based rewriting , and in the unit space, further normalized between 0 and 1, thus indicating how far the optimal rewriting is with respect to the original query.
Example 3.3. The optimal coverage-based rewriting of the running example corresponds to query ⟨43, 20⟩ (see Example 2.3). The grid-based accuracy of such solution is 0.16 (see Figure 2), since this is the maximum length between the solution and its neighbours on the grid. Since ( ⟨43, 20⟩ ( )) = 38 and ( ( )) = 8 (see Figure 2), the relaxation degree is 3.75 (to guarantee constraint satisfaction, the cardinality of the rewritten query is about 4 times that of the original query). Finally, the proximity, i.e., the Euclidean distance between (30, 10) and (43, 20) in the unit space, normalized between 0 and 1, is 0.19, thus corresponding to a relaxation of 19% with respect to the maximum query, returning the whole dataset. ^ 4
In this section, we present some preliminary experimental results with the aim of analyzing the accuracy of the proposed query rewriting approach. 4.1
All experiments were conducted on a PC with an Intel Core i58300H 2.30 GHz CPU and 16GB main memory, running Microsoft Windows 10. All programs were coded in Python 3.8.
The experiments refer to a real dataset, stored in PostgreSQL: Diabetes US2 representing 10 years (1999-2008) of clinical care at 130 US hospitals and integrated delivery networks (100,000 instances). It includes over 50 features representing patient and hospital outcomes. For our experiments we use gender as sensitive attribute and we add a coverage constraint on .
For this dataset, we generated many random samples with an increasing size, guaranteeing a variable percentage of error (1% or 3%) and a variable level of confidence (95% or 99%). More precisely, we considered the following sample sizes: 1067 (3% error and 95% confidence), 1843 (3% error and 99% confidence), 9604 (1% error and 95% confidence), 16588 (1% error and 99% confidence). For each sample size, we generated 5 random samples, for a total of 20 samples. The samples are all small enough to be stored in main memory.
In order to evaluate the accuracy of the proposed approach, we randomly generated a set of 1000 queries, with diferent selectivities, and we compared the impact of the grid and of the considered sample in detecting the optimal coverage-based rewriting, by considering the measures presented in Section 3. All the selected queries contain three selection conditions (thus leading to a three-dimensional grid), with respect to the three numerical attributes with the highest number of distinct values, namely (number_emergency,num_lab_procedures,num_medications); selection values are picked at random from the attribute value range in the dataset. For the sake of simplicity, join queries are not considered for these preliminary experiments.
For each query, we then defined the coverage constraint taking into account the considered query and in such a way that it is neither satisfied on the dataset nor on the considered samples.
The experiments were performed by considering two distinct binning approaches during the pre-processing step: (i) equiwidth∗, corresponding to an equi-width approach, dividing each axis in a fixed number of bins of equal size, set as the minimum between a selected number (denoted by # in the experimental results) and the number of distinct values for the considered attribute in the dataset; (ii) equi-depth∗, in which each bin, defined as for the equi-width∗ approach, contains a constant number of instances. A variable number of bins, namely 4, 8, 16, 32, 64, has been considered for specific experiments.
We then performed three groups of experiments aimed at analyzing the grid-based, the sample-based, and the solutionbased accuracy of the optimal coverage-based rewriting. 2https://archive.ics.uci.edu/ml/datasets/Diabetes+130-US+hospitals+for+years+ 1999-2008 (a) Maximal grid-based accuracy (b) Minimal grid-based accuracy
Experimental evaluation 4.2.1 Grid-based accuracy. The first group of experiments aims at analyzing the maximum and minimum grid-based accuracy, as presented in Subsection 3.1, by varying the number of bins, with respect to the selected binning approach, namely equi-depth∗ and equi-width∗. To this aim, we selected a sample with size 16588 (sample 16588_3 in Figure 4) and we considered all the generated 1000 random queries. The obtained results are independent from the query selectivity, therefore in the following we discuss those obtained with selectivity equal to 2.5%.
Figure 3 shows that both the maximum and the minimum grid-based accuracy decrease by increasing the number of bins, independently from the chosen binning approach. This is because, by increasing the number of bins, the space is discretized into a higher number of cells, thus obtaining cells of smaller size.
From Figure 3 we also observe the behaviour described by Proposition 1: the maximal grid-based accuracy obtained with the equi-depth∗ approach is always higher than the grid-based accuracy obtained with the equi-width∗ approach; minimal accuracy behaves in the opposite way.
4.2.2 Sample-based accuracy. The second group of experiments deals with the analysis of the sample-based accuracy, according to the measures introduced in Subsection 3.2. To this aim, we considered all the samples described in Subsection 4.1 and, for each of them, we computed the KS distance with respect to the input dataset.
Results, presented in Figure 4, show that the obtained values are very similar and quite small: for most sample sizes, the greatest diferences refer to the third decimal digit. As expected, by increasing the sample size, the KS distance tends to decrease.
In order to evaluate the impact of the KS distance on samplebased accuracy measures, we considered the sample size leading to the highest variance (9604) and we selected the samples with the highest diference between the corresponding KS distances Sample 9604_1 9604_2 9604_3 9604_4 9604_5 Mean Variance KS Distance 0.0058 0.0064 0.0026 0.0071 0.0134 0.0071 1.24e-5 Sample 16588_1 16588_2 16588_3 16588_4 16588_5 Mean Variance
KS Distance 0.0156 0.0183 0.0130 0.0130 0.0119 0.0144 5.36e-6 (namely, 9604_3 and 9604_5). We then computed the samplebased accuracy measures on the set of 1000 random queries.
Table 1 shows the results obtained by considering the equidepth∗ approach and 32 bins (similar values has been obtained for the equi-width∗ and other numbers of bins). As you can see, there is no clear ordering between the two samples when considering such measures. In particular, sample 9604_3 is better than sample 9604_5 with respect to minimality; however, for proximity and solution distance the opposite result holds. Thus, it seems that the KS measure is not good enough for discriminating between samples with a diferent behaviour with respect to the detection of the optimal coverage-based rewriting. Additional work is therefore needed for investigating or defining alternative functions able to discriminate between samples under the considered scenario.
4.2.3 Solution-based accuracy. The last group of experiments aims at analyzing the solution-based accuracy, according to the measures introduced in Subsection 3.3, by varying the number of bins, with respect to the selected binning approach, namely equidepth∗ and equi-width∗. To this aim, we selected sample 16588_3 (i.e., the biggest sample with the smallest KS distance with respect to the initial dataset) and we considered all the generated 1000 random queries. The obtained results show a diferent behaviour with respect to the region in which the optimal solution is located, either dense or sparse. In particular, Figure 5 shows that, as expected, by increasing the number of bins, the grid-based accuracy of the solution will decrease as well. However, depending on where the optimal solution is located, the equi-depth∗ and the equi-width∗ approaches behave in a diferent way. More precisely, when the solution region is dense (Figure 5(a)), the accuracy is lower with the equi-depth∗ approach since in this case higher density will lead to smaller bins. On the other hand, when the solution region is sparse (Figure 5(b)), the accuracy is usually (a) Solution in a dense region (a) Solution in a dense region (b) Solution in a sparse region lower with the equi-width∗ approach since in this case lower density will lead to longer bins under the equi-depth∗ approach.
A similar behavior can be observed for the relaxation degree (Figure 6) and the proximity (Figure 7): by increasing the number of bins, they decrease for both the binning approaches. When the solution is contained in a dense region, equi-depth∗ behaves better than equi-width∗, especially for low numbers of bins. We further notice that, for very low numbers of bins, proximity and grid-based accuracy coincide (the farthest neighbour of the solution is the query point itself). (b) Solution in a sparse region
Finally, notice that dense regions have a greater impact on
query cardinalities and, as a consequence, on the relaxation
degree, whose values are usually higher in this case (starting from
8 bins), independently on the selected binning approach. On the
other hand, dense regions tend to generate optimal solutions with
lower proximity (more evident with the equi-depth∗ approach,
that is more sensible to data distribution), since constraint
satisfaction can be obtained on query points closer to the initial one.
In general, for uniformly distributed datasets, in which no sparse
regions can be detected, equi-depth∗ can be considered the best
option. By combining the obtained results with those presented
in [
The interest for coverage constraints has been introduced in [
The technique considered in this paper relies on rewriting.
Other fairness-aware rewriting approaches have been proposed
for OLAP queries [
Impact evaluation is quite relevant in the design and the
execution of non-discriminating pipelines, usually very complex
in real-world scenarios. Various systems have been designed
for supporting the user during this activity. Among them, we
recall: Fair-DAGs [
Rewriting approaches have been recognized as an interesting
mean for enforcing specific non-discriminating properties
guaranteeing transparency. In this paper, we started from the
approach proposed in [
Preliminary experimental results show that: (i) diferent
binning approaches lead to diferent grid-based accuracy degrees;
(ii) common measures for computing the distance between
distributions are not efective for analyzing their behaviour in the
detection of the optimal coverage-based solution; (iii) the number
of bins used in the generation of the search space has an impact
in the accuracy of the detected solution, and not only on the
performance [
The proposed approach is at the basis of covRew [
Future work is needed in order to understand how to define new distance functions between distributions, focusing on their behaviour during coverage-based rewriting. An additional issue concerns the definition and the analysis of further solution-based measures, evaluating the quality of the detected solution with respect to the solution that would have been obtained without considering a sample, as well as their integration in the covRew prototype system.