A Metalanguage Representation of Relational Databases for Deductive Question-Answering Systems

1. Introduction and Overview

This paper presents a method of formally representing the information that exists in a relational database. Database rep­ resentation technology has progressed independently of AI, but there is a need to reconcile it with Al representations. Many Al systems tha t. address real-world domains must access existing databases; typicallly these have been natural-language question­ answering systems, e.g., LUNAR [14[ and D-LADDER [BJ . The D-LADDEll database, for example, is a pre-existing relational database that is distributed across several sites of the Arpanet; access to the information is through a pre-defined database query language. D-LADDER can parse and "understand" English-l anguage questions for which no information is available from the database because it maintains a representation of the domain of discourse that subsumes the information present in the database. llowever, to respond reasonably to a user's question between the database and the domain of discourse.

1The work reported l-.cre wa~ Sllpported by t.hc o~rcnse Advanced Itcs(·arch Project· Agrn r.y under Contract N00039- 80--r. -0615. The view· ~nd con­ clusions contained in this document arc tho~ ·w· of the author:~ and should not Ue interprclt!d a!» rcprel'cnti!.tive of tht~ official policies of the Defense Advanct·d Hcsearch Projects Agency of the U.S. Government.

Queries about the domain are originally expressed as for­ mulas in the ML. By attempting a constructive proof of a cer­ tai n ML expression involving that formula, it is possible to either answer the query by a proof in the ML theory, or find a DBL expression that is equivalent t.o the original ML query. In the latter case, because the DDL is fully interpreted by the database, the answer to the query can be found by evaluating the DBL expression with a suitable database query processor. This whole process is reminiscent of the an6wer extraction tech­ nique of Green [5].

The metalanguage/database language dichotomy is useful in making a theoretically satisfying distinction between the description of the discourse domain required by an AI sys­ tem, and the information that may be present in an associated database. As a result, it will be possible for a question-answering system that uses this representation to respond in a more sophis­ ticated way to user inquiries to a database. For example, it is possible to correctly represent the distinction between questions such as "Is P always true?" versu6 "Is P currently true in the database?"

2. The Relational Database as a Model

We seek a method of describing the information that a database contains, that is, a way of formally characterizing the way in which data in the database relates to the domain under consideration. For the purposes of this paper, we will restrict our attention to a particular type of database, the relational database, because it is more readily amenable to formal analysis than are other database formulations. 3 A relational database is a set of relations {R,} over a set of domains {D 1 } . Each relation R consists of a set of tuples of some fixed length n, the arity of the relation; we will indicate a relation's arity with a superscript, R" . The clements of the tuples are drawn from the domains of the database. 4 In a relational database, the relations arc finite, but the domai ns may be infinite, e.g., the domain LENGTHS in the sample database below is the set of positive real numbers over some interval.

As an example relational database, consider the following relations about the ships world:

SHIPR: SHIPS X SNAMES X LENGTHS X MEDIC COM MAN DR : OFFICERS X SHIPS

The domains are SHIPS, SNAMES (ship names), LENGTHS, OFFICERS, and MEDIC. MEDIC is the bi­ nary domain {T, F} , and its use will be explained below. This sample database is derived from the DL UE FILE database ac­ cessed by the LADDER project [6] . A typical tuple of the SHIPR relation might be {USN123,LAFAYETTE,344.6,T}.

A relational database is used to model the world in the following way. -If a tuple { u, x, y, z} is present in a relation R\ then the objects u, x, y, and z are assumed to participate in the corresponding real-world relation. Thus the presence of the tuple {USN123,LAFAYETTE,344 .6,T} means that the ship USN123 has the name Lafayette and the length 344.6. The interpretation of theM EDIC value is that the ship has a doctor on board if the value is T, and does not if the value is F .

'The approach described here will actually work with any database repre­ sP.ntation ttchnology that is powerful enough to be a mechaui'lable model for some first-order language .

4 Thi!1 is unfortunate terminology, since we have already introduced domain of di.srour.!e. The relational domains are sets of individuals drawn from the universe of individuals of th~ domain of discourse. �~nerally thP.re should be no confusion about the proper rcferrent of domain ln this paper, becau1e

or context.

What happens if a tuple is not present in a relation depends on the interpretation one chooses for the database. The strongest assumption that can be made is that if a tu pie is ab­ sent, the relation does not hold for the elements of that tuple. Whether this assumption is appropriate or not depends on the domain of discourse that is being modeled. It assumes that the database has complete information about the part of the world that corresponds to the relations it contains. In many applications, the database has only partial information about the domain of discourse. A formalization of the information that the database contains must be rich enough to represent a partial correspondence between the database and the domain.

The relations in a relational database can be considered to form an algebraic structure under the operations join, restric­ tion, projection, and set union and difference [3] . These opera­ tions can be used to extract information from the database in a convenient manner. For example, suppose we wished to find the officers of all ships over a length L . One way to do this would be to join tuples from the COM MAN DR and SH IPR relations with the same SJ-1 IPS element, 5 restrict the resulting relation so that only tuples with a LENGTH element greater than L remain, and then project the OFFICER elements to yield a set of one-element tuples containing the answer.

Formally, the results of algebraic manipulations on a rela­ tional database can be described by designing an appropriate first-order language for the database. The basic idea is that expressions in the language (which we will call the database language, or DBL) are either true or false with respect to the database; further, because we actually have the database in hand, it is possible to determine the.truth value for any ex­ pression of the DBL by performing algebraic operations on the database. Thus the DBL functions as a query language for the database, because it describes properties of the database. A query is phrased as an expression in the DBL, and then algebraic manipulations can be performed on the database to determine the truth of the expression, and hence answer the query. Codd [3] has shown that the five given operations are sufficient to decide the truth-value of any expression in an ap­ propriately defined DBL; hence the database and its associated algebra forms a computable or mechanizable model for the DBL.

At this point, it is helpful to look at the DBL for a particular database, the sample database given above. We will use a many­ sorted first-order language with equality. There is one sort for each relation in the database; a sort consists of all tuples that are in its corresponding relation. Variables arc restricted to range over a given sort. In quantified expressions, the sort that a variable is restricted to will always be indicated by giving the name of the relation for the sort. For example, in

Vt/sHIPR ...

the variable t is restricted to tuples in the relation SH IPR. Because variables only refer to tuples in a relation, this type of language has been called a tuple relational calculus [13] .

Besides variables over tuple sets, we allow function terms that refer to elements in the domain. Among these terms will be unary functions that pick out elements of a tuple. Generally, we will use function names thRt arc similar to the domain of the element that they select from the tuple. As an example, consider:

5 Th is operation is called &n tquijoin, and is the composition or a join with an equality rf'Jtridion.

'Vt/sHIPR [3name(t) =LAFAYETTE] V [length(t) > 344.6]

The above expression says that for all tuples in the SHIPR relation, either the S NAMES element of the tuple is equal LAFAYETTE, or the LENGTHS element is greater than 344.6 meters. There are two unary functions, sname and length, and one constant function, LAF AY ETT E.

The language also contains the boolean operators, the equality predicate, and some arithmetic predicates such as greater than and less than. As defined, the DBL has the im­ portant property that every expression that can be written in the language is decidable with respect to the sample database, using the relational algebraic operations. Such a language is called 3ale in the database literature [13]; a safe language is one whose expressions can all be interpreted by examining just the instances of relations present in the database. The practical im­ port of this is that safe languages are mechani~able, in the sense that the truth value of every expression in the language can be determined by a finite number of algebraic manipulations on its intended model.

3. The Metalanguage

A language like the DDL for which the intended model is available is called an interpreted language. If the database cor­ rectly reflects the structure of the domain of discourse, then we need no additional representational apparatus to describe the domain. However, it is more often the case that we have incom­ plete information about the domain of discourse: for example, we may know that the Lafayette is commanded either by Smith or Jones, without knowing which one of the two is the actual commander. Such partial information about the domain cannot be expressed within the database model.

Another way to view this situation is to say that the database and the domain of discourse are both models of the DBL, but they are not coextensive. That is, in the real world it may be the case that either Smith or Jones is the captain of the Lafayette; because we do not know which is the case, there will be no tuple in the COM MAN DR relation of the form {nnn, U SN123}, where. U SNl23 is the identifier of the Lafayette. So if the query, "Does Jones command the Lafayette" is posed in the DBL, the answer with respect to the database will be "no," which may not be the case in the actual world. 8

If a question-answering system is to return correct responses to user's queries when only partial information about the domain is available, then a more powerful representation than the DBL and its associated database is required. On the other hand, we wish to make use of the information that is contained in the database in those cases where it is sufficient for responding to a query. So the representation we seek must not only characterize the domain of discourse, it must also encode the way in which

6 We are going to assume in this :>aper that what information the databaae does contain about the domain or diecourse is correct. In principle , the formali1ation presented in this section could readily handle cases where the database was not in conformity with the domain, e.g., the tuple JONES ,USNI23 is preoent in the COMMANDR relation even when Jones is not actually the commander of the Lafayette. It may be uoeful in pract ice to have thio abil ity, especially when dealing with a changing domain where update· to the databaae may not be timely.

the database as a model corresponds to the actual world.

To represent the domain of discourse, we will usc another many-sorted first-order language with equality, called the metalanguage, or MI.. . The MI.. will have non-logical axioms that state properties about the domain. For example, for the ships world we might define the following predicates:

DOC(x,y) means that x is the doctor aboard ship y;

NAME(x,y) means that x is the name of ship y;

LEN(x,y) means that x is the length of ship y;

COM(x,y) means that officer x commands the ship y.

A typical assertion about the domain might be:

'Vxf SHIPS 3y/LENGTHS LEN(y, x), ·

which says that every ship has a length. It is not critical that we have chosen this puticular form of the first-order predicate cal­ culus; any of the non-sorted variants would do just as well. Note that the ML need not be a tuple calculus; in this example, vari­ ables range over individual ships, officers, lengths, etc., rather than tuples.

In addition to representing the domain of discourse, the MI.. is also used to characterize the database as a model of the DDL; this is what makes it a metalanguage. In the MI.. , we will use the predicate DB of one argument, a DBL formula, to mean that that formula holds in the database. Assume, for example, that the MI.. term I denotes the DBL formu la Vt/sHIPR !sname(t) = LAFAYETTE]V[length(t) > 344 .6] . Then the MI.. expression DB(!) asserts that the DDL formula denoted by I is actually true of the database; that is, all tu pies in the SHIPR relation either have their sname clement equal to LAF AY ETT E, or their length clement greater than 344.6.

In the metalanguage, we require a number of constructors for DDL formulas. For boolean connectives of the DBL, the constructors and, or, imp, and not take DDL formulas as argu­ ments and return the obvious DDL compound boolean formula. For example, the ML term and(!, g) denotes the DBL formula F IIG, where F and G are the DBL formulas denoted by f and g. This abstract syntax for object-language formulas was intro­ duced by McCarthy [9] .

Because the DB predicate represents truth in the database model, the normal truth-recursion axioms are valid for it . We introduce the MI.. sort DBF S, which is the set of all DBL formulas, and write the truth-recursion axioms as:

Vf/oBFS [DB(not(f)) :=~DB(!)] 'VIg/oBF'S [DB(or(f,g)) := DB(f)VDB(g)J 'Vfg/oBFS [DB(and(! , g)) := DB(/)IIDB(g)l TR l.

'VIgf DBFS [DB( imp(!, g)):= DB(!):JDB(g)l

Additionally, to construct an arbitrary DBL formula we will need MI.. terms that denote DBL predicates, terms, and quantifiers. At this point it is convenient to develop the theory for the propositional case; later it will be extended to predicates over individuals. For each DDL propositional constant there is a MI.. constant term that denotes it. The convention will be to use primed terms in the MI.. to denote the corresponding unprimed propositional constants in the DBL. Thus the MI.. term P' will have the DDL proposition P as its denotation. Given this and the MI.. boolean constructors, it is possible to write a MI.. term for any sentential expression of the DDL, e.g., and(P', not(Q')) denotes the DBL formula PII~Q . The two MI.. terms TRUE' and FALSE' are specially defined to refer to the DBL propositions TRUE and FALSE, whose tru t h values in the database arc always taken to be true and false, respectively:

4. Database Query Derivation

Having described the DBL and its associated database within the ML, we are in a position to formulate the derivation of database queries in the DDL from an original ML query. At this point we will restrict our attention to closed queries, that is, those whose answer is either yes or no. Closed queries can be represented by closed ML expressions.

Suppose that qwff is a ML expression whose truth value ia to be determined. Consider the ML schema:

If a constructive proof of Tl can be found for a given instance of qwff, the binding for I will be a DBL formula that is equivalent to the original query qwff. By evaluating the DBL query with respect to the database, the truth of qwlf can be determined. Note the use of the equivalence ronnective in Tl; if the answer to the DBL language query turns ·out to be "false," then the negation of qwlfwill have been established.

A special case of Tl occurs if the binding for I is TRUE or FALSE. When this happens, the truth or falsity of qwlfwill have been established entirely within the metalanguage, without the necessity of evaluating a DBL query.

Example . Let P and Q be two DDL propositions which we intend to have the same meaning as the ML predicates P and Q, respectively (we can use the same names because we will always know which language a formula is in). The ML also contains the constructors P' and Q' of no arguments, whose denotations are the DBL language formulas P and Q. We can state that the DBL and ML predicates have the same meaning by axioms of the following sort:

Pl states that r (or Q) holds just in case the DBL formula represented by P' (or Q') holds in the database. The axioms Pl can be used to derive DBL queries equivalent to any ML query that is a sentential expression over P and Q. Suppose the original ML query is PVQ. Then it is easy to show that, by T Rl and Pl,

The process of database query derivation is similar to that of answer extraction in formal question-answering systems [5j. The problem of finding a database query is reduced to that of finding a proof of the first-order ML formula that is an instance of Tl.

5. Predications on Individuals

In section 3 an abstract syntax was developed for DBL constant predicates. But since an important part of the DDL are terms referring to individuals, the abstract syntax must be ex tended to include constructors for these DBL terms. In this section we introduce the needed technical machinery for this into the ML. Although the machinery itself may appear cumbersome, the idea behind it is fairly simple: to state the correspondence between terms in the DBL and the individuals they name. The complications arise in keeping track of the distinction between terms in the ML, terms in the OL, and the individuals they denote.

5.1 The Denotation Function

We begin by defining a new sort, DBTS, that is the set of DBL terms. ML terms of this sort will denote DBL terms. Again, a primed convention will be used; e.g., the ML constant term A' will denote the DBL constant term A. We can diagram this relationship as follows:

ML: A B A' B'

DBL: t~..-1---~

individuals: A B~

The arrows in the diagram represent the denotations of the terms. A and B as terms in the ML refer to the individuals A and B in the domain of discourse; they are of the sort IN DS. Similarly, the terms A and B of the DBL also denote individuals in the domain. The ML constants A' and B' (of sort DBTS) refer to the DBL terms A and B, rather than individuals. There is nothing special about using the same symbols in both lan­ guages to denote these individuals; it is done here simply for consistency of naming.

To construct DBL expression that involve predications over arguments, the ML contains a primed constructor symbol P' for each predicate symbol P of the DDL. The arguments of the ML constructor P' are DBL terms, one f-or each of P's arguments. Thus the denotation of the constructor P' is a DBL predicate over DBL terms; P'(A', B') denotes the DBL predicate P(A, B) .

Although it is possible for the DBL and the ML to have different domains of individuals, it is technically convenient to make them identical. This will make the correspondence be­ tween quantified expressions in the two languages easier to state. To as~ert that the DBL's model actually has enough individuals, the denotation and naming functions must be introduced into the metalanguage.

It is often useful to know, in the ML, what individual a DBL term refers to. The denotation function 1::. is used for this purpose; 7 it takes a DBL term as its argument, and ·returns the individual denoted by that term. In the ML, the sorts of the argument and result of the denotation function are given by:

The 1::. function can be understood more easily by examining the denotation map for individuals in the ML and the DBL; it maps between a DBL term and its referrent. Because, in the ML, A' refers to the DBL term whose denotation is the same as the ML term A, we write:

5.2 Standard Names

In any language, there may be many different names for the same individual; e.g., we could speak of the Lafayette as "the ship commanded ' 'I Jones." Such names might change their denotations in different circumstances, however. It is handy to have a name for each individual that is always guaranteed to refer to that individual; these are called standard names. All of the constant terms that we will introduce into the DDL will be such standard names (e.g., LAFAYETTE from section 2},

1 Church )2) introduced the denotation function to formally describe the denotation of terms in the object language.

since there is no need to have more than one constant term for the sarne individual in the DBL.

In the ML, it will be useful to construct the standard DBL name for individuals. We define the standard name function 11 of one argument, an individual. The value of 11 is the standard DBL constant term that refers to that individual. Thus we would write:

and

In the denotation diagram above, 11 is the mapping from in­ dividuals to their standard name in the DBL.

We state here two useful properties of the standard name function:

The ML function =' constructs the DBL equality predicate of its two arguments. DNl essentially says that the two DBL standard names for different individuals actually do refer to different individuals. DN2 establishes 11 as the DBL standard name function for all individuals referred to by the ML, because it guarantees that the denotation of an individual's DBL name is indeed that individual.

5.3 Quantified DBL Expressions

Quantified DBL expression are constructed with the ML functions some and all. Both these functions take three argu­ ments: a DDL variable name, a DBL sort, and a DDL expression. We will generally use ML constant terms t' and s' to denote DBL tuple variables t and s, and primed constant terms to denote the corresponding sorts in the DBL. Thus:

5.4 Corner-Quotes

The abstract syntax can be a cumbersome way of naming complicated DBL expressions within the ML. To reduce the notational burden, we introduce an abbreviation device: we will let a DBL expression stand for itself in ML formulas. The DBL formula will be set off with corner-quotes from the rest of the ML formula so that there is no confusion. Here are some examples of the use of corner-quotes:

The translation between corner-quote abbreviations and their corresponding ML terms is straightforward: all predicate and term symbols in the corner-quote expression are replaced by primed symbols, and booleans and quantificrs map back to their constructors in the ML. It should be noted that the corner· quote convention is strictly a device for abbreviation of ML terms; it does not introduce any logical machinery into the ML.

It commonly occurs that ML terms of the form 11(x) are found in DBJ. term constructions, where x is a ML variable ranging over individuals (sort l N DS). We therefore extend the corner-quote conventions so that if a ML variable of sort IN DS occurs within corner-quotes, it translates to the standard name of that variable. So, for example, the denotation axiom DNl would be written as:

where rx f= y 1 is an abbreviation for not(ry(x) =' ry(y)).

In addition, Wf' allow ML variables of the sort D!JFS to ap­ pear within corner-quote abbreviations; they remain unchanged in translation. The only use of this convention will. be in P6 in section 7.2; there, ·for example, r'rlt/sHTPRJ' is an abbreviation for all(t', SH l PR', f), where f is a ML variable of sort DBFS.

6. Some Query Derivations

We are now in a position to state the relationship between the ML predicates DOC, COM, etc., and the relations of the database. Suppose it is the case that the database contains complete information about the commander of every ship, so that there is an {officer,ship} tuple in the COMMANDR relation for each officer and ship in the domain of discourse. The correspondence between the COM predicate and the COM MAN DR relation can be stated as:

Note that because of the corner-quote convention, x and y will be replaced by ry(x) and ry(y) in the ML term naming the DBL expression. P3 can be used to derive database queries relating to the COM predicate.

Example. The query to be answered is "Does Jones com­ mand ship USN123?" By Tl, this is expressed in the ML as:

If the standard DBL names for Jones and USN123 arc also JONES and USNl23, then by ?3 the equivalent DBL expression is:

A more complicated correspondence exists between the DOC predicate and the SHIP R relation:

The first two assertions state that if the tv! EDIC element of a SH ll'R tuple is T, then there is a 'doctor on board the ship; and if it is F, then there is not. The last assertions says that theM EDIC field will always contain one ofT or F.

Ezample. The query to be answered is "Is there a doctor on board USN123?" From Tl, the ML expression is:

By using ?4 above, either of the following two DBL expres­ sion can be proven to satisfy Q3:

Given just ?4, it is not possible to find a DBL expression corresponding to the query, "Is Jones the doctor on board USN123?" The domain of discourse represented by the DOC predicate properly subsumes the database's inform&· tion on the subject. Thus it is possible to represent this query in the ML, but not in the DBL.

7. Incomplete Inform,tion

In the previous section, we encountered an example of a clatabasc which had incomplete information about the domain of discourse: there was no representation for which doctor was on board a ship, just an indication that some doctor was present. In this section, we will examine a few of the more common ways in which a database may have incomplete information about the domain . This catalog does not exhaust the possiblities available for characterizing the relationship of a database to its domain within the ML; but it does show how to deal with a few of the more common situations that arise in practice.

7.1 No Attachment for a Predicate

It often occurs that some part of the domain of discourse is just not referred to at all by the database. For the sake of con­ ceptual completeness, for example, we may allow the user to ask about properties of ships that are not included in the database under consideration. In this case, there will be a predicate in the ML that refers to the property, but no corresponding DBL tuple set. The ability to deal with this type of incompleteness is particularly important in building systems that must interact with users who are unfamiliar with the contents of a database.

A special case of this type of incompleteness occurs when a ML predicate has only a partial correspondence in some database relation. An example of this is the DOC predicate in the previous section (axiom P4); only ML queries involv­ ing existential quantification over the doctor argument could be answered . Partial correspondence of a ML predicate is charac­ terized by the ability to find DBL expressions for some, but not all of the ML queries containing the predicate.

7.2 Only-if Incompleteness

The correspondence previously stated between the COM predicate and the COMMANDR relation, expressed in ?3, used an equivalence connective. The only-if half of this connec­ tive is important for the derivation of DBL expressions equiv­ alent to ML formulas involving COM. This is because the only­ if half of ?3 states that if the tuple {A, B} is not present in the COM MAN DR relation, then A does not command B.

In many cases, however, the interpretation of a database relation is that if a tuple is present, then the relationship holds between those individuals; but if it is not present, it cannot be inferred that the relationship docs not hold . All of the positive instances of the relation correspond with the domain of discourse, but not the negative instances. For example, it may be the case that all of the commanders of U.S. naval ships are known, but not those of foreign naval ships. Then the axiom ?3 is too strong, and must be weakened to an implication:

This axiom is not strong enough to allow the derivation of equiv­ alent DBL expressions Cor the COM predicate, but may still be useful in an intelligent question-answering system. Failing to find a proof of an instance of Tl for a ML query, such a system might weaken Tl to find a DBL formula that implies, but is not implied by, the original query. If a positive answer is returned from the database, then the original query is true; if not, no conclusion can be drawn.

7.3 Domain Incompleteneaa

Since the DBL is a tuple calculus, there is no ex­ plicit quantification over subdomains of INDS, e.g., SHIPS, OFFICERS, etc. How then can DBL queries be formed that ask whether a property holds for all the members of one of these sets? For example, consider the ML query:

This asks whether all ships have a length greater than 344.4 meters. Suppose we aaaume that every ship length is represented in the SHIPR relation:

PS is not sufficient to answer QS; the reason is that we have not stated anything about whether all ships are included in the SIIIPR relation or not. A counterexample to the truth of QS would be a domain where there were some ships that did not have lengths. The best we can do with PS is to derive the equivalent ML formula:

where there is still a ML quantifier over all ships.

Domain incompleteness is thus automatically assumed un­ less explicit non-logical axioms are included to counteract it. For the ships world we are using as an example, we want to say that all ships in the domain are to be found in the SHIP R relation; on the other hand, not all LENGTHS or NAMES need be present. That is, the domain LENGTHS is assumed to be the rational numbers in the interval (say) [100, lOOOj; at any given moment, only a finite subset of these will be present in the Sl!IPR relation. Similarly, more NAMES are available than are in use.

To state the completeness of the SHIPR relation with respect to SHIPS, we assert:

That is, a universal quantifier over SHIPS can be moved inside the DB predicate to the SHIP R relation. The use of P6 enables us to prove that the following DBL expression satisfies QS:

On the other hand, because there is no explicit domain com­ pleteness axiom like P6 for LENGTIIS, the question "Is there some ship of every length?" cannot be answered by a DBL query.

The ability to correctly represent that the database has only partial information about a domain of individuals enables us to allow infinite domains in the database, without deriving DOL expressions that yield counterintuitive truth values for ML queries. If answering a ML query involves quantifying over an infinite domain, then no equivalent DBL expression will ever be generated for it.

8. Other Issues

In this section we will briefly describe how open queries can be accomodated in the metalanguage approach. We will also examine some of the ways in which a question-answering system might use the representation to respond intelligently to user queries.

8.1 Open Queries

Open queries are queries whose answer is a set of in­ dividuals, rather than a truth value. In the metalanguage, open queries can be represented by a formula that has one or more free variables in it. The answe· 1 o the query is the set of those individuals that, when substitu,ed for the free variables, make the query true. 8 For simplicity, we will consider open formulaa with only one free variable. The free variable will be indicated by enclosing it in square brackets next to the ML formula: M[x] is a ML formula with free variable x. Free variables in the ML will always be of the sort IN DS.

In the DBL, we will allow free variables over the simple (non-tuple) domains. Because of the finiteness of the DBL tuple domains, DBL expressions involving free variables have the im­ portant property that only a finite set of individuals will satisfy the expression when substituted for the free variable. 9 A DBL query with a free variable is thus guaranteed to return a finite set of individuals; further, bctause or the computational properties of the DBL discussed in the second section, there exists an al­ gorithm for determining this set.

The problem of finding a DBL open formula that cor­ responds to a ML open formula can be stated in terms similar to Tl, the schema for closed queries:

Here f[al'l(x)] is the DBL expression constructed by substitut­ ing the term 71(x) for the free DBL variable a in f. If a con­ structive proof of T2 can be found, then it will yield an open DBL formula whose truth value is the same as that of M[x] for every individual x.

8.2 Types of Questions and Answers

The ability to formalize the relationship of the database to the domain opens up new possibilities for intelligent response to a user's queries. One type of query that can be readily handled in this framework is a request concerning what information the database has about the domain. For example, suppose a naive user wants to know if the database has information about what doctors are on board which ships. This question could be phrased in the ML as:

'Vxl SHIPS 'Vyl DOCTORS [3/ I DBFS DB(!)= DOC(x, y)J

8 Reiter jl2J extends the notion of the an1wcr to an open query to di1junctive combinations of individuala, e.g., "either Smith or Jonea comma.nda the Lafayette." We do not consider this complication here.

0 To show this, it is necessary to exclude from the DBL expre11ion1 or the form a = a, where a is a free variable.

If this ML formula could be proven, then any query about individual doctors and ships could be answered. Note that we are not interested in evaluating the DOL formula that is a binding for f in this case; rather, we wish to establish the existence of a class of DOL formulas.

In a more speculative vein, we might consider integrating the MLIDBL framework with current Al formalisms for the representation of changing states of the world, most notably the situation calculus [10]. Suppose each ML predicate were extended to take an additional argument, a situation in which the predicate was to hold. Thus DOC(x, y, s) would mean that x was the doctor on board y in situation s. There would be some distinguished situation SO, the current state of the world, about which the database would have information.' It would then be possible to correctly represent and answer user queries that made the distinction between a proposition always being true of the domain, as opposed to true in the current situation. For example, consider the two queries:

Is there always a doctor on every ship? Is there a doctor on every ship now?

The first of these can only be answered by proving a ML formula over all situations; the second can be answered by consulting the current state of the database.

If several previous copies of the database are kept around, then it is also possible to answer queries about past situa­ tions. Suppose, for example, that the day associated with each situation is kept in the ML, and a separate copy of the daily database is available for querying. Then queries such as "Do more ships have doctors on board today than yesterday?" could be answered by evaluating two database queries and computing the answer from the values they returned.

9. Relation to Other Work

Some recent work in formalisms for database representation has been collected in [4]. This work differs broadly from the ap­ proach presented here in that the dabatase is viewed as a set of ground atomic sentences in a first-order theory of the domain of discourse, rather than as a model. There arc several disad­ vantages to interpreting the database as part of the syntactic description of the domain, which the approach described here does not suffer from:

• Because the database tuples are taken to be part of the lan­ guage that describes the domain, special algorithms must be formulated to translate from a formula containing non­ database predicates to an equivalent one containing just database predicates.
• Special assumptions about incomplete information must be made, because it cannot be assumed that the negation of a tuple not present in a relation holds. These special assumptions, which have been called the Closed World As­ sumption and Domain Closure, do not always correspond with our intuitive notions about incomplete information in the database, and do not give the required flexibility in axiomatizing the relationship of the database to the domain.
• The representational power of the first-order language used to describe the domain is severely restricted in order to carry out database query derivation in the presence of the incompleteness assumptions. In particular, these systems forgo the use of existential quantification and function sym­ bols in axioms that connect the database· and non-database predicates. This means, for example, that a relationship

such as P1 could not be encoded.

The systems described in i'IJ suffer from these limitations lo a greater or lesser extent, depending on which trade-ofT they choose to make. For example, Chang 111 chooses a very restric­ tive form for his axioms, but has a simple algorithm for deriving equivalent formulas that involve only database relations. Heiler Jl2l relaxes these restrictions somewhat, and also gives an exact account of the assumptions being made about incomplete infor­ mation; but his derivational algorithm is more complicated.

It should be mentioned that the criticisms leveled above apply to the so-called evalualional approach to database query derivation, which is assumed in this paper. That is, the database is presented a priori, and must be addressed by a separate query processor whose communication overhead is high relative to deduction outside the database. With this assumption, it is reasonable to try to transform the full query to one that can be evaluated all at once against the database. Other systems, such as J7J, assume a much tighter coupling between the database and the non-database parts of the first-order theory. The database is assumed to be simply a repository for atomic ground formulas that can be accessed during the course of a proof, although some attempt is made to minimize the total number of accesses.

10. Conclusion

We have taken the view that the information content of a relational database can best be represented as a model of a particular type of first-order language, a tuple relational cal­ culus. This view has proved particularly useful in two respects. First, by axiomatizing the database language and its associated rnodel in a metatheory, we have been able to describe in a power­ ful and flexible manner how the database corresponds to the domain of discourse. This is a representational advance, be­ cause AI systems that must address databases need just this facility. Secondly, viewing the database as a mechanizable model of the DBL enables us to take advantage of the computa­ tional properties of database query language processors. Once a database query that is equivalent to an original query is derived, it can be evaluated against the database to determine the truth of the original query. Thus the algebraic operations of the database processor can be incorporated in an elegant way into the deductive process of question-answering.

A final word about implementation. An initial algorithm that incorporated some of the ideas about incomplete infor­ mation in the database was implemented for the D-LADDER project J81 . A restricted first-order language (the conceptual schema) was used to represent the domain of discourse, and a query expressed in this language was transformed by the algorithm into the database language SODA 1111. However, th is algorithm did not take advantage of the power of the metalanguage encoding. In KLAUS, an intelligent knowledge­ acquisition and question-answering system, we intend to imple­ ment the ML/DBL structure as described in this paper, and explore the cpmplicated issues of deduction that will arise.