Naturalness in a type II seesaw model and implications

for physical scalars


Fatma-Zohra Hannou
email: fatma.hannou@lip6.fr

Bernd Amann
email: bernd.amann@lip6.fr

Mohamed-Amine Baazizi
email: amine.baazizi@lip6.fr

Explaining Query Answer Completeness and Correctness with Minimal Pattern Covers

Information incompleteness is a major data quality issue which is amplified by the increasing amount of data collected from unreliable sources. Assessing the completeness of data is crucial for determining the quality of the data itself, but also for verifying the validity of query answers over incomplete data. While there exists an important amount of work on modeling data completeness, deriving this completeness information has not received much attention. In this work, we tackle the issue of efficiently describing and inferring knowledge about data completeness w.r.t. to a complete reference data set and study the use of a pattern algebra for summarizing the completeness and validity of query answers. We describe an implementation and experiments with a real-world dataset to validate the effectiveness and the efficiency of our approach.

INTRODUCTION

Information incompleteness is a major data quality issue that is exacerbated by the growing number of applications, collecting data from distributed, open, and unreliable environments. Sensor networks and data integration are significant examples in which data incompleteness naturally arises due to hardware or software failures, data incompatibility, missing data access authorizations etc. In all these situations, querying and analyzing data can lead to deriving partial or incorrect answers. Extensive effort has been devoted to representing and querying incomplete databases [START_REF] Motro | Integrity = Validity + Completeness[END_REF][START_REF] Levy | Obtaining Complete Answers from Incomplete Databases[END_REF][START_REF] Fan | Relative Information Completeness[END_REF][START_REF] Lang | Partial results in database systems[END_REF][START_REF] Razniewski | Identifying the extent of completeness of query answers over partially complete databases[END_REF][START_REF] Sundarmurthy | m-tables: Representing missing data[END_REF]. The common characteristics of these approaches is the use of some intensional or extensional information about completeness for deciding whether a query returns complete answers and, in some cases, for annotating the query answers with some completeness meta-data. Despite these efforts, reasoning about data completeness remains tricky due to the complexity of exhaustively representing and deriving information about available and missing data in large datasets.

In many situations, datasets and query results are explicitly or implicitly depend on some complete reference (or master) datasets to describe their expected full extent. For instance, sensor databases are usually construed within a spatio-temporal reference delimiting the coverage of the captured data. It is also believed according to [START_REF] Loshin | Master data management[END_REF] that 80 % of enterprises maintain master data with their analytical databases (customers informations, product) . In other data-centric applications, a reference is defined by domain experts during database design and updated when necessary. Finally, it may also sometimes be useful to use an existing table or query result as a reference for deriving a comprehensive representation about available and missing information in some specific context.

Representing information completeness. To understand the importance of using reference datasets for assessing data completeness, consider the database in Table 2 which depicts an example of a sensor database. The table Energy reports on daily energy measurements for some locations specified by floor (fl) and room (ro). This database is endowed with a spatial reference MAP describing all locations in some building and a calendar CAL indicating the expected temporal coverage (Table 1). Observe that both reference data sets are not necessarily validated master data but might have been built by an expert for a specific analysis task. For various reasons, the current database misses some values that are pinpointed in grayscale in the Energy table. Assume that an analyst wants to gain a full knowledge about the segments of the data that are available or missing. To facilitate her understanding of the data, the analyst would like a summarized version of the completeness information and may opt for a pattern-based representation like the one presented in Table 3. This figure shows two tables P E and reports that no measure can be found for room r2 and week w2. This representation is compact as it only reports on the largest possible partitions that are complete (resp. missing) in the data. It is also covering as it reports on every possible maximal complete (resp. missing) partition of the data. Without this presentation, the analyst might have to issue several queries without any guarantee of deriving an exhaustive information about completeness that the pattern representation offers in a rather natural manner. Analyzing information completeness. Pattern tables can become very large due to randomness of missing information and may not be easily analyzed by hand. Querying pattern tables with SQL turns out to be a convenient means for extracting and reasoning about data completeness. In our example, if an analyst wants to identify the floors where all measures are available, she could issue the following query on P E and notice that, since p1 is the only pattern satisfying the predicate of Q0, the only floor satisfying her criteria is f 2.

Q0 : s e l e c t f l from P E where r o= ' * ' and we= ' * ' and da= ' * '

Querying pattern tables have another interesting application when it comes to extracting completeness information of query answers obtained from incomplete input tables. One solution consists in evaluating a query over the data and in extracting afterwards the completeness of the query answer from the corresponding reference dataset. However, extracting completeness patterns is costly and it often is more effective to derive the completeness patterns of query answers directly from the patterns of the input data. To illustrate this idea, consider Q1 which retrieves all measures referring to week w2: Q1 : s e l e c t * from Energy where we = ' w2 ' ;

By evaluating Q1 over P E and P E respectively, we obtain The pattern completeness model can also play a crucial role for validating the correctness of aggregation queries answers. When such queries are applied on incomplete data, the values resulting from aggregating incomplete partitions are simply incorrect and there is means to notify this fact to the user. To illustrate the role of the pattern model in detecting potential problems with aggregation queries, consider Q2 which sums the energy consumption over all day values.

Q2 : s e l e c t f l , ro , we , sum(kWh) as kWh from Energy group by f l , ro , we This query returns both valid and non-valid answers produced by complete and incomplete partitions respectively. Incomplete partitions producing incorrect results can easily be identified by patterns for which the value of the attribute day is a constant instead of * . These "incompleteness" patterns are separated from the correct partitions in Q2(P E ) and Q2(P E ). Annotating query results. Completeness pattern tables also can be used for rewriting aggregation queries to automatically annotate the produced results. For example, Table 4 shows the annotated result of query Q2 where completeness information is directly extracted from P2 and P2. This result can be obtained by rewriting Q2 into a union of two queries separating the correct and incorrect answers. For example, for generating the subset of correct results generated by complete partitions, we use the following query rewriting for Q2 : The partition of incorrect and incorrect results can be generated by changing the last filter into p.da != ' * '. In a similar way, it is straightforward to to define a SQL query which generates the set of missing answers by joining the reference data set with the missing pattern table.

