Relational Strategies for Processing Universally Quantified Queries to Large Data Bases

1. INTRODUCTION

It has been shown in Chang [1978), Furukawa [1977), Hinker [1978), Kellog et al. [1978) and Reiter [1978b) that deductive logic offers considerable potential for improving on-line access to large, complex data base domains. The common feature of the current researches to that direction is the attempt to combine a deductive component with relational data bases.

Chang [1978) divided the approaches of these researches into two groups: One is the evaluational approach where intensions are used to transform queries and extensions are used to evaluate queries. The other is the non-evaluational o~e where both intensions and extensions are used to prove a question represented by a formula in the same manner. It has been shown in Reiter [1978b) that the evaluations! approach is more feasible for data bases with very large extensions and comparatively small intensions.

Codd [1972) has defined an algorithm to convert queries expressed in relational calculus to a sequence of relational algebraic operations. Reiter [1978b) has developed a general framework in the restricted first order logic which enables one to get indefinite answers to any queries, and reformulated Codd's algorithm in his framework. Reiter [1978a] has also developed an efficient query conversion algorithm under the closed world assumption (CWA) .

In this paper, a new algorithm to evaluate universally quantified conditional querles under the CWA is presented. Summary operation on a relation is added to the set of primitive operations of the relational algebra . The algorithm reduces the problem to the application of the operations of set intersection, summary and join to the answers to the subqueries .

