Count constraint is a data dependency that requires the results of given count operations on a relation to be within a certain range. By means of count constraints a new decisional problem, called the Inverse OLAP, has been recently introduced: given a flat fact table, does there exist an instance satisfying a set of given count constraints? This paper focus on a special case of Inverse OLAP, called Inverse Tree-OLAP, for which the flat fact table key is modeled by a Dimensional Fact Model (DFM) with a tree structure.
Emerging “Big Data” platforms and applications call for the invention of novel data analysis techniques that are capable to handle large amount of data. There is therefore an increasing need to use real-life datasets for data-driven experiments but, as pointed out in a recent ACM SIGMOD Blog post by Gerhard Weikum [13], datasets used into research papers are often poor. Companies have their own interesting data, and industrial labs have access to such data and real-life workloads; however, such datasets are often proprietary and out of reach for academic research. In order to ensure high quality experimental findings, inverse mining techniques can be applied to generate artificial datasets that reflect the patterns of real ones: the patterns are first discovered by data mining techniques (or directly provided by domain experts) and then used to generate “realistic” privacy-preserving datasets.
A promising and important example of inverse mining is Inverse Frequent itemset Mining (IFM), first stated in [9], which consists of finding a transactional database D satisfying given support constraints on some itemsets, which are typically the frequent ones. As an example, given the items a; b; c; d, the itemsets I1 = fa; bg; I2 = fb; cg and I3 = fc; dg, the support constraints I1 = I2 = 100 and I3 = 50, and a fixed database size equal to 170, a feasible transactional database D consists of the following (replicated) transactions: hfa; b; cg; 70i (i.e., there are 70 occurrences of the transaction fa; b; cg in D), hfb; c; dg; 10i, hfa; bg; 30i, hfb; cg; 20i and hfc; dg; 40i. Observe that the support constraint I1 = 100 is satisfied by D as there are 30 occurrences of I1 in D and I1 is a subset of fa; b; cg occurring 70 times in D – it is easy to see that the other support constraints are satisfied as well.
Count constraints have been used in [12] to define a new integrity constraint decisional problem: given a relation scheme and a number of count constraints on it, does there exist a relation instance satisfying the count constraints? The problem has been called Inverse OLAP because the typical relation scheme dealt with is a (flat) fact table, whose attributes are dimensions (i.e., properties, possibly structured at various levels of abstraction) – no measure attributes are considered as the only aggregation operator is the count. We recall that a flat fact table can be represented as a star schema with additional tables for storing dimensions or a snowflake schema, which includes additional dimensional tables describing dimension hierarchies. This kind of fact table is called a factless fact table [7] and it arises in some scenarios storing many-to-many mappings in which no attribute qualifies as a measure – typical cases are event records, where an event is given by a combination of simultaneously occurring dimensional characteristics.
Inverse OLAP has a potential high relevance in synthesizing data cubes having predefined characteristics to be used in benchmarks of novel techniques for handling big data. Inverse OLAP has been proved in [12] to be NEXP-complete under various conditions: data complexity (i.e, the number of attributes and the size of constraints are constant), program complexity (i.e, the domains are constant) and combined complexity.
We are not discouraged by the high complexity and in this paper we present a solution approach of the Inverse OLAP problem for the case of a flat fact table, called tree-fact table, whose schema is a special case of Dimensional Fact Model (DFM) of [5]: it is a tree (and not a graph as in the general definition) having dimension hierarchy levels as nodes and the “rolls-up-t” relationships between them as edges.
This paper is the short version of the paper [11], where we present the main results of our research. 2
In this section we define the Inverse Tree-OLAP problem. We assume that the flat fact table R has the following scheme (tree-fact table): R(B1; : : : ; Bn; S1; : : : ; Sn; M1; : : : ; Mm), where (B1; : : : ; Bn) is the table key (basic dimensions), Si, 1 i n, is a dimension hierarchy tree rooted on Bi, and M1; : : : ; Mm) are measures. We also assume that the all the once-to-many relationships in the subtrees S2; : : : ; Sn are stored as facts in ad-hoc additional domain tables (as in an ontology) whereas the first level of the one-to-many relationships in the subtree S1 are not. In addition we assume that all the dimension domains are given in suitable tables except for the basic dimension B1 (aggregating basic dimension), whose values are generated by means of a polynomial time function. Finally the values of measures are determined by means of a polynomial time function having the table key domains as range.
We make the following restrictions on the count constraints that can be applied to a tree-fact table: – Tree-Tuple Count Constraint: the table key fB1; : : : ; Bng must be contained in
X [ Y, being X and Y suitable subsets of dimensions, respectively; – Tree-Tuple Count Constraint-B1: Y = fB1g, X is a subset of dimensions in the subtree S1 rooted at A1 and all other basic dimensions B2; : : : ; Bn as well as the ones in the corresponding subtrees S2; : : : ; Sn must be contained in Z, being Z a suitable subset of dimensions; – Tree-Group Count Constraint: W = B1, Y = fB2; : : : ; Bng while all other dimensions must be in Z (being Z a suitable subset of dimensions), i.e., they are existentially quantified.
Observe that Tree-Group Count Constraints define an IFM-like subproblem, whose very objective is to model how the values of the basic dimensions can occur together in a many-to-many relationship. Restrictions on Tree-Tuple Count Constraints avoid the problem of handling duplicates on table projections. In fact, the projected tuples are guaranteed to be distinct as the table key B1; : : : ; Bn is included in the set of selection / projection attributes. The problem of removing duplicates from table projections has been recognized in [1] as the critical step for checking satisfaction of cardinality constraints. As for Tree-Tuple Count Constraint-B1, distinctness of projected tuples will be guaranteed by our solution approach that group the tuples by the aggregation basic dimension.
We are now ready to define the specialization of Inverse OLAP.
Inverse Tree-OLAP Problem. Given a tree-fact table R on a DFM D and a set of 2D count constraints C, the Inverse Tree-OLAP problem consists of deciding whether there exists a relation r on R such that r j= C [ F , where F are the functional dependencies corresponding to D. 2
The next result shows that the (both data and combined) complexity of Inverse TreeOLAP remains NEXP-complete.
Proposition 1. Inverse Tree-OLAP is NEXP-complete.
PROOF (sketch). Membership to NEXP derives from the fact that Inverse OLAP is in NEXP and Inverse Tree-OLAP is a specialization of Inverse OLAP. Actually satisfaction of FDs is not explicitly required in the general Inverse OLAP formulation as possible FDs are expressed as count constraints. Checking FDs can be obviously done in time polynomial in the size of a problem certificate and, therefore, the complexity remains in NEXP. To prove NEXP-hardness, it is sufficient to show that any instance x of IFMI can be transformed in logarithmic space into an instance x0 of Inverse Tree-OLAP, such that x is a YES-instance for IFMI if and only if x0 is a YES-instance for Inverse Tree-OLAP. We shall give some intuition on this part of the proof in the example below. 2
Observe that NEXP-completeness only depends on the presence of Tree-Group Count Constraints. The fact that Tuple Constraints do not have high complexity is due to our restrictions that produce table projections without duplicates.
To get an intuition of our approach, consider a tree-fact table R(S; W; B; C; R; T ; L; A; G; P ) modeling a classical example of point-of-sales transaction application. Recall that the dimensions are: S (Sale), W (Ware), B (ware Brand), C (sale Customer), R (customer Ranking), T (customer Town), L (sale Location), A (sale Area) and G (ware Group). The basic dimensions are S; W and B and S is the aggregating one. There is a unique measure: P (item Price), where an item is a pair ware-brand and its price may vary from one location to another. Then the value of P is univocally determined by the values of L, W and B – we assume that the function returning the price value is suitably stored to be used after a feasible solution has been produced. The domains of the dimensions, denoted by DS , DW and so on, are given and they are finite tables; however, DS is not explicitly stored but the values are generated as needed.
The prefixed one-to-many relationships are given and stored into the tables: DW G, DLA, and DCT . The other one-to-many relationships are not predefined.
A domain table DfW Bg 1 2 stores a number of predefined itemsets (i.e., sets of items) and a range of admissible supports 1 2 for each of them. There are additional tables: DGA 1 2 storing the admissible numbers of ware groups that must be assigned for location areas, DBR 1 2 storing the admissible numbers of brands that must be sold to all customers of each ranking and DR !1!2 storing the admissible numbers of regions that must be interested to all customers of each ranking. Observe that the minimum value !1 for the lowest ranking is 0.
Enforcing the total number of sales
true ! s1
#(fS : R(S; w; b; c; r; t; l; a; g; p)g)
s2
where low letters represent existentially quantified variables and s1; s2 with s1 s2 are
two non negative integers, denoting respectively the minimal and the maximal number
of sales in a feasible solution. Constraint (
DfW Bg 1 2 (X; 1; 2) !
1
#(fS : X
fW B : R(S; W; B; v)gg)
2
(
Y =fW B : DW (W )
Y 6 X ! #(fS : X
DB(B)g ^ DfW Bg 1 2 (X ; 1; 2) ^
fW B : R(S; W; B; v))gg) where is a non negative integer denoting the infrequency support threshold. Constraint 3 is a Tree-Group Count Constraint that enforces that all itemsets that are not a (not necessarily proper) subset of some itemset in DfW Bg 1 2 must have a support below the threshold .
We point out that Constraints (
DGA 1 2 (G; A; 1; 2) ! 1 #(fS W B : R(S; W; B; c; r; t; l; A; G; p)g) 2:
This Tree-Tuple Count Constraint fixes the number of wares of each group that must be sold to all locations of a given area.
DL(L) ! 1 #(fS : R(S; W; B; v)g) 2: where v has been defined above and 1; 2 with 1 2 are two non negative integers denoting the same distribution range for all locations. This is a Tree-Tuple Count Constraint-B1.
Assigning brands to rankings
(
#(fW B : R(S; W; B; v)g) where is a positive integer denoting the maximal transaction length. Constraint 5 is a Tree-Tuple Count Constraint.
We next define a number of additional Tree-Tuple Count Constraints (including type B 1) that involve also non-basic dimensions.
many relationship from G (ware Group) to W (Ware), defined by DW G. The following Tree-Tuple Count Constraint:
DW (W) ^ DS(S) ^ DB(B) ! #(fG : R(S; W; B; c; r; t; l; a; G; p) ^ :DW G(W; G)g) = 0: excludes the possibility that any ware can take a group value different from the one that has been fixed in DW G. Observe that we have slightly modified the notation inside the function # by enabling a conjunction of the fact predicate with domain predicates – the semantics of this extension is obvious.
We add similar constraints for all other prefixed one-to-many relationships: from L (sale Location) to A (Area), from C (Customer) to T (Town) and from C to R (customer Ranking).
Enforcing the total number of tuples in the fact table
true ! s3
#(fS W B : R(S; W; B; v)g)
s4
where s3; s4 with s3 s4 are two non negative integers, denoting respectively the
minimal and the maximal cardinality of a feasible fact table instance. Constraint (
DB R 1 2 (B; R; 1; 2) ! 1 #(fS W B : R(S; W; B; c; R; t; l; a; g; pg) 2:
This is a Tree-Tuple Count Constraint.
DR !1!2 (R; !1; !2) !
!1
#(fS : R(S; w; b; c; R; t; l; a; g; p)g)
!2:
(
In this section we present a method for finding an approximate solution of the Inverse Tree-OLAP. Given a instance x of the Inverse Tree-OLAP: 1. Construct an instance y of IFMI using Tree-Group Count Constraints and possible Tree-Tuple Count Constraints (also in the variant B1) for which all non-basic dimensions are existentially quantified. Any itemset is a set of (n 1)-tuples on the basic dimensions B2; : : : ; Bn that share the same value for the aggregating basic dimension B1. 2. Solve y using the algorithm of [6] – let D be the transaction database computed by the algorithm, where a transaction is a set of items and each item is an element of B2 Bn. 3. Represent the database D as a set of triples (t; Z(t); (t)), where Z(t) is an itemset occurring in D, (t) is the number of its duplicates in D and t is an identifier for the itemset Z(t). Note that t is not a value in the domain of the aggregating basic domain B1 but it represents a group of (t) distinct values for B1. 4. Represent an instance r of the relation R by means of variables as follows: for each (t; Z(t); (t)), introduce variables x^b1b2:::bnd, where b2 : : : bn d are all admissible values for B2; : : : ; Bn, d is the list of all possible values for non-basic domains that are not determined by the prefixed one-to-many relationships and ^b1 represents the portion of t duplicates that are assigned to the values of the other subscript indices. Observe that this representation can be seen as a chase, which is a finite “canonical” database, witnessing the satisfiability of integrity constraints [2]. 5. Use the Tree-Tuple Count Constraints and Tree-Tuple Count Constraints-B1 involving non-basic dimensions to compute the variable values. To this end, we use linear equations that are solved using a linear program whose objective function is the cost of violating the above constraints. 6. Generate a flat table starting from the computed variable values by including the values for non-basic domains that are determined by the prefixed one-to-many relationships and by computing the measure values.
For presentation sake, we next illustrate our method by referring to the example described in Section 2.
As already mentioned, constraints (
D(I)
I max 8I 2 S0 : D(I) size1 jDj
size2:
8I 2 BS0 : D(I)
0
0
(
The inverse frequent itemset mining problem with infrequency constraint (IFMI) on I, S, , 0 and size consists of finding a database D over I such that the following conditions hold (or of eventually stating that there is no such a database):
By the anti-monotonocity property, constraints (
An instance of IFMI is constructed by fixing: I = fhw bi j DW(w) DBbg, = f(X; 1; 2) j DfW Bg 1 2 (X; 1; 2)g, 0 = (see constraint 3), size1 = s1 and size2 = s2 (see constraint 1). It is then straightforward to derive S and BS0 .
For the solution of the IFMI instance, we adopt the approach of [6]. The instance is represented as an integer linear program with a linear number of constraints (corresponding to the support constraints of the itemsets in S [ BS0 and to the two database size constraints) and an exponential number 2n of variables xj , one for each possible transaction Ij , indicating to number of its occurrences in the database. The program is represented in a succinct format with size O(n (m + m0)) – recall that a succinct problem is a problem whose instances are not given straightforward, but are themselves encoded using an a concise input with size logarithmic in the actual input size [10]. Then the integer constraint on the variables xj are relaxed so that an approximate solution is obtained by solving a linear program. Because of the exponential number of variables, the column generation algorithm (see e.g [4]), which is a version of the simplex dealing with a large number of variables (large-scale linear programs). This method solves a linear program without explicitly including all columns (i.e., variables), in the coefficient matrix but only a subset of them with cardinality equal to the number of rows (i.e., constraints). Columns are dynamically generated by solving an auxiliary optimization problem called the pricing problem.
Observe that constraints (
The algorithm returns a transaction database D that is an approximate solution of the problem. The database D is represented in a succinct format: (s^; Z; ), where Z is an itemset occurring in D, is the number of its duplicates and s^ is an identifier for Z. We stress that s^ is not a sale value in DS as the itemset Z will be eventually assigned to distinct sale values. Let S^ the set of all identifiers s^. For each s^ 2 S^, (s^) denotes the duplicate number for s^, Z(s^) is the itemset Z.
So far we have implemented steps (
To make the computation effective, we relax the integer constraint on all variables; so they are defined on the domain of non-negative rational numbers. We introduce the following equations:
X xs^wblc = (s^) l2DL;c2DC xs^wblc =0
8s^ 2 S^ 8 hw; bi 2 Z(s^) 8s^ 2 S^ 8l 2 DL 8c 2 DC 8 hw; bi 2 (DW DB) n Z(s^)
Equation (15) states that, fixed a transaction z^ and any item hw; bi of Z(S^), the sum of all assignments of the item to all possible locations and customers must be equal to the duplicate number (s^). On the other hand, equation 16 enforces that xs^wblc = 0 whenever the item hw; bi i is not part of any transaction s^.
Let us now implement step (
Constraints (
X
xs^wblc 8s^ 2 S^ 8c : DCR(c; r) 8w 2 DW : hw; bi 2 Z(s^)
X
xs^wblc 8s^2S^ 8hw;bi2Z(s^) 8c: DCR(c;r) 2 br 2 !2r 8g 2 DG 8a 2 DA where ( 1br; 2br) and (!1r; !2r) are the pairs such that DBR 1 2 (b; r; 1gr; 2gr) and DR !1!2 (r; !r; !2r) are true.
1
Obviously equations (15)–(20) can be solved in time polynomial in the domain sizes. Nevertheless, there is a problem that must be dealt with: the equations could be too restrictive so that no solution exists. However, as we are interest in finding an approximate solution that has the minimal violation the problem can be solved by introducing two artificial variables for each equation. For instance, equation (18) is rewritten as: w1l + where w1l and w2l are non-negative artificial variables. We take the summation of all artificial variables as an objective function to be minimized. Therefore we obtain a linear program representation of the equation resolution problem. By solving the linear program we compute a solution minimizing the objective function – that is, the one with the minimal constraint violation.
We point out that the size of the linear program is not exponential as for the IFMI linear program but polynomial. Nevertheless, the number of both rows and columns may be large. So, a row-column generation approach can be adopted: at each iteration step, the pricing problem has to also decide which row must be eventually expanded.
Once solved the linear equation system, we have to perform the last task (
Inverse OLAP is the problem of deciding whether a given fact table satisfies a set of given count constraints [12]. In this paper we have defined a special case of this problem, called Inverse Tree-OLAP, for which the flat fact table key is modeled by a Dimensional Fact Model (DFM) with a tree structure. The count constraints define aggregation patterns to be respected by both the many-to-many relationship among the basic dimensions and the one-to-many relationships within dimension hierarchies.