Q2(P

The last use-case shows another benefit of completeness patters when joining data tables. Consider that an analyst wants to exploit the result of Q2 to derive the consumption per square meter. To do so, she join the result of Q2, which has been materialized in the Contributions. In this article we are interested in reasoning with relative information completeness in general and in analyzing query answers over incomplete datasets. This setting is of interest for many practical situations where data analysts need to assess the quality of complex queries. Our main contributions are the following:

• a new data completeness model based on the notion of minimal completeness pattern cover for summarizing relative completeness information ;

• a new sound and complete pattern algebra extending the relational algebra with two fundamental operators, allowing for generating and transforming completeness pattern covers ;

• an implementation and an experimental evaluation on a real-world sensor dataset, on top of a standard relational DBMS.

Paper Outline. The rest of the article is structured as follows. Section 2 discusses related work. Section 3 introduces the pattern model as well as the notions of completeness and correctness of SQL queries. The pattern algebra and some applications of pattern queries are presented in Section 4. Section 5 describes our solution for processing and optimize pattern queries using standard relational database technology and presents two algorithms for generating pattern tables. The experimentations presented in Section 6 evaluate our approach on a real-world sensor dataset.

RELATED WORK

Modeling Information Completeness. Information completeness is a major data quality issue that received attention in several contexts [START_REF] Pipino | Data Quality Assessment[END_REF][START_REF] Batini | Data Quality: Concepts, Methodologies and Techniques (Data-Centric Systems and Applications[END_REF]. In the database context, data completeness usually addresses the question of query answer completeness under two different settings: the Closed-World-Assumption (CWA) which considers that the database contains all tuples while some of them might have null values [START_REF] Imieliński | Incomplete information in relational databases[END_REF], and the open-world assumption (OWA) which considers, in addition to the possibility of attributes with null values, tuples which are missing in the database.

Under the OWA setting, some line of work considers using reference database DBC which can be either virtual or materialized to capture the full extent of data. A standard way for representing the completeness of a database DB w.r.t. a virtual database DBC consists in defining complete information as views over DBC [START_REF] Motro | Integrity = Validity + Completeness[END_REF][START_REF] Levy | Obtaining Complete Answers from Incomplete Databases[END_REF][START_REF] Razniewski | Identifying the extent of completeness of query answers over partially complete databases[END_REF]. Deciding whether a query is complete then relies on determining whether this query can be rewritten into queries that can be answered on DBC using the defined views.

Our work is more reminiscent to the relative information completeness line of work using materialized reference (master) datasets [START_REF] Fan | Relative Information Completeness[END_REF]. In this work, given a database DB and a master database DBC , deciding whether DB is complete for a query Q resorts to finding a set of containment constraints V of the form q(DB) ⊆ p(DBC ) where q is a query on DB and p is a projection on DBC . The complexity bounds obtained for different languages used for expressing queries and containment constraints demonstrate the difficulty of reasoning about information completeness [START_REF] Fan | Relative Information Completeness[END_REF]. Our pattern tables can be considered as exhaustive sets (disjunctions) of conjunctive containment constraints. Our goal within this setting is not only to decide if the answer is complete, but also to compute all containment constraints (patterns) satisfied by the query answer.

[16] introduces m-tables (inspired from c-tables [START_REF] Imieliński | Incomplete information in relational databases[END_REF]) for representing completeness information and an algebra over m-tables for annotating query answers with certainty information. Our completeness patterns can be assimilated to extended tuples in the m-tables model, by substituting m by * . This theoretical model is more expressive than our pattern based model, but also has more practical issues than our model which can efficiently be implemented by using standard relational database technology.

Pattern-based Completeness Models and Algebras. The seminal work of [START_REF] Motro | Integrity = Validity + Completeness[END_REF] suggests a model based on meta tuples that describe data integrity (completeness and correctness) constraints. Meta relations are similar to our pattern tables, where meta tuples are used to define available, valid and invalid data and to encode logical views over virtual complete and correct data tables. Query completeness checks if there exists a rewriting of the query using only complete views. Another idea of this early work is the definition of an algebra that manipulates meta tuples for producing sound (but not complete) sets of meta tuples satisfied by an input query.

More recently, [START_REF] Razniewski | Identifying the extent of completeness of query answers over partially complete databases[END_REF] presents an approach which consists in associating completeness patterns to data tables and an algebra for querying patterns to produce query answer completeness information. From this work we adopt the approach of using patterns and of defining an algebra to ma-nipulate these patterns. In [START_REF] Razniewski | Identifying the extent of completeness of query answers over partially complete databases[END_REF] completeness patterns describe the extent of data completeness as views over a virtual complete database, whereas we suppose that completeness of a data table or query answer is automatically assessed w.r.t. a materialized reference table. This introduces an additional practical and semantic dimension for analyzing quality issues of data and query results related to information incompleteness.

The work in [START_REF] Lang | Partial results in database systems[END_REF] analyzes different types of partial result anomalies engendered by data incompleteness. The data completeness model distinguishes between cardinality (incomplete, phantom, indeterminate) and correctness (credible and non-credible) anomalies at different granularity levels (input, operator, column, partition). The authors also study how these anomalies are propagated within a query plan. We follow the same approach regarding completeness propagation using operators at the granularity of partition (down to individual tuples). We derive raw completeness informations from reference data whereas [START_REF] Lang | Partial results in database systems[END_REF] derives completeness information from observed physical access anomalies.

Query Result Correctness. In our setting, correctness does not deal with the validity of data tuples w.r.t. logical constraints as in [START_REF] Motro | Integrity = Validity + Completeness[END_REF][START_REF] Levy | Obtaining Complete Answers from Incomplete Databases[END_REF], but is more related to the concept of summarizability [START_REF] Mazón | A survey on summarizability issues in multidimensional modeling[END_REF]. The notion of summarizability was first introduced by [START_REF] Shoshani | OLAP and statistical databases: Similarities and differences[END_REF] in the context of statistical databases, where it refers to the correct computation of aggregate values with a coarser level of detail from aggregate values with a finer level of detail. One of the summarizability conditions defined in [START_REF] Shoshani | OLAP and statistical databases: Similarities and differences[END_REF] is completeness which checks if all elements in a cluster (coarser level) exist and are attached to some cluster. In our setting, this mainly corresponds to the constraint that the partitions (clusters) generated by the group-by clause of an analytical query are complete. As we we will show in Section 4.2, our pattern model and algebra also allows us to identify and filter incomplete partitions.

Provenance and explanations. Many existing work deals

with deriving explanations for missing answers [START_REF] Herschel | Artemis: A system for analyzing missing answers[END_REF][START_REF] Herschel | Explaining missing answers to spjua queries[END_REF] or with answering why-not questions [START_REF] Tran | How to conquer why-not questions[END_REF][START_REF] Bidoit | Efficient computation of polynomial explanations of why-not questions[END_REF]. These works assume the data to be complete and focus on understanding the behaviour of queries rather than on evaluating the impact of incomplete data on the completeness and the validity of queries with aggregation.

DATA MODEL

Reference tables and completeness

The main extension of our data model with respect to the relational data model is the possibility to define reference tables for representing completeness constraints over data tables. Definition 1. Let D and R be two relational tables such that D contains all attributes A of table R.

= (D, R) a relational table Γ(T ) = R D with null values such that ∆(Γ(T )) = T . Definition 2. A constrained table T = (D, R) with refer- ence attributes A is complete iff R ⊆ πA(D).
Example 2. The constrained table T =(Energy, R) in Table 2 is not complete for R = MAP×CAL but it is complete for R=σ we= w1 ∧ro= r1 (MAP×CAL)

Minimal pattern covers

In this section we introduce the notion of minimal completeness pattern cover as a comprehensive description of all complete and empty data partitions in a constrained table. Definition 3. Let A = {a1, a2, ..., an} be a set of reference attributes where the domain of each attribute is extended by a distinguished value * called wildcard. A (completeness) pattern p = [a1 : v1, a2 : v2, ..., an : vn] over A is a tuple which assigns to each reference attribute ai ∈ A a value vi ∈ dom(ai) ∪ { * } in the extended domain of ai. A set of completeness patterns P (A) = {p1, p2, . . . , p k } over a set of reference attributes A is called a pattern table.

In the following we will denote by [ * ] the wildcard pattern where all attributes are assigned to wildcards. Observe that a pattern table might contain only data tuples, i.e. pattern tuples without any wildcards. Completeness patterns are part of a generalization/specialization hierarchy defined as follows.

Definition 4. A pattern p1 generalizes a pattern p2 if p1 can be obtained from p2 by replacing zero or more constants by wildcards. Inversely, p1 specializes p2 if p1 can be obtained from p2 by replacing zero or more wildcards by constants.

We can show that this generalization/specialization hierarchy forms a semi-lattice with the wildcard pattern as topelement and data tuples as bottom elements.

Reasoning with minimal covers

Completeness patterns define data partitions and minimal pattern covers can be used for reasoning about the completeness of these partitions. For example, by the definition of minimal cover, we can show for all constrained tables T = (D, R) where R = ∅ and all patterns p ∈ P * (T ) in the minimal cover of T that:

• the instance I(p, D) is complete and not empty.

• the instances I(p , D) of all specializations p of p are complete (but might be empty) and

• the instances I(p , D) of all generalizations p = p of p are incomplete and not empty.

Similarly, let T = (D, R) denote the complement of T where D contains all tuples "missing" in D w.r.t. R and P * (T ) be the minimal cover of T . Then as before, we can show for all T = (D, R) where R = ∅ and all patterns p ∈ P * (T ) in the minimal cover of T :

• the instance I(p, D) is incomplete and empty.

• the instances I(p , D) of all specializations p of p are empty (but might be complete) and

• the instances I(p , D) of all generalization p = p of p are incomplete and not empty.

We introduce the following attributes for characterizing some completeness pattern p:

-

E : I(p, D) is empty; -N : I(p, D) is not empty; -C : I(p, D) is complete; -I : I(p, D) is incomplete;
For example, a pattern p is an E-pattern, if its partition is empty. Then, an IE-pattern denotes a partition which is incomplete and empty, i.e. missing.

Example 5. Consider a minimal cover P and its complement P given in Table 5. Figure 1 is a tree representation

P A B C a4 * * a1 b2 * a3 * c2 * * c4
of patterns where each node at some level i in the tree corresponds to a pattern with i constant attributes. The wild-

COMPLETENESS PATTERN ALGEBRA

Pattern queries and algebra

Let T = (D, R) be a constrained table and Q be a relational query which can be applied to D and R. Our goal is to define a set of operators which allow us to compute the minimal cover P * (T ) of the result of T = Q(T ) = (Q(D), Q(R)). Suppose that there exists an operator computing the minimal cover of some constrained table T . Then it is possible to obtain the minimal cover P * (T ) of T by applying : P * (T ) = (Q(D), Q(R)) (see red dashed lines in Figure 2). An alternative way is to rewrite Q(D) into a new query Q(P, R) over a strict (not necessarily minimal) cover P (T ) of constrained table T such that Q takes as input the couple (P, R) and produces the new couple (P * (T ), Q(R)) (see blue solid line in Figure 2).

T = (D, R) T = (D , R ) P (T ) P * (T ) Q Q Figure 2: Pattern queries
In the following we will show that it is possible to extend the relational algebra RA with two operators unfold ( ) and fold ( ) for transforming strictly covering (but not necessarily reduced) pattern tables and to use this extended algebra RAext = RA ∪ { , } to define a new pattern algebra RApatt over pattern tables. Definition 11. The unfold operator A(P, R) generates for a given pattern table P and reference table R an equivalent pattern table P ≡R P where all values of attributes ai ∈ A are constant values.

The unfolding A(P, R) of a pattern table P on some attribute set A w.r.t. its reference table R can be defined by the following relational algebra expression:

A(P, R) = πR.A,P.¬A(P 1 θ R) (1)
where θ = a j ∈A (P.aj = * ∨ P.aj = R.aj) for all attributes in A and πR.A,P.¬A denotes the projection on attributes A of R and on all attributes of P except A.

Example 6. Consider the following pattern table P and the reference of Table 1. Unfolding a minimal pattern table does not preserve minimality. For example, the third pattern subsumes the second one in the result. Operator fold a i is the inverse operator of a i and generalizes, when possible, all subsets S of patterns p ∈ S which are equal for all attributes except for attribute ai into a single pattern pa i : * with a wildcard value for attribute ai = * : Definition 12. The fold operator a i (P, R) generates for a given pattern table P and reference table R an equivalent pattern table P ≡R P where there exists no pattern pa i : * and subset S ⊆ P of specializations p of pa i : * where pa i : * = * and pa i : * is equivalent to S: ∃pa i : * , S ⊆ P : pa i : * = * ∧ {pa i : * } ≡R S.

To compute A(P, R) we first compute the set M = R -I(P, R) = R -D of all reference tuples missing in D1 . Then, let pa i : * denote the pattern obtained from p by replacing the constant value vi of attribute ai in p by a wildcard * . The semi-join expression G(ai) = σ a i = * (P ) θ M where θ = i =j (P.aj = * ∨ P.aj = M.aj) returns all patterns p in P which cannot be generalized on ai: condition θ is true for all patterns p ∈ P where the pa i : * is incomplete (its instance in M is not empty). Then G(ai) = σ a i = * (P )-G(ai) returns the set of patterns p where pa i : * is complete and we can define the folding operator as follows:

a i (P, R) = σa i = * (P ) ∪ G(ai) ∪ {[ai : * ]} × π¬a i (G(ai))
Observe that if there is no pattern p ∈ P where ai has a constant value, then G(ai) and G(ai) are empty and a i (P, R) = P . Therefore, ro(P , R) returns P E in Table 3.

As for unfold, the fold operation is associative and can be generalized on a set of attributes A = {a1, a2, ..., an}:

A(P, R) = P for A = ∅ a i ∈A h ( a i ( A-a i (P, R), R)) otherwise (2)
In the following, (P, R) (unfold all) and (P, R) (fold all) will denote the unfold and fold operations over all reference attributes in P (and R). It is easy to show that ( (P, R), R) = P and ( (D, R), R) = D Using the extended relational algebra RAext, we can now define a pattern algebra RApatt which consists in defining for each relational operator op ∈= {σ, π, 1, ∪, ∩, -} its counterpart ôp ∈ {σ, π, 1, ∪, ∩, -}. Let P and P be two strict covers of constrained tables T = (D, R) and T = (D , R ). Then we define the following pattern algebra RApatt = {σ, π, 1, ∪, ∩, -} where each operator ôp is defined by using its relational counterpart op and operators and : ôp (P ) = ( op ( (P, R)), op (R))

(3)

P ôp P = ( (P, R) op (P , R ), R op R ) (4)
Theorem 3. RApatt is sound and complete.

Proof. We show that for all relational operators op ∈ {σ, π, 1, ∪, ∩, -}, constrained tables T = (D, R) and T = (D , R ) with strict covers P and P respectively, equations 5 and 6 are true: ôp (P ) = ( op (D), op (R))

(5)

P ôp P = (D op D , R op R ) (6)
For proving soundness and completeness we use the two equalities P = (D, R) and D = (P, R); Soundness: ôp (P ) = ( op ( (P, R)), op (R)) = ( op (D), op (R))

P ôp P = ( (P, R) op (P , R ), R op R ) = (D op D , R op R )
The first equality in both equations is obtained by definitions 3 and 4, respectively. Completeness:

( op (D), op (R)) = ( op ( (P, R)), op (R)) = ôp (P ) (7)
(D op D , R op R ) = ( (P, R) op (P , R ), R op R ) (8) =P ôp P (9)
The last equality in both equations is obtained by definitions 3 and 4, respectively.

Safe projection. Using the extended relational algebra, we also can define a specific operator called safe projection which filters all complete partitions before projection. Let Aπ denote the attributes removed by some projection. Then θπ = a i ∈Aπ (ai = * ) filters all patterns which are incomplete for attributes Aπ. The safe projection operator π * first folds all patterns over the attributes which are projected out and filters all incomplete dimensions before projection. This guarantees that the result only contains patterns corresponding to partitions which were complete w.r.t. the removed attributes:

π * ¬Aπ (P, R) =(π¬A π (σ θπ ( Aπ (P, R))), π¬A π (R)) (10)
Observe also that if P is already a minimal cover, projection produces a minimal cover without requiring a final fold operation.

Pattern query examples

The extended relational algebra and the pattern algebra can be used to define queries on pattern tables. Let T = (D, R) be a constrained table with a strict cover P over some reference attributes A.

Generating pattern and dimension tables. By definition, the complete unfolding (P, R) of P generates table D. On the other hand, the complete folding (P, R) of P generates the minimal cover of T . Observe that we also can obtain the same minimal cover by a complete folding (D, R) of D.

Querying pattern tables. As mentioned in Section 3.3, it is possible to check the completeness and emptiness of partitions in T using only information available in the minimal cover P and its complement P . It is easy to show that simple selection over pattern tables is sufficient to check if a given pattern p exists in some pattern table P or is a specialization/generalization of a pattern p ∈ P . For example pattern [a5, * , * ] is incomplete and not empty (IN) or complete and empty (CE) since query σ A= a5 (P ∪ P ) is empty (see Section 3.3).

Identifying complete partitions. Consider, for example the SQL query with reference table R(f l, ro, we, da): s e l e c t f l , we , avg ( khw ) from D group by f l , we Let P be a strict cover of constrained table T = (D, R). The completeness patterns of the result can be computed by the projection πfl,we (P ) whereas the safe projection presented in Section 4.1 π * f l,we (P ) retrieves the patterns of all partitions with correct result.

Identify missing information in joins.

Folding can be used to analyze completeness issues in join queries and to identify missing information in input data tables. For example, consider a natural join T 1 S between two data tables T and S sharing a set of attributes A. Then, (πA(T ), πA(S)) returns a compact representation of all tuples in T that can be joined with S whereas (πA(T ) -πA(S), πA(T )) returns a compact representation of the tuples in S that are missing with respect to T in order to produce a complete result.

PATTERN QUERY PROCESSING

Pattern query optimization and execution

As shown in Section 4.1 unfolding can directly be translated into the relational algebra, whereas folding over a set of attributes needs recursion which is not expressible in relational algebra (see Section 5.3 for implementations of ). Based on these observations, it is possible to rewrite any pattern query without folding into a relational query over pattern tables and reference tables. We will illustrate this by two examples with selection and projection.

Example 8. Let T = (D, R) be a constrained table strictly covered by a pattern table P . Let σ θσ (D) be a selection with a filtering predicate θσ using only reference attributes. The following pattern selection generates a minimal cover for the result of Q:

σθσ (P, R) = (σ θσ ( (P, R)), σ θσ (R)) (11)
Unfolding is necessary to check the existence of tuples in pattern instances. For example, in order to check if a pattern p = (a1 : v1, . . . , ai : * , . . . , an : vn) satisfies a filtering condition ai=ci, p must be unfolded on attribute ai. As shown before, the final fold operation cannot be translated into relational algebra without recursion. However the subexpression composed of a selection and an unfold can be translated into the relational algebra and optimized using standard relational query rewriting. Starting from the filtering expression Q = σ θσ ( (P, R)) we can apply following rewriting steps to obtain a more optimal expression in relational algebra:

• replace (P, R) by A(P, R) unfolding P only over the filtering attributes A = {ai, ..., a k } used in the filtering condition θσ;

• replace A(P, R) by its relational definition and push the selection condition θσ into the unfold rewriting:

Q = πR.A,P.¬A(P 1 θ (σ θσ (R)))
where θ = a j ∈A (P.aj = * ∨ P.aj = R.aj)

Finally, if the condition is a conjunction of equality predicates ai = ci, all pattern attributes ai ∈ A can safely be replaced by ai : * and join can be replaced by semi-join:

Q = ({[A : * ]} × (πP.¬A(P θ (σ θσ (R))), σ θσ (R)))
The final query expression can directly be translated into SQL.

Example 9. Consider the following more complex query expression over the same constrained table (D, R):

Q = π f l,ro,we,da (σ f l= f 1 (D))
Let P be a strict (not necessarily minimal) cover of D and R = MAP × CAL. By applying similar rewriting steps as before, we can obtain the following pattern query which generates a strict cover of the constrained query result (Q(D), Q(R)): {f l : * } × π P.ro,P.we,P.da (P 1 cond (σ f l= f 1 (MAP)) [START_REF] Pipino | Data Quality Assessment[END_REF] The corresponding SQL query is the following: s e l e c t ' * ' as f l , p . ro , p . we , p . da from P j o i n MAP on ( P . f l = ' * ' or P * . f l =MAP . f l ) and ( P . r o= ' * ' or P . r o=MAP . r o ) where MAP . f l = ' f 1 ' Observe that the SQL query only refers to table MAP for unfolding attribute f l. Reference table CAL is independent of MAP and can be ignored. This point is discussed in more detail in the following section.

Independent reference tables

Fold ( ) and unfold ( ) comprise costly joins with reference tables. In many real world settings, reference tables R = R1 × R2 × ... × Rn are defined by the Cartesian product of independent reference tables Ri corresponding to spatial, temporal and other dimensions. These reference tables Ri are obviously much smaller than the generated reference table R and introduce optimization opportunities for reducing unfolding/folding costs.

Definition 13. Let P be a pattern table with a reference table R = R1 × R2 × ... × Rn. The unfolding of a pattern table P on some attribute set A = A1 ∪ A2 ∪ ... ∪ A k where Ai are non-empty subsets of attributes of sub-table Ri (wlg. unfolding is done over the first k reference tables Ri) is defined as follows:

A(P, R) = πR i .A i ,P.¬A(P 1 θ 1 R1 1 θ 2 R2 1 θ 3 ... 1 θ k R k )) ( 13
)
where θ i = a j ∈A i (P.aj = * ∨P.aj = Ri.aj) and πR i .A i ,P.¬A denotes the projection on attributes Ai of Ri and on all attributes of P except A.

Observe that A only joins with reference tables Ri which contain at least one attribute a ∈ A. Definition 14. The folding of a pattern table P on some attribute ai of a reference table Rj is defined as in Definition 12, except that the missing tuples can directly be computed from the reference table Rj without considering the other tables: M = Rj -πA j (D).

Then, similarly to unfold, the fold operator A only needs to access reference tables Rj which contain at least one attribute ai ∈ A.

Proposition 4. If all attribute domains are independent and the input pattern tables are minimal covers, selection with equality, projection and Cartesian product can be expressed using the relational algebra (without ) and generate minimal covers.

Proof. The proof directly follows from the definitions of selection with equality, projection and Cartesian product.

Folding algorithms

As shown in Section 4.1 the fold operator can be implemented by an iterative evaluation of standard SQL queries including joins with reference tables (Equation 2). This section will present two optimized folding algorithms. The first algorithm F oldData computes minimal covers for data tables and the second algorithm F oldP atterns directly folds pattern tables into minimal covers without a preliminary unfolding step.

Folding data

Algorithm F oldData (Algorithm 1) computes for a given constrained table T = (D, R) a strict cover P * (T ) following a set of attributes A. If A is the set of all attributes in T , F oldData produces the minimal cover of T . The algorithm explores the data table by searching for complete partitions. It starts from the most general pattern i.e. wildcard pattern [ * ] (level 0) and explores top-down and breadth-first the pattern subsumption lattice LD generated by the active attribute domains in the data table D. Each level l corresponds to all patterns p with l constants. For checking if some pattern p is satisfied by D, the algorithm compares the cardinality of p in D and R using standard SQL queries (we assume that the projection of D on the reference attributes is included in R). After each level, all specializations of the found complete patterns p are by definition also complete and the tuples covered by p can be pruned from D before executing the next level. Algorithm F oldData uses the following functions:

• powerSet(A, N ) produces all subsets of A of cardinality N .

• patterns(A, D) produces for a set of attributes A, all patterns πA(D)

× {[ * ]} • checkComp(p, D, R) checks if I(p, D) = I(p, R)
• prune(P, D) deletes from D all tuples satisfied by patterns p ∈ P .

Observe that operations checkComp and patterns can be implemented by standard SQL queries. In particular, patterns is a simple projection on D and checkComp can be implemented by comparing the result of two count-queries on D and R (we suppose that D ⊆ R). In the worst case, . The number of patterns size(LD) of LD depends on the active attribute domains in the data table D and is exponential in the number of attributes: size(LD) = n i=1 (C i n ) * Dn where n is the number of attributes, and Di is the maximum size of the Cartesian product of the active domain of i attributes in the data table. The size of the reference table influences the cost of checking pattern satisfaction. Such a worst case scenario corresponds to particular case of random missing data which generates large pattern tables without pruning opportunities. As we show in our experiments, real-world data generally follows more regular incompleteness schemes which increase the compression rate and folding performance.

Folding pattern tables

Algorithm F oldData operates exclusively on data tables and cannot be used to fold pattern tables without a preliminary complete unfold. This unfolding obviously loses the compression of pattern tables, in particular for pattern tables with a high compactness ratios.

A pattern table P is not minimal for two main reasons. First, it might not be reduced, i.e. it contains two patterns p1 and p2 such that p1 < p2. Second, it might not be a cover, i.e. there might exist a subset of patterns S ⊆ P which could be merged into a single equivalent pattern p ∈ P . For example [f1,r1,w1, * ] and [f1,r2,w1, * ] from P can be merged into [f1, * ,w1, * ] / ∈ P . Algorithm 2 treats these issues separately. The merge step (lines 1 to 11) first solves the second issue and checks if the instance I(S, R) of a subset S ⊆ P is equivalent to the instance I(p, R) of a pattern p ∈ P . The algorithm explores the pattern lattice bottom-up starting from the most specialized pattern (at the lowest level) and by recursively merging sets S of patterns which differ only on the constant of one attribute. As soon as S can be merged into one pattern p, the latter is added to P (it might be merged with a higher level pattern at the next iteration). Notice that merged patterns are removed only after all level merges are performed (line 11), because one pattern can take part in several pattern merges. For example, [f1,r1,w1, * ] can merge first with [f1,r2,w1, * ] to generate [f1, * ,w1, * ], and merge a second time with [f2,r1,w1, * ] to produce [ * ,r1,w1, * ]).

The first outer loop performs the merge and uses the following functions:

• getP att(P, level) returns all patterns p ∈ P with level constant attributes.

• isGen(p1, p2) checks if p1 is a generalization of p2 (Definition 4)

• gen(p, a) generalizes pattern p by replacing the constant attribute a by a wildcard.

• getConstAttrs(p) finds all constant attributes of pattern p.

• checkComp(X, p, T, R) checks if the instance of pattern set X in data table T is equal to the instance of pattern p in R.

• getSimP att(P, p, a) returns all patterns in P which differ from p by a different constant value for attribute a.

To deal with the first issue, Algorithm F oldP atterns reduces P by removing all remaining patterns p1 ∈ P which specialize another pattern p2 ∈ P . This can be done by a simple auto-join on P (lines 12 to 17 . Since the size Di over the pattern table P is in general much smaller than the size Di over the data set D, computing the minimal cover for P (without unfold) is in general much more efficient than computing the minimal cover on the data set D. This observation is confirmed by our experiments (see Section 6) Proposition 5. Algorithm F oldP atterns is correct.

Proof. We can show that a pattern p can only be generated if there exists an attribute a and a subset of patterns S ⊆ P such that p generalizes all patterns in S on attribute a and S is equivalent to p. Then by following a recursive bottom-up strategy we guarantee that all possible generalizations are tested, which preserves the pattern covers equivalence. The reduce step guarantees minimality, by browsing the pattern lattice and filtering all possible specializations.

EXPERIMENTATION

The goal of our experiments are manifold: (i) testifying on the effectiveness of patterns in compactly representing completeness, (ii) analyzing the performance of the pattern derivation algorithms (Algorithms 1 and 2) and (iii) studying the efficiency impact of the pattern algebra.

We ran our experiments on a standard Linux machine equipped with a 2.4 GhZ dual core CPU, 8GB of RAM and 350 GB of standard storage. The algorithms are implemented in Python 2.6 whereas data and patterns were managed in PostgresSQL [START_REF] Stonebraker | The design of postgres[END_REF] and accessed using the psy-copg2+ library of Python. We did not define any indexes to accelerate filters and joins.

Datasets

We use both a real-world and a synthetic dataset. The real-world dataset corresponds to sensor measurements of different kinds (electricity, heating,...) collected during one year at our University campus. This dataset features both spatial and temporal incompleteness since not at all parts of the campus are covered and many of the sensors operate erratically. The synthetic dataset is generated from the real one by introducing more randomness for the purpose of studying the impact of data distribution on pattern compactness.

We restrict on measures pertaining to temperatures collected in 12 out of 96 buildings and refer to this data with Temp. We build two reference tables with different spatial coverage and identical temporal span. The first reference, noted R All , includes all spatial locations of the campus regardless of the existence of temperature sensors. The second reference, noted RT emp, restricts on localities equipped with a temperature sensor, that is, localities present in Temp. The schema of the data and the reference tables together with their sizes are reported in 6.

Temp(building, f loor, room, year, month, day, hour, value) Loc(building, f loor, room) Cal(year, month, day, hour) Intuitively, the choice of the reference has an impact on the derivation of completeness patterns in terms of efficiency and effectiveness. We start by investigating the effectiveness by studying the variation of the compaction ratio when varying the size of the data and of its associated reference. To do so, we build two smaller data tables by restricting Temp spatially, by selecting only the measures of one building (e.g. Building 25), and temporally, by keeping the measures pertaining to one month out of 12 (e.g. January). The resulting tables are respectively noted with T OneBlg and T OneMon. Their cardinalities are reported in Table 7 together with their completeness ratio CR(ds, R) = |ds|/|Rx| w.r.t. their references Rx. We denote by R ds All and R ds T emp the reference tables obtained by using the same spatial or temporal restriction of the dataset ds. For example, R T OneBlg All = σ building= 25 (R All ). As expected, the closer data is to its reference, the better is the completeness ratio. We observe that the spatial restriction allows for achieving the highest completeness ratio (21.43%).

Sch(R All ) = Sch(RT emp) = Sch(Loc) ∪ Sch(Cal)

Pattern table generation

We perform a preliminary experiment to verify the effectiveness of patterns in terms of compactness and the efficiency of Algorithm F oldData. The compactness of a pattern table P is defined by the ratio |P |/|D| between the size of P and the size of its data table. We consider all combinations of datasets and references and report the results in Table 8. Observe that using a more precise reference (spatial restriction) leads to decreasing execution time for Temp and T OneMon due to reduced completeness check time. The results also confirm that the reference choice impacts the dataset completeness and is a determinant factor for the execution time.

Variability analysis. Since the compactness of a pattern table plays a major role in the performance of the query result explanation process, we investigate the problem of determining which dataset features lead to high compactness. We examine three features : (i) distribution of completeness, (ii) dataset completeness and (iii) dataset size. We use in this experiment both the real-world dataset and the synthetic one which is obtained by randomly inserting or deleting measures starting from real-world dataset.

In both cases, we generate a series of datasets, by increasing and decreasing the completeness ratio. Starting from datasets with a fixed completeness ratio, we build two series of datasets: one obtained by successively inserting tuples from the reference until reaching full completeness, another one obtained by successively deleting its tuples until reaching emptiness. The insertion and deletions follow two strategies: i) a sequential strategy which selects the (inserted or deleted) tuples using their spatial and temporal domain order preserving the original data distribution and which we call real distribution, and ii) a random strategy which picks these tuples in a random fashion, we call simulated distribution. compactness of a random dataset with 30% completeness evolves symmetrically in both directions (insertion and deletion): successive insertions/deletions generate/remove tuples which give raise to new patterns. At some point, these insertions/deletions will cause the merging of fine-grained patterns to coarser-grained ones increasing the compactness ratio to achieve maximum compactness at both extremities. In the real datasets we observe the same trend with a lower amplitude for a dataset with 50% initial completeness: insertions lead to a faster completion of the partial partitions (thanks to order sensitive updates) and thus to faster derivation of coarser patterns without deriving all their subsumed patterns.

