Towards Efficient Metaquerying

1 Introduction

With the tremendous growth in information around us, datamining is emerging as a vital research area among the AI and Databases communities [Fayyad eta/., 1996]. Metaquerying [Shen, 1992; Wei-Min Shen and Zaniolo, 1996] is a very promising approach for datamining in re­ lational or deductive databases. Metaqueries serve as a generic description of the class of patterns to be discov­ ered and help guide the process of data analysis and pat­ tern generation. Unlike many other discovery systems, patterns discovered using metaqueries can link informa­ tion from many tables in databases. These patterns are all relational, while most machine-learning systems can only learn propositional patterns.

Metaqueries can be specified by human experts or al­ ternatively, they can be automatically generated from the database schema. Either way, they serve as a very important interface between human "discoverers" and the discovery system.

Ehud Gudes Mathematics and Computer Science Ben-Gurion University of the Negev Beer-Sheva Israel ehud@cs.bgu.ac.il

A metaquery R has the form

where T and L; are literal schemas. Each literal schema L; has the form Q;(Yl> ... , Yn;) where all non-predicate variables Y~: are implicitly universally quantified. The expression Q;(Y1 , ... , Yn;) is called a relation pattern. The right-hand-side £1 , ... , Lm is called the body of the metaquery, and T is called the head of the metaquery. The predicate variable Q; can be instantiated only to a predicate symbol of the specified arity n;. The instan­ tiation must be done in a way which is consistent with the variable names.

For example, suppose that you have a database having the relations depicted in Figure 1. Let P ,Q, and R be variables for predicates, then the metaquery

specifies that the patterns to be discovered are transitiv­ ity relations

where p,q, and r are specific predicates. One possible result of this metaquery on the database in Figure 1 is the pattern

which means intuitively that if a student takes a course from a certain department then he must be a student of that department .

1.1 The notion of support and confidence for metaqueries

Sup~ose that we are given the metaquery (2) again, but mstead of the relations shown in Figure 1, we have the relations shown in Figure 2 (the relation course­ department is the same as in Figure 1).

The rule (3) doesn't hold in all cases anymore. But we can say that it holds in 75% of the cases, or in other words, that it has confidence 0.75.

Let us now consider another set of relations from an employee database of an Israeli high-tech company hav­ ing 1000 employees. The company is located in Beer­ Sheva, and all the employees except Ana live in Beer­ Sheva. Ana lives in Kibutz Shoval near by. None of the employees, except Guy, where born in the area. Guy was born in Kibutz Shoval and Ana is the boss of Guy.

Now suppose that we pose the following metaquery:

An answer to this metaquery can be:

with confidence 1.0. So we are going to learn the rule that if an employee was born in some place and a sec­ ond employee lives in that same place, then the first employee must be the boss of the second. This rule is useless because it is based on a very weak evidence two people out of the 1000 who work in this company. Rules in which the rule body is satisfied by only a very low fraction of the relations involved should be avoided or . , m other words, we would like rules with high support.

Hence, each answer to a metaquery is a rule accom­ panied by two numbers: the support and the confidence. The threshold for the support and confidence is provided by the user. Intuitively, the support indicates how fre­ quently the body of the rule is satisfied, and the confi­ dence indicates what fraction of the tuples which satisfy the body also satisfy the head. Similar to the case of association rules, the notions of support and confidence have two purposes: to avoid presenting negligible infor­ mation to the user and to cut off the search space by early detection of low support and confidence.

Formally, given a rule