In deductive relational data bases developed so far, only extensions have been considered to compose relations. Intensions have been. stor ed in knowledge bases outside the relational data bases. However, it sometimes happens that we have a set of uniform intensional dat9 of the form ('<lx;t. ) p(i(}. In this paper, a new representation schema based on the partial multi-valued dependency (PHVD) decomposition of a relation is introduced as a suitable way to express such data.

Queries to the decomposed relations are evaluated using a set of equations which give users the image of the original relations as a logical view. Furthermore, it will be stoown that universally quantified queries on those relations can be evaluated very efficiently by applying the rule-based symbolic evaluation method.

2. REVIEW OF QUERY EVALUATION UNDER THE CWA

In this section, query evaluation under the CWA developed by Reiter [1978a] will be reviewed quickly as well as some extentions.

All queries have the form [x 1c 1 , ·.. ,x /~: (qlyl/& ) ... (q Y /9 )W(x,, ··· ,x J,, ... y )]n n where ~(X1···'!1,fn,f1 , ··· ,y111 ) ~s a qufntifier free formula with free variables x 1 , ··· ,x, Y 1 , ... , y and q i is either '</ or 3 , i = 1 , ... , ~. We shafl use the abbreviated notation [?1-'t: (q}'lt)W(~.~)] to express a typical query. The 1:.' s and 9' s, which are called types, are sets of constant signs which the variables associated with them range over. A sequence of types~= (~ 1 , ···· ~n) is the set ~,x···X!n·

A data base (DB) is a set of clauses containing no functional signs.

Under the CWA, if no proof of a positive ground literal exists, then the negation of that literal is assumed true. This can be viewed as equivalent to implicitly augmenting the given data base with all such negated literals.

Since worlds are completely specified under the CWA, the set of CWA answers IQI W to Q = [t/~ : (q111)W(1,1>J is defined as rotlows:

{ ~ .... ... u -~- ( ... ;t) , ... -+)} IQICWA = c : c f:'t: and DB EDB qy/'CJ W x,y

where EDB = {Pc : P is· a predicate sign, ~ a tuple of constant signs and DB t+ Pi!}.

The evaluation of any queries are reduced to the applications of the relational algebraic operations to the answers to atomic queries. Before listing query conversion rules, we define some of the operations of relational algebra.

Let Q = [t/~,z/ If': W], and 1 is the n-tuple x , ... ,x . Then IQI is a set of (n+l)-tuples, a~d the ~rojection of IQI with respect to z, n IQI is the set of n-tuples obtained from IQI b} deleting the (n+l)st component from each (n+l)-tuple of IQI.

Let Q = [t;l,z!'f: W]. Then the quotient of IQI ~ z, Az IQI, is a set of tuples and is defined as follows:

~" ~z IQI iff (<!,a) f- IQi for all a " 'f. The operater ~z is called the division with respect to z.

Let Q1 = [~/~,z/tf:W1] and Q2 = (y/(,z/1' :W2]. The join of IQ11 and IQ21 with respect to z, 1z(IQ11,1Q21), is a set of tuples and defined as follows:

( (!, d , l) E: I z ( I Q 1 I , I 921 )

iff (<!,d)~ 1911 and (~,d)~ 1921. We sometimes denote 1z(IQ11,1Q21) as (1911 lz 1921).

The set of query conversion rules are listed below:

Rule 1. (Decomposition of AND/OR queries) 1. I [it/-i! :W1 ,.. W2] I = I rV't :W1] I f'l I [t/~ :W2] I. 2. l[xl't :W1 v W2]1 = 1[1/t :W1]1 U 1[11't:W2]1.

Rule 2. (Elimination of negation) 1. I [1/~ :W]I = ~ - l[it/l! :W] I.

2. 1[1/~ :W1AW2]1 = 1[1/.C :W1]1- 1[1/t :W2]1.

Rule 3. (Elimination of existential quantifiers) I [iii : C 3 )t!IDWJ I = llJI [11-t ,11'1: W] I where 11;t denotes 1f 1 ··· ~ and TT i is the projecti6n with respe~t to fi. Y

Rule 4. (Elimination of universal quantifiers) l[t!=l: ('tly/"1 )W]I = ~il[11t,1l'6 :W ]I where A 9 denotes ~~1 ·· ·6~,.. and 6~.,.: is the division with respect toY~·

Rule 5. (Decomposition of AND queries) I [iii :W1 A W2] I

= ( 1[11/il :W1] I I I [~2/~ :W2] I) where ~i is a sub-sequence of ? which appears in Wi, and ti is the corresponding sub-sequence of ~. for i = 1, 2. The join operation I is performed with respect to the variables included in both f1 and ~.

Host of the above rules are derived from Reiter [1978a]. The extended points are as follows:

1. In rule 2, the restriction that W, W1 ane W2 must be quantifier free is removed.
2. Rule 4 is new. Reiter has developed a general framework which enables one to get indefinite answers. The division operator defined by Codd [1972] has been properly generalized in the framework. However, the handling of universal quantifiers in the CWA has been ommitted in Reiter [1978a]. But there is no reason to exclude the handling of universal quantifiers in the CWA and moreover the set of conversion rules becomes more well-structured by adding these rules.

3. Rule 5 is new, too. It is easily shown that this rule reduces the ~unt of computation. Let Qi = (it/~:Wi] and ti = TT'iti(~, i.e., the compliment subsequence oft , r = 1, 2. We would have to evaluate Q = (x/~ :w1~ W2] according to IQI = IQ11 ~ IQ21, unless we have Rule 5. But it is easily shown that

for 1 = 1, 2. By applying Rule 5, we can avoid the execution of the above costly Cartesian product operations.

3. THE HANDLING OF UNIVERSAL QUANTIFIERS

Let us consider how to compute the division c1ziQI where Q = (x/'t.,z/'f : (qy/f)W]. The following algorithm generates the answer c1ziQI.

Algorithm D.

1. Group the answer set IQI to the query Q by 1 and make a list of z·s for each x (we denote the list by Zi).

2. For each zf, test whether it includes the set ~· If the test succeeds, then put the 1 in the answer set AziQI.

Rule 4 says that ~ziQI is the answer set for the universally ~uantified query QO = (il/t : (~z/'f)(qf/~)W ] . Notice that QO is the abbreviation of the conditional query QO' = [it/~: (~~'z)(zfft(qf/f)W)). The inclusion test ~c Z~ in Algorithm D reflects the implication in QO', where the consequent z & f in QO' corresponds to the lefthand set f and the antecedent (qi!#)W to the righthand set zt.

We can use the division operation to efficiently evaluate a class of conditional queries Qc = [X/~ : ('~ z/lf )( W1 ... W2)] such that W1 does not contain any free variables in x. The following theorem states the fact more precisely.

Theorem 1. Let Qc = [11~ : (Y zit)( WH W2)) be a universally quantified conditional query and assume that W1 does not contain any free varibles in x, Q = [x/~,z/~ :W2), and Qz = ( z/'f :W1). If DB U m is consistent, then

We sometimes denote ~z'~IQziiQI as IQI I IQzl.

We cannot use Theorem if W1 contains any variables in f. We can deal w.ith the general case by introducing the following cut operation:

Let R = I [1/~1 z/tj.- :W(x, z)) 1. Then the cut of R

with respect to 1, denoted bl f-.< R) , is a set of pairs (ai, D1) where <f1 e- "t. atid D1 is a set of dk e "t such that

Di : {dk : (i!i,dk) ~ R}.

We regard .fit(R) to be a function from nzR to 2"t.R and denote D1 as fl(R)(it;.). fX(R)(~i) is called the cross-section of f~(R) at ~ 1 .

The set of D is exactly the same as zai in Algorithm D.

Theorem 2. Let Q =[X/~: ('Vz/'f)(W1-+W2)]. If DB u S is consistent, then

where Ri = l[xi/~i·z/.y :Will for 1 = 1, 2.

Since A c B iff I A f'\ B1 = IAI in case A and B are finite sets, we can replace the set inclusion test in Theorem 2 by a simple comparison of the cardinal numbers of two sets. This strategy has been implemented in GM-RDMS (Whitney [1974]), where an operation called summary has been used to construct a set of pairs cal, IDil) which summarize the pairs (i!i, Di).

Example

The following example is taken from Palermo [1974) . There are four relations: ~. SUPPLIERS, PROJECT and PART, as shown in Figure l (The relation names are underlined to distinguish them from the corresponding predicates. They are considered to refer sets, rather than predicates).

WI PID PTYPE

31 A

32 A

33 B

Figure 1. An example data base.

The relation ~ (SID, PID, JID) is a set of tuples (x, y, z) such that a supplier x supplies a part y to a project z. SUPPLIER (SID, SLOC, SNAME) has information on suppliers' locations and their names. PROJECT (JID, JLOC, JNAHE) has information on projects' locations and their names. £ABI (PID, PTYPE) defines the type of each part.

Let us consider the following query to the above data base:

~ Find the name and location of suppliers each of whom has supplied at least one project located in San Jose with at least one of every part of type A.

This query is expressed as follows:

Q = [x/SNAME, y/SLOC : (3 s/SID) (SUPPLIER( s ,y ,x) A(3j/PID)(PROJECT(SJ,j) A(Vp/PID)(PART(p,A) ~ SUPPLY(s,p,j))))]

The evaluation of Q proceeds as follows:

By applying Rule 3 and 5 to Q, we get

IQI = 1Ts(IQ11 *s IQ21).

2.Let Q21 = [j/JID: PROJECT(SJ,j)]

and Q22 = [s/SID,j/JID : (~p/PID){PART(p,A)~SUPPLY(s,p,j))]

From Rule 3 and 5, we obtain

3.Let

Rl = l[p/PID : PART(p,A)]I and

R2 = 1[5/SID,j/JID,p/PID SUPPLY(s,p,j)]l

Since Rl is not an empty set,

I Q221 : R2 I R 1

from Theorem 1 .

The snapshots of the above evaluation process is shown in Figure 2, where the summary operation

is used to evaluate Q22.

4. THE PMVD DECOMPOSITION OF A RELATION

Suppose that the answer of the universally quantified query Q22 in the previous example is saved. Then, we can answer to the same query immediately by simply restoring the saved answer. We need to save answers for other types, e.g. a set of supplier-project pairs (x, y) such that x supplies all parts of type B to y. These answers can be put together if we associate each type to each answers. Let SUPPLYALL (SID, JID, PTYPE) be the relation built in such a way. From SUPPLYALL and lARI relations, we can infer the "SUPPLY" fact, namely;

Furthermore, we can remove all tuples which are infered in (4.1) from the original ~ relation. We rename the reduced SUPPLY relation as SUPPLYSOHE. The original SUPPLY relation is now decomposed into two relations: SUPPLYALL and SUPPLYSOHE, as shown in Figure 3.

The extension of SUPPLY(s,p,j) can be obtained from not only the SUPPLYSOHE relation, but also the SUPPLYALL relation. other relations which about SUPPLY(s,p,j). equation holds: Assume that there are no contain the information Then, the following

This equation is used to transform queries in terms of simple user's view of relations to those in terms of system's view (Furukawa [1977]). The relational algebraic expression of the query Q22, that is,

IQ221 = ~(s,p,j) I ~t=A· PART(p,t) (4.3)

is transformed to:

where the operator ~ht> is defined by

and is called the selection with respect to fct).

Considering the meaning of the predicate "SUPPLYALL", it is expected that IQ2211 = l[siSID,jiJID : SUPPLYALL(s,A,j)]l should be included in the answer set IQ221. In fact, we can deduce IQ2211 as the answer.

To deduce the result, we need several rules and assertions as follows.

The deduction process is as follows:

1. From RU1, and (4.4), it is shown that

2. From (4.5), transformed to RU2 and ( 4. 4) , I Q221 is

3. From (4.6), AS2, RU3 and AS1 , IQ221 i s further transformed to:

This is the final result and is equal to IQ2211.

If SUPLLYSOME(s,p,j) : , then all suppliers supply only all parts of some types to some projects. In this case, it i s said that multi-valued dependency (HVD) PTYPE~ (SID , JID) holds and it is guaranteed that the SUPPLYPART relation, that is, the hypothetical single relation which includes all information about SUPPLY and PART, can be decomposed into

SUPPLYALL(s,t,j) : ITP(SUPPLYPART(s,j,p , t) ) and PART(p, t) = Tis1T 1 (SUPPLYPART(s ,j ,p , t)) without losing any information .

If SUPPLYSOME(s,j,p) is not empty, the above condition holds only for the subset (SUPPLY - SUPPLYSOME) of the SUPPLY relation . We say t ha t partial HVD (PHVD~PE ""lt(SID,JID) holds i n SUPPLYPART relation with SUPPLYSOHE relat i on as exception.

The relation SUPPLYALL, unlike ordinary relations, is a set of intensional data. A t upl e (sO,tO,jO) in SUPPLYALL means that the supplier sO supplies all parts of type tO to the project jO. On the other hand, "SUPPLYALL(sO,tO,jO)" may sometimes be interpreted as an extensional fac t by itself. (sO,tO,jO) becomes an extensional fact if it is not unusual that some suppliers supply to some projects all parts of some types. In that case, the query will be expressed directly in terms of "SUPPLY ALL", instead of through "SUPPLY".

It has been suggested in Ohsuga [1979) that the information clustering by the division is an important mechanism to build a structure in the data base. The PMVD decomposition schema, together with the associated query transformation equation, enables one to realize the above mechanism in the framework of deductive relational data bases.

We finally remark the evaluation of queries other than universally quantified ones to the decomposed relations. For example, consider the query Q = [p/PID,j/JID : SUPPLY(237,p,j)]. By applying the query transformation equation (4.2) ~~ IQI = ~s= 237 sUPPLY(s,p,j), it is transformed

IQI = ~s- 237 CSUPPLYALL(s,y,j) *t f!Rl(p,y) U - SUPPLYSOME(s,p,j)). (4.7)

We need to perform the costly join of the SUPPLYALL relation and the fARl relation to evaluate (4.7). However, it may sometimes be adequate to answer in terms of SUPPLYALL and SUPPLYSOME instead of SUPPLY. In that case, we can avoid the join. It is related to the notion of approximate responses discussed in Joshi et al. [1977].

5. CONCLUSION

Practical algorithms to evaluate universally quantified queries are presented.

Furthermore, a new representation schema based on the PMVD decomposition of relations are introduced. A set of uniform intensional data of the form (9'it/t)P(X) is expressed as a relation by using the schema. Universally quantified queries to the decomposed relations are converted to quantifier-free queries by the rule-based symbolic evaluation method.

The DBAP (Furukawa [1977]) are being expanded to realize the algorithms presented in this paper ..

ACKNOWLEDGEMENT

The auther thank to Dr. Osamu Ishii and Dr. Akio Tojo for providing a chance of the present study, and to Professor Setsuo Ohsuga, Mr. Kazuhiro Fuchi and the staffs of the information systems section for their helpful discussions.