Finally, notice that the completeness distribution is a direct factor impacting compactness. Different completeness ratios lead to variable pattern numbers, the more a dataset is complete, the fewer the patterns.

Performance. In the following experiment we evaluate the performance of algorithm F oldData. From the original dataset Temp, we derived 30 datasets grouped into three categories, each with approximately the same completeness rate, but different dataset sizes. Figure 5 shows the running time of F oldData for all datasets according to the number of generated patterns. Categories are represented by points of different colors (orange = 15%, violet = 10% and green = 3% completeness rate). Notice that execution time is not im-

Pattern Query Processing

The following experiment measures the efficiency of processing pattern queries for producing minimal covers for queries over constrained tables. We compare the patternbased query plans (blue solid path in Figure 2) using the techniques described in Section 5 by comparing it with the "naive" strategy of computing the minimal cover from the results of the query applied to the data and reference tables (red dashed path in Figure 2). We tested both approaches on the queries below and report the result in Figure 6. Assessing the completeness of queries using pattern algebra outperforms the naive approach for all of the tested queries. For Q1 and Q2 efficiency is obtained by exploiting the fact that both queries use only the spatial reference (reference independence). For Q3, where the gain is less important, partial unfolding over both reference tables incurs some overhead while remaining reasonably low. Queries Q4 and Q5 need no unfolding which explains their performance gain with respect to the naive solution. For Q5, patternbased evaluation is much more efficient because of the pattern cover compactness (11K tuples). Note also that this particular pattern query doesn't need unfolding, in contrast with Q4. We observe the same trend with join query Q6 (not shown in the figure) which takes 31 seconds to be executed and where the pattern algebra query only takes 7.9 seconds. The pattern join implies a partial unfold on attribute b with a small number of values (96b) and generates a small number of patterns which have to be refolded.