let J denote the relation which IS the equijoin of r1, .. . , rm, and let Jt be the relation which is the equijoini of J and t . Where y and x are some relations, let Y:r:, be the projection of y over the fields which are common to y and x, and let lx I be the number of tuples in x. For each i, i = l...m define S; to be the fraction 1 (;/ 1 1 · The sup­ port of the rule (6) is the maximum overS;, i = l...m. Less formally, the support is the maximum fraction of any relation r; in J . The confidence of ( 6) is the fraction oft that appears in J, or, formally, the confidence of (6) is IIW·

The support that we have defined has the following useful property:

Claim 1.1 For any two relations r; and ri in the rule {6) that have at least one common attribute variable, S; is not bigger the the fraction of r; that participates in the equijoin between r; and ri.

This property enables us to get an upper bound on the support of the rule (6) by performing pairwise equijoins instead of equijoin of all the relations in the body of the rule.

Shen et al. [Wei-Min Shen and Zaniolo, 1996] are to best of our knowledge the first who have presented a framework that uses metaqueries to integrate inductive learning methods with deductive database technologies. The confidence measure that we use is similar to the one used by Shen et al. . However, we do not agree with their definition of support, and hence developed our own. According to Shen and Leng [Shen and Leng, 1996], the support (called "base by Shen and Leng) should be the fraction rrd~I 1 L,j . We believe that our definition of sup­ port reflects better its intuitive meaning. Consider again the students database of Figure 1, and suppose that there are 100,000 tuples in the relation student-course and 1000 tuples in the relation course-department. Ac­ cording to Shen and Leng, the support for the rule (3) "ll b 106 I . . WI e IQ8 = 1000 . The support will shrmk even more as the number of courses grow, no matter how many students are in the relation student-course. This low support will render the rule (3) uninteresting, although this rule involves all the tuples in the relation student­ course. Note that according to our definition, the sup­ port for this rule is 1.0, because there is one relation, student-course which participate in the equijoin of the body of The rule in full capacity.

2 Complexity

How hard is answering a metaquery? In this section we will show that the computation task is NP-Hard. First, let us rephrase the problem as a decision problem.

Definition 2.1 (The MQ Problem)

Instance: A database VB and a metaquery M Q of the form {1).

1 The equijoins are accomplished by enforcing values of attributes that are bound to the same variable name in the metaquery to be equivalent.

Question: Are there relations q1, ... , qm, t in VB such that the rule T +-- £1, ... , Lm holds with support and confidence greater than 0 when we replace T by t and each Q;, i = 1, ... , m by q;.

Theorem 2.2 The MQ problem is NP-Hard.

Proof: We will show a reduction from HAMILTO­ NIAN PATH (HP) to the MQ problem. We remind the reader that the HP problem is as follows [Garey and Johnson, 1979]: given a directed Graph (V, E), deter­ mine whether there is a path in the graph by which each vertex is visited exactly once. So suppose we are given a graph G = (V, E). We will construct a database VB and a metaquery MQ as follows. VB will have two relations: Rv and R£. Rv contains exactly one tuple, which is the list of all vertices in V, and RE is the set of all edges in E, that is:

M Q will be the following metaquery:

We claim that the answer to the MQ problem composed of the above VB and MQ will be "YES" iff there is a Hamiltonian path u1 , u2 , ... , Un in G. And indeed, if there is a Hamiltonian path in G, then the rule

Holds with support > 0 and confidence > 0, and so the answer to the given MQ problem will be ''YES". On the other hand, if the answer to this MQ problem is YES, then, since we require that the support and confidence be positive, and since Rv has only one tuple and RE is the only binary relation, it must be the case that there is a Hamiltonian path in G. ·

It is worthwhile to mention a tractable subset. If the database scheme is fixed in advance, and we do not al­ low a predicate variable to appear more than once in a query, then the number and maximum size of all possi­ ble different metaqueries is a constant. In this case every metaquery has a constant number of instantiations and hence can be answered by a join of a constant number of relations.

The reader might wonder whether the complexity analysis done on inductive logic programs (e.g. [Dze­ roski et al., 1992]) is relevant here. The answer is no. In inductive logic programming the goal is to construct a program that will generate a given goal relation out of other relations and positive and negative examples. Here, we are interested in finding to what extent some rule on given relations and goal relation holds. We don't have to find a rule that accurately generates the goal relation, and we do not have negative examples.

Instantiate(SR)

• Input: SR: a set ~, Rt, ... , Rn of relation patterns, par­ tially instantiated, each with a set of constraints Co, ... , Cn. Initially the constraints sets are all empty.
• Output: Relations rO, rl.. .rn that match the relation patterns in SR with the variables bound to at­ tributes.
• If SR is completely instantiated then return SR.
• Pick the next uninstantiated relation variable R; from SR, {here we should use CSP variable ordering techniques to choose}
• Pick up the next possible instantiation r to R; ( r should meet the constraints in C; and should be of the same arity as R;). {here we should use CSP value ordering techniques to choose}
• For each relation pattern R; not yet instantiated do:
• if R; has a common field variable X with R; , add to the C; the constraint that X must be bound to an attribute with type Tx, where Tx is the type of the attribute that X is bound to in r.
• Call Instantiate recursively.

Figure 3: Algotithm for the instantiation stage

3 Efficient Algorithms for Metaqueries

In this section we discuss the algorithms for generating all rules resulting from a given metaquery.

The process of answering a metaquery can be divided into two stages. In the first stage, which we call the in­ stantiation stage, we are looking for sets of relations that match the pattern determined by the metaquery. In the second stage, which we call the filtration stage, we filter out all rules that match the pattern of the metaquery but do not have enough support and confidence.

3.1 The instantiation stage

The process of instantiating a metaquery is similar to solving a Constraint Satisfaction problem (CSP) [Dechter, 1992] where we are basically looking for all solutions of the CSP problem. In our experiments we used a very simple CSP algorithm (forward checking with Back-jumping [Dechter, 1990]) but other more ad­ vanced algorithms may be used.

The basic instantiation algorithm is shown in Figure 3. If this stage suceeds, at the end of this stage each relation pattern R(X1, ... ,Xn) that appear in the metaquery is instantiated. That is, R is bound to some relation name r and each variable is bound to an attribute (''field") of the relation. We assume that a procedure att( r, X) can return the attribute in r to which the variable X is bound.

3.2 The filtration stage

The filtration stage itself is composed of two steps: fil­ tering out rules with low support, and filtering out rules with low confidence. We compute confidence only for rules with sufficient support. In our research we have focused so far on algorithms for computing support. We will discuss three alternatives:

• The Join approach the straightforward way: com­ puting the equijoin of the body of the rule, then computing S1 (Sa as defined in section 1.1) for each relation in the body, and then taking the maximum.
• The histogram approach Using histograms for esti­ mating support. Computing the support using the Join approach only for rules with high estimated support.
• The histogram + memory approach same as the histogram approach, except that we store interme­ diate results in memory, and reuse them when we are called to make the same computation.

The procedure Join-support( r1, ... , rm) computes the support S, of each relation by performing the Join as explained in section 1.1. and then returns Max{Sal1 ~ i ~ m}. Since the Join is an expensive operation, we try to detect rules with low support using some low­ cost procedures. The other two approaches compute an upper bound on the support and then compute the exact support only for rules with high enough upper bound of support. The idea is summarized in Algorithm compute­ support in Figure 4. Note that once one relation with high S, is found, we turn to compute the exact support using Join.

The procedure S1-upbound called by the algorithm compute-support returns an upper bound for the value S, for a single relation r, in the body of the rule. This can be done by one of the two procedure: s,-upbound-brave or S,-upbound-cautious, shown in Figures 5 and 6, re­ spectively. The basic idea is that an upper bound can be achieved by taking the join of a relation r, with any other

8;-upboud-brave(r;,S) input: A relation r; and a set of relations S. output: An upper bound on S; for a rule whose body is SU{r;}. 1. s = 1.0 2. If there is r' E S such that r' and r; have a common variable X then s =upbound(r;, r', att(r;, X), att(r', X)); 3. returns;

relation with which r1 has a variables in common. Pro­ cedure s,-upbound-brave does this by picking one arbi­ trary relation with which r, has a common variable, and procedure s,-upbound-cautious does this by considering all relations with which r, has variables in common, and taking the minimum. Procedure S,-upbound-cautious works harder than procedure s,-upbound-brave but it achieves a tighter upper bound and hence can save more Join computations.

The procedure upbound called by procedure s,-upbound-cautious or procedure s,-upbound-brave founds an upper bound on S1 (as in Section 1.1) for a given relation r, using one of two approaches: the histogram approach or the histogram+memory approach.

The histograms approach exploits the fact that his­ tograms are easy to construct and are quite useful for support estimation. A histogram of an attribute of some relation is a mapping h between the set of values that this attribute can take and the set of natural numbers, such that for each possible value v, h(v) is the number of tuples in the relation in which v appears as the value of the attribute. Given two relations r1 and r2, proce­ dure upbound-histo shown in Figure 7 achieves an upper bound on the support of the equijoin between them. Pro­ cedure upbound-histo prepares the histograms and then calls the procedure Risto which actually computes the

upbound-histo( r1, r2, att1, ath) input: Two relations r1 and r2, att1 an attribute of r1, ath an attribute of r2 . att1 and att2 are of the same type. output: An upper bound on the support where only r1 and r2 are considered. 1. Let U be the set of a.ll distinct values in att1 of r1 and ath of r2. 2. Let ht be a. histogram with domain U of the values in att1 of rt. (If there is no such histogram, build it). 3. Let h2 be a. histogram with domain U of the values in ath of r2. (If there is no such histogram, build it). 4. return Histo( r1, r2, ht, h2, lUI);

support.

According to Claim 1.1 of Section 1.1, the number returned by Risto is also an upper bound on the support of the rule in which only r1 and r2 appear in the body with a common variable X.

The problem with the procedure upbound-histo is that it doesn't exploit the fact that pairs of instantiated re­ lations can appear again and again in many different instantiations of the same metaquery. In the procedure upbound-histo-mem, shown in Figure 9, we save in mem­ ory estimated support of pairs of relations and retrieve this information if necessary.

3.3 Evaluation

The efficiency of algorithm compute-support depends on the likelihood of finding a rule with high support. If a large fraction of the rules has a high support, then this algorithm will work harder then the straightforward algorithm which computes support by performing Join without trying to estimate the result before. Note that for rules with high support algorithm compute-support works harder than the algorithm which performs a Join directly because first it estimates the support, finds out that it is high, and then calls the Join procedure.

Our working assumption is that rules with high sup­ port are much less likely. In any case, however, the above analysis calls for an experimental evaluation of the algo­ rithms. In this subsection we present some preliminary results on such experiments. The evaluation was done on the Studentgrades database supported by the FlexiMine system [Domshlak et al., 1998]. This database contains information on students and some of their demographic characteristics, courses, and grades. The relevant ta­ bles for our experiment are: The student table with 997 rows, The course table with 1403 rows, The family table with 997 rows, The studentcourse table with 20705 rows. Each table contains between 5 and 9 attributes.

We have compared the performance of our algorithms by measuring the time it took them to compute support of 20 different rules involving four relations each. All the rules were instances of the same metaquery. The experiments were done on a Sun / SunOS workstation with one spare CPU and 128 MB main memory.

The time {in seconds) for the support computation were measured for the following configurations:

1. the support is computed by performing the join (procedure Join-support),
2. the support is computed by histogram without using memory (procedure upbound-histo in Figure 7).
3. the support is computed by our histogram using memory (procedure upbound-histo-mem in Figure 9) .

All the above methods were tested using the procedure Si-upbound-brave. Procedure Si-upbound-cautious was not tested yet.

Table 10 shows the results obtained when the support threshold was set to 0.5. The columns is as follows:

• num - the serial number of the rule, conf- the confi­ dence of the rule.
• Sjoin - the support computed by the definition, i.e first performing the join and then computing the support
• Shisto - the estimated support computed by our Risto method (Figure 8).
• join - the time to compute the support by the Join method, accumulated.
• histo - the time to compute the support by the his­ togram method, accumulated. including time for computing the histograms.
• mem - the time to compute the support by the Histogram method with memory, accumulated.

It can be seen that the Histogram method achieves about 50% savings in time, while the memory method has even improved on that.

Figure 11 shows the behavior of all three methods with a varying support threshold (0- 0.5) . Line 1 is the time for the Join method, Line 2- for the histogram method, and Line 3 for the histogram+memory method. In that figure the time for the Join method is normalized to 1 while the other time lines are relative to this time (e.g: the value 0.8 for the histogram method means that for that value of support, the histogram method time was 0.8 of the Join method). It can be seen that the larger is the support threshold, the better the methods which estimate first perform. This is because the highest the threshold is, the more rules do not pass it and can be cut by using support estimates.

4 Conclusion

This paper contributes to the research on metaqueries in several ways. We analyze the complexity of the related computational problem, we propose a new notion of sup­ port for a rule generated according to a pattern, and we present novel and efficient algorithms for computing support. Although more experimental work is needed for real evaluation of the algorithms we have developed, preliminary experimental evaluation is quite promising.