How Not to Say "NIL": Improving Answers to Failing Queries in Data Base Systems

1. INTRODUCTION

The relationship between a question and the appropriate answer(s) to this question has re­ cently been investigated from several points of view; we only mention [3], [s], (1o1. In this paper, we shall be concerned with a subproblem, namely how to find an appropriate answer to a failing data base query. We shall illustrate the purpose of this pape·r by the following example: Suppose somebody had asked for "all employees in the shoe department who are youn­ ger than 3o and earn more than $25.ooo" and the query failed, i.e., the answer was something like "nil", "¢", or "there are none". If the user is seriously interested in the answer be­ cause s/he needs it for some decision s/he has to make, then s/he probably goes on asking a series of questions like the question about "all employees younger than 31 and earning more than $24 , ooo" which all might be answered by "nil" as well; thus s/he will finally ask for a list of "all employees in the shoe department together with their age and salary" where another "nil" would indicate that there is no shoe department at all. Clearly it would be desirable that the system reports in its answer to the very first question that - in contradic­ tion to the user's expectations - there is no such department. This becomes even more deman­ ding since the number of questions which a user will have to put in order to discover the ori­ gin of a failure will rapidly increase as data base or queries become more complex.

· This research was carried out while the author was still at the Institut fur Informatik der Technischen UniversitAt Milnchen.

In this paper, we shall propose a method by means of which the reasons for the failure of a user's query may be reported to the user as the answer to his query. In section 2, we shall in­ troduce a non-procedural predicate calculus ba­ sed formal language which will be used to re­ present queries and answers throughout the rest of this paper. In section 3, we define how the so-called predecessors of a query (which are queries themselves) are inferred from a query; furthermore we show how recursive substitution of failing queries by their predecessors leads to an informative answer to the user's original query. In section 4, we shall discuss how the suggested method may be implemented and we shall demonstrate how it may be improved by considering the integrity constraints the data base is subject to. In a concluding section, we shall compare our approach to related research.

Throughout this paper, all examples refer to the following data base according to the rela­ tional model of data (cf . (1] ) :

EMP ( NAM, SAL, AGE, ON DEPT (DNO, DNAME ) CAR ( LIP, OWN, COL )

An employee EMP has a name NAM, a salary SAL, the age AGE and works for a department DEPT which is identified by a department number DNO (or ON respectively) and which has a department name DNAME. Moreover there are cars CAR with a licence plate LIP, a color COL, and an owner OWN who is an employee identified by his name.

2. :!:!!! QUERY LANGUAGE

2.1 Conventions

Throughout this paper, we shall use the follo­ wing notation:

• -Rand R' are non-empty relations (R t R')
• -A, A1, and A2 are attributes of R
• A' is an attribute of R'
• v is an attribute value of A'
• x and y are tuple variables for relations (x f y)
• w is a relational operator, i.e.,

For convenience, we assume that all attributes in the data base are named differently also if they are from different relations.

2.2 Terms

The elementary constituents of our query lan­ guage are terms, they are defined by the

following axioms:

• (T1) Any string of characters x where x=(x.A w v)

is called a term.

• (T2) Any string of characters x where x=(x.A1 w x.A2)

is called a term.

• (T3) Any string of characters X where x=(x.A w y.A')

is called a term.

• (T4) A string of characters is a term only if this is by reason of (T1), (T2), or (T3).

For a term X· let F(xl denote the set of vari­ ables which are free in x; clearly F(xl={x, y} in the case of (T3) and F(xl={x} in the case of (T1) or (T2). Terms according to (T3) also will be called join terms, all other terms will be called simple terms if they have to be dis­ tinguished. Note that for any tuple variable occurring in a term, the relation it stands for may be uniquely determined because all attri­

butes are named differently.

2.3 Expressions

Terms may be combined to form expressions by applying the following axioms:

• (E1) If X is a term then X is an expression. (E2) If a and B are expressions then x=<a ~ 6) and x=<a v 6)

are expressions.

• (E3) If a is an expression and x&F(a) then x=3x a and x= Vx a

are expressions.

• (E4) A string of characters is an expression only if this is by reason of a finite num­ ber of applications of (E1) through (E3).

F(xl may be expanded to expressions x in a na­ tural way: If x is an expression according to (E2) then F(xl :=F(a) vF(B) and if x is an ex­ pression according to (E3) then F(xl :=F(al\{x}. Given an expression X· we shall refer to the variables from F(x) as to T-variables (target), whereas all other variables occurring in x will be called Q-variables (qualification) ·

2.4 Well-Formed Sets

Expressions form the basis of our query lan­ guage, but not every expression according to section 2.3 leads to a meaningful query; there­ fore, we restrict our further considerations to a subclass of expressions, namely the so-called connected expressions. An expression x is called a connected expression if and only if for any Q-variable x in X there are n+1 join

terms 1 0 , 1 1 , ... , ln (nllo), n Q-variables

Informally speaking, for any Q-variable of a connected expression there is a path of join terms which "ties" this Q-variable to a T-vari­ able.

Let now x be a connected expression with F<x>+¢ and x 1 , x 2 , ... , xn the elements of F(xl in an

arbitrary but fixed order, then

is called a well-formed set. A well-formed set may be interpreted as the following data base query: "Find all those combinations of tuples from the relations specified by the variables xieF <x) for which the expression x holds." Thus the well-formed set

corresponds to the query "Find all employees in the shoe department who are younger than 3o and

earn more than 2 5 . ooo. "

2.5 Properties of Well-Formed Sets

The query language formed by the well-formed sets corresponds to a great extent to the data sublanguage ALPHA (cf. [2]l. The fact that well-formed sets cannot be used to ask for sin­ gle attributes but only for complete tuples is not really a restriction but rather a tribute to a more convenient notation. The absence of explicit negation from the expressions does not mean a deficiency either, since the language contains also the inverse operator of any of its relational operators (cf. 2.1).

Our restriction to connected expressions seems to be of some consequence for the expressive power of the language; but in fact, queries formed from unconnected expressions do not seem to make much sense as one can see from the following example:

{xj ( (x.AGE>3o),.. ]y(y.DNAME=' shoe'))} The answer to this query would be either a list of employees older than 3o or "nil" depending on whether there is a shoe department or not; thus, if the answer to this query is "nil" one does not know whether there is no shoe depart­ ment or whether there are no employees older than 3o and this seems to be a strong argument for excluding unconnected expressions from the formation of well-formed sets. Still we have to mention that for most (not all) unconnected ex­ pressions there are equivalent connected ones; this is illustrated by the following query which is semantically equivalent to the above one but formed from a connected expression :

{x J ( (x.AGE>3o),.. 3 y ( (y .DNAME=' shoe'),.. ((x.DN=y.DNO)v(x.DNty .DNO))))}

3. THE PREDECESSORS OF~ QUERY

3.1 Predecessors of Natural Language Questions

If somebody asked for "all employees who are younger than 3o and own a red car" and there are no such employees then one possible situa­ tion is that there are employees who are youn­ ger than 3o and own a car but none of these cars is red and that there are red cars but all of them are owned by employees older than 3o. A user who obtains "nil" as the answer to the above question will be likely to interpret the answer in this way. Still there are several other situations which might have led to "nil":

• (R1) There are no employees who own a red car.
• (R2) There are no employees who are younger than 3o and own a car.
• (R3) There are no employees who own a car.
• (R4) There are no red cars.
• (RS) There are no employees younger than 3o. We neglect the pathological situations where

there are no employees or no cars because in this case the question would have resulted from a wrong understanding of the structure of the data base.

Each of the situations (R1) through (RS) im­ plies a negative answer to the user's question; moreover for each of these situations there is a question which corresponds to it in a natural way:

• (S1) Find all employees who own a red car.
• (s2) Find all employees who are younger than 3o and own a car.
• (S3) Find all employees who own a car.
• (S4) Find all red cars.
• (SS) Find all employees younger than 3o.

Such questions are called the predecessors of the original question. In general, a question Q is called a predecessor £f~ question R if a negative answer to Q implies a negative answer to R.

A predecessor of a question may have predeces­ sors itself and one can easily see that these have to be elements of the set of predecessors of the original question; thus the set of pre­ decessors of a question is partially ordered. In the above example (SS) is a predecessor of (S2), (S4) is a predecessor of (Sl), and (S3) is a predecessor of both (S1) and (S2). We make use of this property in the following defini­ tion: A question Q is called an immediate pre­ decessor £f ~ question R if Q is a predecessor of R but not predecessor of any of R's prede­ cessors. The reason why we are concerned with these immediate predecessors is that stepwise substitution of a failing query by its prede­ cessors finally leads to the actual reason for the failure like (R1) - (RS) in the example.

3.2 Predecessors of Well-Formed Sets

The questions from section 3.1 may be expressed as well-formed sets:

(Uo) {xj ((x.AGE<3o) "jy((y.OWN=x.NAM) ,..(y.COL='red')))}

(U1) {x 13 y( (y.OWN=x.NAM)"'(y.COL='red'))}

(U2) {xI ( (x.AGE<3o),.. ]y (y .OWN=x.NAM))}

(U3) {xl3y(y.OWN=x.NAM)}

(U4) {yl(y.COL='red')}

(US) {XI (x.AGE<3o)}

Replacing a question by one of its predecessors here mainly means removing one term from the query's expression. On the other hand, not ev­ ery removal of a term from a query results in a predecessor of that query; thus (y.OWN=x.NAM) must not be removed from (Uo) since the resul­ ting expression would not be connected. Now we are going to introduce rules which specify how the predecessors of a well-formed set are ob­ tained, i.e., which of the terms of a wellformed set may and which may not be removed in order to yield a predecessor. Predecessors of well-formed sets correspond to a large extent to the immediate predecessors of natural lan­ guage questions but they are not equivalent: The negative answer to a predecessor of a well-formed set does not necessarily imply the negative answer to the original query. Moreover predecessors are only similar to the related concepts "presumption" (cf. (6]) and "presuppo­ sition" (cf. (a]) .

The above example showed that a join term may be removed from a query expression only if this does not "disconnect" the query expression; therefore, the first rule for obtaining prede­ cessors is:

(Xl) A join term must not be removed if both its free variables occur in other terms of the expression too .

This is the reason why (y.OWN=x . NAM) must not be removed from (Uo) but may be removed from (U2) thus yielding (US). There is one excep­ tion to this rule, namely:

• (X2) A join term may always be removed if there is a "parallel" join term in the expres­

sion which connects the same variables. To give an example of this rule we add an attribute DRIVER to the CAR relation where a DRIVER is an employee identified by his name; we then might ask:

• {xI ( (x.AGE<3o) "'jy ( ( (y.OWN-=x.NAM) ~~.(y.DRIVER=x.NAM))ol\(y.COL= 1 red 1 ))) }

i.e., "find all employees who are younger than 3o and own and drive a red car"; according to (X2) we may remove (y.OWN=x.NAM).

Simply deleting join terms may have the effect that we obtain expressions without T-variables and hence no well-formed sets. Therefore we have to make sure that the resulting expres­ sions always contain at least one free vari­ able; this is achieved by the following rule:

• (X3) Whenever we remove a join term which contains a Q-variable and a T-variable which does not occur anywhere else in the ex­ pression the Q-variable is made a T-vari­ able .

A Q-variable is made a T-variable by removing the quantifier of that variable from the ex­ pression. An example of the application of (X3) is the way in which (U4) is derived from (Ul).

3. 3 ~ .!:2, Handle Disjunctions

So far we were only concerned with queries without disjunctions. When consi~ering disjunc­ tion, we have to distinguish two situations, namely whether there is a disjunction at the top level of the query (i.e., the query expression is x=!avBll or somewhere else in the query.

• (X4) If a query is disjunctive at the top level of its query expression, then it has two predecessors which correspond to the two constituents of the disjunction.

Thus a query like:

• {x!(((x.COL='red')"'(x.OWN='Smith')) v( (x .COL=' blue' ),.(x .OWN=' Brown'·)) l }

i.e. ,"find all cars which are either red and owned by Smith or blue and owned by Brown" has the following predecessors:

• {xl((x.COL='red 1 )"'(x.OWN='Smith'))}

{x ( (x .COL=' blue' )"(x.OWN=' Brown')) }

A negative answer to one of these predecessors does not imply a negative answer to the origi­ nal query, rather a negative answer to the ori­ ginal query is equivalent to negative answers to both predecessors. Note, however, that a deeper reason for the failure of the original query, e.g., "there are no red cars and there is no Mr. Brown" would be detected by forming the predecessors of the predecessors.

If there is a disjunction at a deeper level of the query expression, then we need two more rules which further restrict the terms which may be removed from the query.

• (XS) A simple term which is a consti tuent of a disjunction may be removed only if the other constituent is a simple term too.
• (X6) If one constituent of a disjunction has been removed then the other constituent of that disjunction has to be removed to­
• gether with it if it is a simple term.

Application of (XS) and (X6) is demonstrated by the following example:

{x !3y ( (x .NAM=y .OWN) ol\( ( (y .COL=' red') v(y .COL=' blue 1 ) )y(y .COL=' white'))) }

(x.COL='red 1 ) may be removed because of (XS) , then because of (X6) both other simple terms are removed too; so the only predecessors of this query are:

{xl]y(x.NAM=y.OWN)} {yl(((y.COL='red 1 )v(y.COL= 'blue')) v(y.COL='white'l)}

Summarizing we can say that the predecessors of a well-formed set are obtained either by appli­ cation of (X4) or - for every term of the query expression - by trying to remove it under con­ sideration of (XI), (X2) , (X3), (XS), and (X6) . It can be shown that if B is a well-formed set representing a query which fails, then the ans­ wer "B=¢" may be substituted by the answer

where Bi are those predecessors of B which are empty themselves. The advantage of this latter answer is that it is more informative than the original one because each Bi is either a superset of B or a set whose emptiness implies the emptiness of B; if B is disjunctive at the top level then both answers are equivalent. Since each B. is a well-formed set and thus a query itself; we may apply the process of answer sub­ stitution recursively until each Bi in the ans­ wer has either non-empty predecessors only or no predecessors at all. For an example, we have to refer to (4].

4. IMPLEMENTATION

4.1 The Elementary Algorithm

In this section, we shall investigate how the predecessors of a given query may be computed. We start by taking the point of view that the evaluation of a query and the computation of the predecessors of that query are kept com­ pletely apart from each other; thus, as long as a query does not fail nothing has to be done. In the case of failure, the following algorithm will provide the appropriate answer according to 3.3. The data structures the algorithm ope­ rates on are three sets whose elements are well-formed sets; there is one set (PAl contai­ ning possible answers to the query, one set (DA) containing definite answers to the query, and an auxiliary set (AS) . At the beginning PA contains the failing query whereas DA and AS are empty. The basic idea of the algorithm is to recursively replace the elements of PA by their predecessors as long as there are any and to move them to DA otherwise. In detail the al­ gorithm looks like this:

• (All Choose an element a from PA and put the predecessors of a into AS (a is the next element which either will be moved to the definite answers or will be replaced by its empty predecessors) .
• (A2) If AS is empty then go to (A4) (If there are no more predecessors of a then we have to test whether a is a definite answer or not).
• (A3) Remove an element 8 from AS; if Bf¢ then immediately go to (A2) otherwise remove a from PA - if possible -, insert 8 in DA and then go to (A2) (As long as a prede­ cessor of a is non-empty, nothing has to be ~one, otherwise the predecessor repla­ ces a in the set of possible answers) ·
• (A4) If a is contained in PA then remove it from PA and insert it in DA (If a is still a possible answer then it was not replaced by any of its predecessors and therefore becomes a definite answer).
• (AS) If PAis non-empty then go to (Al), other­ wise stop (The procedure does not termi­ nate as long as there are still possible answers) .

It can be shown that DA is non-empty after the algorithm has terminated and that it contains exactly those well-formed sets Bi which form the appropriate answer

to the user's query.

4.2 Performance Improvements

The above algorithm is a pretty obvious method but on the other hand it does not work very efficiently. One of the drawbacks of the method as it stands is that a well-formed set may be computed more than once if it is a predecessor of more than one possible answer. A simple way to overcome this redundancy is to keep a list of already computed predecessors together with the information whether they are empty or not. A better solution would be to support the algo­ rithm by a strategy which makes sure that no well-formed set has to be evaluated more than once. An example for such a strategy would be to choose always that well-formed set with the "longest expression" in (All ; then no well­ formed set could be inserted in PA again after it has already been removed from PA.

If we abandon the (naive) point of view that query evaluation and computation of predeces­ sors are kept apart from each other, the algo­ rithm may be improved considerably: Note that before our algorithm can start the whole query has already been evaluated, namely in order to find out that it fails. Evaluation of a query consists of a sequence of elementary operations such as projections, joins, and selections whose results are sets of tuples corresponding to certain well-formed sets. It is easy to see that - no matter what query evaluation strategy is applied - these well-formed sets occur some­ where among the predecessors of the failing query. Therefore, if information about the well-formed sets which already have been compu­ ted by the query evaluator is made available to the above algorithm, then the number of prede­ cessors which have to be tested for emptiness will be further reduced.

4.3 Considering Integrity Constraints

Roughly speaking, integrity constraints are re­ strictions which the data base is subject to in order to be in a well-defined state. An example of an integrity constraint on our data base would be that for every tuple of the relation CAR there has to be a tuple of the relation EMP such that the values of their attributes OWN and NAME are identical. Such integrity con~ straints may be used to simplify the predeces­ sor structure of a given query; we illustrate

• this by means of the following example: B={xl ( (x.COL= 1 red 1 ) "]y( (y.NAM=x.OWN) ~~o(x.A�E<3o)))}

i.e., "find all red cars owned by employees who are younger than 3o." According to section 3 the predecessors of B are B1 and B2, those of B1 are B3 and B4, and those of B2 are B4 and BS

B1={xJjy((y.NAM=x.OWN)~~o(y.A�E<3o))}

B2={x I ( (x.COL= 1 red')" 3Y (y .NAM=x.OWN))}

B3={yl (y.AGE<3o)}

B4={XI3Y(y.NAM=x.OWN)}

BS={x 1 (x.COL=' red')}

Now, if every car has to have an owner then ob­ viously B4 is the set of all cars and therefore cannot be empty; moreover B2 is identical to the set of all red cars, namely BS. Consequent­ ly, we would like to obtain B1 and BS as the predecessors of B and B3 as the only predeces­ sor of B1. Integrity constraints may be used to remove certain join terms from the predecessor queries, we thereby reduce the average number of predecessors which have to be checked for emptiness in the case of failure and hence fur­ ther improve the efficiency of our procedure. For a more thorough discussion of this point we have to refer to [4].

5. CONCLUSION

The work described in this paper is closely re­ lated to the research reported in [9] and in [7]. In [9), a formal query language called HI-IQ for a CODASYL-type data base is used to express queries and to compute deeper reasons for a possible failure of a query. Still, HI-IQ supports a much narrower range of queries than well-formed sets do; moreover the procedure that computes the predecessors of a query does not obtain all possible predecessors of an ar­ bitrary query. The method for obtaining an appropriate answer to a failing query will on average require more computation than the pro­ cedure suggested here because small deviations of the user's expectations from the actual data require more computation than greater devia­ tions do. Finally, the method proposed in (9] does not make any use of integrity constraints during the computation of predecessors.

In (7], the problem of how to find an appro­ priate answer to a failing query is investiga­ ted for natural language queries: A natural language query is translated into a so-called meta query language (MQL) which is a graphical representation of the query still close to na­ tural language; from this MQL representation the predecessors of a query are computed. A query represented in MQL then has to be trans­ lated into the actual query language before it may be evaluated. Contrary to that approach, we have shown in this paper that informative ans­ wers to failing data base queries may be ob­ tained from a purely formal query representa­ tion and that clues provided by natural lan­ guage are not actually needed for this task. Nevertheless, we have to mention that our me­ thod will gain its full strength only if the informative answers will be rephrased in natu­ ral language.