Folding pattern query results. The last experiments set aims at digging deeper in the efficiency of pattern queries by analyzing the overhead of F oldP atterns. We consider different pattern table sizes,to minimize. Running the F oldP atterns algorithm produces pattern minimal covers with variable compactness values (see Table 9). We report the F oldP atterns phase execution time while keeping track of the exact number of merge and reduce operations (see section 5.3).

As expected, the running time grows with the number of patterns to minimize and merging patterns is much more expensive than reducing patterns which is a purely syntactic operation.

CONCLUSION

In this paper, we presented a pattern-based approach for representing and summarizing relative completeness information. We proposed a formal model and characterized a powerful reasoning mechanism for inferring and analyzing exhaustive sets of completeness statements about data and query answers. We validated our approach experimentally and confirm the efficiency of the pattern algebra and its usefulness in evaluating query completeness and correctness.

Extending the model with statistical information about data completeness is a challenging future direction. A natural extension under study is the use of a map-reduce platform like Apache Spark [START_REF] Zaharia | Apache spark: a unified engine for big data processing[END_REF] to compute minimal pattern covers and implement the pattern algebra. Developing an interactive tool for reasoning on patterns is an interesting application that we are considering.

  E ) fl ro we * * w1 f2 * * f1 r1 * Q2(P E ) fl ro we * r2 w2 f1 r1 *

  Q complete : s e l e c t f l , ro , we , sum(kWh) as kWh, ' ok ' as annot from Energy d natural j o i n P p where ( d . f l = p . f l or p . f l = ' * ' ) and ( d . r o = p . r o or p . r o = ' * ' ) and ( d . we = p . we or p . we = ' * ' ) and p . da = ' * ' group by f l , ro , we

Definition 5 .

 5 The instance I(p, S) of a pattern p in some table S is the subset of tuples t ∈ S which are specializations of p. The instance I(p, S) of a pattern p = [a1 : v1, a2 : v2, ..., an : vn] in some table S can be computed by a relational selection I(p, S) = σ cond (S) with filtering condition cond = (ai = p.ai ∨p.ai = * ). It is then easy to show the following properties of pattern instances: • I([ * ], S) = S; • I(p, I(p, S)) = I(p, S); • S ⊆ S ⇒ I(p, S) ⊆ I(p, S ). The notion of instance can naturally be extended from patterns to pattern tables P and constrained tables T = (D, R): I(P, S) = p∈P I(p, S) and I(p, T ) = (I(p, D), I(p, R)

Figure 1 :

 1 Figure 1: Labeled completeness pattern lattice.

P

  fl ro we da * * w1 * f2 * * * f1 r1 * Mon {f l} (P, R) fl ro we da f1 * w1 * f2 * w1 * f2 * * * f1 r1 * Mon

Example 7 .

 7 Consider the pattern table P below. P fl ro we da f2 * * * f1 r1 * Mon * r1 w1 * * r2 w1 * Observe that • σro= * (P ) = {[f 2, * , * , * ]}, • G(ro) = {[f 1, r1, * , M on]} and • G(ro) = {[ * , r1, w1, * ], [ * , r2, w1, * ]} and thus {[ai : * ]} × π¬a i (G(ai)) = {[ * , * , w1, * ]}.

Algorithm 1 : 2 X 6 P

 126 Algorithm F oldData Data: constrained table T = (D, R), attribute set A Result: minimal cover P * (T ) 1 P := ∅ ; for level := 0 to |A| do := ∅ ; 3 for B ∈ powerSet(A, level) do 4 for p ∈ patterns(B, D) do 5 if checkComp(p, D, R) then := P ∪ {p} ; X := X ∪ {p} ; 7 prune(X , D) ; 8 return P F oldData explores (almost) the whole pattern lattice LD that is generated by all attribute/value combinations in the data table

2 S level = ∅ 3 for 6 S 9 P 10 S 11 P

 23691011 p ∈ getP att(P, level) do 4 for a ∈ getConstAttrs(p) do 5 pa i : * := gen(p, a) := getSimP att(P, p, a) 7 if pa i : * / ∈ P then 8 if checkComp(S, pa i : * , T, R) then := P ∪ {pa i : * } level := S level ∪ S := P -S level 12 for level1 := 0 to |A| do 13 for p1 ∈ getP att(P, level1) do 14 for level2 := level1 + 1 to |A| do 15 for p2 ∈ getP att(P, level2) do 16 if isGen(p1, p2) then 17 P := P -{p2} 18 return P In the worst case, the reduce step generates O(|P | 2 ) generalization tests. Similar to the top-down algorithm F oldData, the size size(LP ) of the pattern lattice LP explored by the merge step can be estimated by size(LP ) = n i=1 (C i n ) * Di where n is the number of attributes, and Di is the maximum size of the Cartesian product of the active domain of i attributes in the pattern table

Figure 3 :Figure 4 :

 34 Figure 3: Synthetic datasets : Data missing randomly

  Figures3 and 4depict the evolution of compactness w.r.t. completeness for each distribution and each of the synthetic dataset. In the synthetic datasets (Figures 3), the compactness of a random dataset with 30% completeness evolves symmetrically in both directions (insertion and deletion): successive insertions/deletions generate/remove tuples which give raise to new patterns. At some point, these insertions/deletions will cause the merging of fine-grained patterns to coarser-grained ones increasing the compactness ratio to achieve maximum compactness at both extremities. In the real datasets we observe the same trend with a lower amplitude for a dataset with 50% initial completeness: insertions lead to a faster completion of the partial partitions (thanks to order sensitive updates) and thus to faster derivation of coarser patterns without deriving all their subsumed patterns.Finally, notice that the completeness distribution is a direct factor impacting compactness. Different completeness ratios lead to variable pattern numbers, the more a dataset is complete, the fewer the patterns.

Figure 5 :

 5 Figure 5: F oldData performance

Figure 6 :

 6 Figure 6: Pattern algebra performance

  Q1: σ b=2223 (T emp) Q2: σ b=2223∧f =1 (T emp) Q3: σ b=2223∧(m=11∨m=12) (T emp) Q4: π b,f,r,y,m,d (T emp) Q5: π f,r,m,d (T emp) Q6: T emp 1 b Elec

Table 1 :

 1 Reference tables

	MAP fl ro f1 r1 f1 r2 f2 r1	CAL we w1 w2	×	da Mon Tue

Table 2 :

 2 Data table P E capturing the available and the missing information of table Energy respectively. More exactly, table P E contains pattern tuples that capture all partitions which are complete w.r.t. the reference. For instance, pattern tuple p0 indicates that all measurements pertaining to week w1 are available, whatever the values of floor, room or day are. Pattern p3 in table P E

	Energy fl ro we da	kWh
	t0 f1 r1 w1 Mon 10
	t1 f1 r1 w1 Tue 12
	t2 f1 r1 w2 Mon 10
	m0 f1 r1 w2 Tue ⊥
	t3 f1 r2 w1 Mon 8
	t4 f1 r2 w1 Tue 10
	m1 f1 r2 w2 Mon ⊥
	m2 f1 r2 w2 Tue ⊥
	t5 f2 r1 w1 Mon 12
	t6 f2 r1 w1 Tue 7
	t7 f2 r1 w2 Mon 8
	t8 f2 r1 w2 Tue 8

Table 3 :

 3 Completeness pattern tables of Energy

	P E fl ro we da p0 * * w1 * p1 f2 * * * p2 f1 r1 * Mon	P E fl ro we da p3 * r2 w2 * p4 f1 r1 * Tue

Table Q1 (

 Q1 P E ) and table Q1(P E ): Q1 produces a complete answer for floor f 2 while the first tuple in Q1(P E ) indicates that no answer is returned for room r2 during week w2:

	Q1(P E ) fl ro we da	Q1(P E ) fl ro we da
	f2 * * *	* r2 w2 *
	f1 r1 * Mon	f1 r1 w2 Tue

Table 4 :

 4 Annotated Query Answer

	Result Q2 fl ro we kWh annot
	f1 r1 w1 22	ok
	f1 r1 w2 10 incorr
	f1 r2 w1 18	ok
	f2 r1 w1 19	ok
	f2 r1 w2 16	ok

table

  EnergyWeek, with the table Surface, which contains the surface of room r1 on both floors. S ) of Q3 can be generated by joining the pattern table Q2(P E ) and the pattern table P S of table Surface.

	P S fl ro * r1	Q3(P E , P S ) fl ro we * r1 w1 * r1 w1

Q3 : s e l e c t f l , ro , we , kwh/M2 as kWh m2 from EnergyWeek natural j o i n Surface ;

In this case, the completeness pattern table

Q3

(P E , P

  Table R is called a reference table for data table D with reference attributes A and the pair T = (D, R) is called a constrained table. Observe that any table S(A, M ) with key A and with null values for attribute M can be decomposed into a constrained table ∆(S) = (D, R) where measure table D ⊆ S contains all tuples in S without null values and R = πA(S) contains all key values in S. Similarly, we can build from any constrained table T

Example 1. The Cartesian product MAP × CAL of tables MAP and CAL in Table 1 is a reference table of Energy with reference attributes A = {f l, ro, we, da}.

  ). The following definition relates constrained tables to pattern tables: Definition 6. A constrained table T = (D, R) satisfies a completeness pattern p, denoted by T |= p, if I(p, R) ⊆ I(p, D). A constrained table T satisfies a completeness pattern table P if T satisfies all patterns in P . It is easy to show that a constrained table T is complete if it satisfies wildcard pattern [ * ]. Definition 7. A pattern p2 subsumes a pattern p1, denoted by p1 p2, if for all constrained tables T : T |= p2 ⇒ T |= p1. In the following, we define several properties and relationships connecting pattern tables to constrained tables which are necessary to define the final notion of minimal pattern cover. Definition 8. A pattern table P covers a constrained table T iff for all patterns p satisfied by T there exists a pattern p ∈ P subsuming p. Example 3. Pattern table P E in Table 3 covers the constrained table T = (Energy, MAP × CAL).When replacing p0 = [ * , * , w1, * ] by two patterns pa = [f1, * , w1, * ] and p b = [f2, * , w1, * ] this is not true anymore, since pattern p0 = [ * , * , w1, * ] is satisfied by T but not subsumed by any pattern in P -{p0} ∪ {pa, p b }.

	Proposition 1. p1 p2 if and only if p1 is a specializa-
	tion of p2. (see proof in the Appendix)

Observe that a pattern table P covering a constrained table T is not necessarily satisfied by T . In particular, any pattern table containing the universal pattern covers all constrained tables T . Definition 9. A pattern table P strictly covers a constrained table T if P covers T and P |= T . Definition 10. A pattern table P is reduced if there exists no pair of distinct patterns p ∈ P and p ∈ P such that p is a generalization of p . Proposition 2. For each constrained table T , there exists a unique reduced strict cover P * (T ) called the minimal pattern cover of T . (see proof in the Appendix) Example 4. Pattern table P E in Table 2 is the minimal pattern cover of constrained table T = (Energy, MAP × CAL).

Table 5 :

 5 A pattern table and its complement

	P A B C
	a2 * *
	a1 b1 *
	* b1 c1
	a1 b3 c2

  ). Algorithm F oldP atterns Data: pattern table P , reference table R, data table T , attribute set A Result: minimal cover P * (I(P, R)) 1 for level := |A| to 0 do

	Algorithm 2:

Table 6 :

 6 Size of reference tables R all and RT emp variant x |Locx| |Calx| |Rx| = |Locx| × |Calx|

	all 10,757 8,760	94,231,320
	T emp 2,810 8,760	24,615,600

Table 7 :

 7 Sizes and completeness ratio.

	dataset ds	|ds| CR(ds, R ds all ) CR(ds, R ds T emp )
	Temp 1,321,686	1.4%	5.36%
	T OneBlg 341,640	21.43%	21.43%
	T OneMon	88,536	1.4%	4.23%

Table 8 :

 8 Pattern derivation: preliminary results.

	Execution Time (sec)

Table 9 :

 9 Pattern Fold algorithm performances P. size Pmin.size Compac. time merges /reduces

	106	22	20.75% 0.29s	7 m
	238	32	13.44% 0.32s	9m+ 79 r
	570	30	5.2%	0.38s	45m
	992	864	87%	0.47s	6 m + 32 r
	10961	3921	35.77% 1.33s 6 m + 7040 r
	11285	11178	99.01% 0.35s	107 r
	12054	11440	94.90% 6.59s 38 m + 158 r

Remind that since P is a strict cover I(P, R) ⊆ D.

APPENDIX

A. PROOFS Lemma 6. p1 p2 ⇒ ∀S : I(p1, S) ⊆ I(p2, S)

Proof. We show that if there exists a table S where I(p1, S) ⊆ I(p2, S), then p1 p2. For showing p1 p2, we define a constrained table T = (D, R) such that I(p2, R) ⊆ I(p2, D) and I(p1, R) ⊆ I(p1, D). Let R = S and D = I(p2, R). Then, I(p2, D) = I(p2, I(p2, R)) = I(p2, R) (by idempotency). Now we have to show that I(p1, R) ⊆ I(p1, D). Based on the initial assumption I(p1, S) ⊆ I(p2, S) and S = R we conclude I(p1, R) ⊆ I(p2, R) and it is sufficient to show that I(p1, D) ⊆ I(p2, R): I(p1, D) = I(p1, I(p2, R)) ⊆ I(p2, R) = I(p2, R).

Proof of Proposition 1. We first prove that if p1 p2 then p1 is a specialization of p2. Suppose that p1 is not a specialization of p2, i.e. there exists no mapping from p1 to p2 such that p2 can be obtained from p1 by replacing one or more constants by a wildcard. In other terms, there exists an attribute ai such that p2.ai = c is a constant and p1.ai = p2.ai. This is equivalent to the statement that cond(p1) contains a condition p1.ai = c which is not contained in cond(p2). Then it is easy to define a table S = {t} where t satisfies p1 but not p2 which leads to I(p1, S) ⊆ I(p2, S). On the other hand, by proposition 6, we know that p1 p2 implies ∀S : I(p1, S) ⊆ I(p2, S) (contradiction).

We now show that if p1 is a specialization of p2, then p1 p2. If p1 is a specialization of p2, then for all S, I(p1, S) = I(p1, I(p2, S)) (then filtering condition of p1 is subsumed by the filtering condition of p2). Then, if I(p2, R) ⊆ I(p2, D) we know by monotonicity of I that I(p1, I(p2, R)) ⊆ I(p1, I(p2, D)) which is equivalent to I(p1, R) ⊆ I(p1, D).

Proof of Proposition 2. By contradiction using the notion of cover and subsumption. Suppose that there exist two minimal strict covers P * (T )1 and P * (T )2. Then there exists a pattern p1 ∈ P * (T )1 -P * (T )2 and a pattern p2 ∈ P * (T )2 -P * (T )1 such that p1 p2 (otherwise P * (T )2 would not be a cover). Since p1 = p2 and by Proposition 1, we can conclude that p1 < p2. By Definition 8 there must exist a third pattern p 1 ∈ P * (T )1 such that p2 p 1 (otherwise P * (T )1 would not be a cover). Then, we obtain p1 < p2 p 1 where p1 and p 1 are two distinct patterns in P * (T )1 and p 1 subsumes p1. This is in contradiction with the claim that P * (T )1 is a minimal cover.