Automatically Inferring Database Schemas

1. Introduction

The goal of this research is to investi&ate the pos~~ibility or automatically inferrin& a database schema. The state or the art in database desi&n is that, to create a database for a particular applica­ tion, one has to expreu one's needs usin& certain concepts and nota­ tion specific to the database-management system. The penon creat­ ing the database thus has to deal with concepts forei&n to the ap­ plication domain. Even for an expert, this is a tedious and error prone task. Our motivation is to make the task for the database designer easier. We desire that the designer should only be concerned with providing a picture of how s/he expects the database to be used and that the system should synthesise a schema from thia infor­ mation.

Figure above provides a pictorial illustration of a database schema. We have chosen the functional data modei!Shipman Sli!Nikhil 84J to express such sehemas. A functional data model can be envisioned as a collection or database types (entities) together with a set ortunctions that operate on these database types. We shall represent a schema in this model by a collection of expressions or the form, 1(a)- /1, where Tis to be thou&ht or as a function whose domain is of type a and whose ran&e is of type {J. We will call an expression of thia sort a database structure. Thus the above database schema, for example, will be represented by the followin& collection of expreuiou.

student() - entity faculty() - entity course() - entity name(student) - strin&

enroll(student) - course

0 Thio work io paniall,y 1upponed by &he NSF Jr&D& ofMCSII-47180 A02

teach( faculty) - course department(course)- strin& advise( faculty) - student

We expect the database designer to provide a picture of the database by specityin& sample English queries that the database sys­ tem might be expected to answer. The followin& set of queries mi&ht serve this purpose for the above database.

1. Name the students enrolled for a course
2. Which faculty teach a course in the cia department!
3. Which faculty advise students!

From these queries we expect our system to synthesise the above database schema ··.

The task of automatically inferring a database schema may be viewed as a problem in learning. Moat of the work in machine learn­ in& has concentrated on inductive inference !Plotkin 7111Shapiro 81J and concept learning IMitchell82). The assumption made in th-; methods is that the input is in some formal lan&uage and generalisa­ tions formed from them are expressed in the same language. Our work diffen in that our input is in the form of parse trees or English sentences and the generalisations formed from them are expressed in the functional data model. That is, the input and the generalisations formed are expressed in different formalisms; this disparity makes it difficult to characterise the mechanism that forms the generalisa­ tion. This work also differs from those mentioned above in that they use notions such as 11.1b1umption to form generaliaation !Plotkin 71) or impose some ordering on the hypothesis space !Shapiro 81l!Mitchell82J, whereas we attempt to exploit certain features of the input, namely the syntactic structure of the sentence, to form abstractions from the input data. However, as this research develops we might take advantage of the notion· tuch as subsump­ tion and other techniques advanced by the above approaches to form further inferences or impose an ordering on the hypothesis space.

In the following aec:tions we address the iaaue of automatically inferring a database schema in some detail. In aec:tion 2 we outline our basic: approach. In aec:tion 2.1 we will explicate how information pertinent to the database structure is extracted from individual queries. Section 2.2 discusses how the information from different queries might be integrated to synthesise a database schema.

2. Inferring a database schema

The approach that we follow is that of constructing the . database schema incrementally in the following sense. Each query 111 processed one at a time and the following two tasb are performed. Fint the database structures corresponding to the query are in­ ferred. Then an attempt is made to integrate this into the existing partial database schema. We discuiiS these two aspects in detail below.

1.1. InferriDI databue ltrueturee from Individual querlee Database structures are abstracted from queries essentially mappins each individual query into a correspondins set of database structures. It is obviously not sensible to desire to do this by llll­ sociatins a rule with each query since there are far too many queries. What we require is a process that can be described in a finite manner but which is still capable of mappins a larse set of queries into the appropriate structures. To achieve this soal we view a query as bein& composed of several smaller pieces, which are in particular its syntactic constituents. We then associate rules with specific syntactic constituents, each such rule performins the task of mappins the associated syntactic structure into a correspondins database structure. The database structures correspondins to an en­ tire query are obtained as a cumulative effect of applyins these rules to syntactic substructures or the query.

00 We are a& thio otap merely in&ere~ted in inrerrinc an appropriate ~chemL We are no& a& &he moment conceminc ounelvet with &ho undoubtedly Impor­ tant tuk or UtociatinJ a ,..oced·re with each or &he rundion namet.

Each or the rules is motivated by the function the associated syntactic structure serves in a database settins. For example, noun phrases generally correspond to objects (database types), preposi­ tional phrases to properties of objects, and verbs to relationships be­ tween objects. We can capture these seneralities by associatins rules that map, for example, noun phrases to objects, prepositional phrases to properties of objects and etc. We present below examples or some rules. Before doins so we need the followins notions.

Deftnltlon 1: a dominates /3 if /3 is an immediate son of a. For example, in the tree below, a dominates /3. In the case of a parse tree of an Enslish sentence, if NP dominates PP it is to be under­ stood as the PP modify ins the NP.

/3 Deftnltlon J : DB-property

i. Ir a is an NP and /3 a PP and a dominates /3 then

a. if the preposition in {3 is 'of then the common noun or a is a DB-property of the common noun (object) or /3.

b. otherwise, the common noun or /3 is a DB-property of the common noun (object) of a.

ii. Ir a {3 is a noun-noun compound and a is not an in­ stance or {3 then a is a DB-property of the common noun or /3.

For example, if the above defmition is applied to the query 'What are the names or students in the database course!' we set name as a DB-property of atudent. Similarly, for the query 'Which faculty teach a course in the cis department!' we get department as a DB­ property of atudent, and for the query 'Name the students enrolled for a course!' we get name as a DB-property of atudent.

Now for a few sample rules: Syntactic Structure S 1 : Noun Phrases. Motivation for the rule: Common nouns correspond to ob­ jects (database types). Rule R 1 : Common nouna that do not denote DB-propertiu fbll definition e) denote databaae tlJpea (entitiea}.

Syntactic Structure S2: a dominates one or more structures

/3, ,.,, ... where a is a NP and /3, ,.,, ... are PP's

Motivation for the rule: Preposition phrases correspond to properties or objects.

Rule R 2 : For each atructure that a dominatea, i.e., /3, ,.,, ... the common noun which ia a DB-propertlJ fb11 definition e) of an object denotea the function name and the object itaelf denotu the t11pe of the domain."··

Syntactic Structure Sa: A sentence structure with a as its subject NP and one or more structures /3, ,.,, ... conjoined to the right of the main verb where /3, ,.,, ... are either NP's or PP's. Motivation for the rule: Verbs correspond to relationships between objects. Rule Ra: The main verb denotea the function name. The common noun of the aubject NP denotea the type of the domain of the function. The range of the function ia then-tuple <r1, rg, ... , rn>, where each r; ia the com­ mon noun of {3, ,.,,. .. conjoined to the right of the main verb

We will now illustrate the use of these rules to infer database structures from the parse trees of queries. The assumption being made here is that parse trees of queries can be obtained and that the parsins mechanism uses a standard Chomsky transformational grammar and also filters out tense and infiectional markers. A r~le is trissered if the structure associated with it matches a structure an the parse tree. Further the rules are unordered and that a single parse tree potentially trisgers more than one rule. Examplea 1

Ql: Which faculty teach a course in the cis department!

Parae tree:

cis· departaent

The syntactic structure S 1 occurs in this parse tree ····, and so the associated rule R1 is applied to yield the database structure

faculty () -+ entity

course () -+ entity

The syntactic structure S2 also occurs in the parse tree, and so the associated rule R 2 is applied to yield the database structure

department(course) -+ strins . . Finally, the syntactic structure Sa occurs m the parse tree and thiS triggers the rule Ra to yield the database structure

teach( faculty) -+ course

J.:t. lntearatlns databue lltructuree

The task here is to integrate the information inferred from in­ dividual queries to form a cogent database schema which is concise and consistent. Two database structures are confiicting if they as­ sign different types to the same function. A database sch~ma is c~>n­ sistent if no two structures in it conflict. The process of mtegratms can be thought of as consistins or two tasks: one task is to i~entify confiictins database structures and resolve them. The other 18 to represent concisely the database schema.

000 The infonnation provided by the pane tree is not adequate to infer the type or the ranee. Some additional infonnation and heuristics .are ~q~ired for this purpo.e. For the present we will not concern ourselves wttb th~ lBSUe.

····we assume that in a noun· noun compound, n 1 n2, if n 1 is an insb.nce or n 2 then n 1 is marked by the paner. Hence 'cis' is marked in the above pane tree. The motivation here is to facilitate the identification or the common nouns.

1.1.1. Resolvlns Conftleta

Connicting database structures are inferred from queries and in fact they can be inferred from a single query. There are at least two circumstances that could potentially result in connicting hypotheses ···oo. First, due to the inherent ambiguity of natural lan­ guage, it is possible to generate multiple parse trees for a single query. These distinct parse trees may give rise to connicting hypotheses. For example, consider the query

Q2: Which student is taking a course in the cis department! There is ambiguity in where the PP - 'in the cis department' should be attached, thus yielding the two potential database structures,

• (i) take(student) -+ course
• (ii) take(student) -+ <course, department>

Second, application of different rules to a single parse tree may also lead to connicting hypotheses. For example, consider the query

Q3: What are the grades of the students in the seminar course! This query gives rise to the connicting database structures

• (i) grade(student) -+ string
• (ii) grade(student, course) -+ string

In certain situations different functions may be inferred that actually bear a common name. For instance, from the query in Example 1, we can infer the database structure,

(i) course() -+ entity

From the query Q3, we infer the database structure,

(ii) course( student) -+ string The functions in (i) and (ii) are actually different; the function in (i) returns all entities of type couru whereas the function in (ii) returns the cour8e-name the entity 8tudent is enrolled for. Functions of this sort are said to be overloaded. A set of hypotheses which include overloaded functions could also be mistakenly identified as connict­ ing hypotheses. It is therefore important to distinguish between these two cases.

In order to resolve connicts we need to address two issues. First, distinguishing between function overloading and connicting hypotheses; second, resolving connicting hypotheses. H only connict­ ing hypotheses were present, then these could be resolved easily. For example, from the additional information (the existing partial database schema or the incoming data) if hypothesis, h1, is inferred and if h 1 happens to be one of the connicting hypotheses then we can resolve the connicting hypotheses in favour of h 1 . But the presence of overloaded functions rules out such a straightforward ap­ proach toward resolving connicts. Alternatively, if negative ex­ amples were provided in the input data then this information can be used to rule out certain hypotheses and this may help resolve con­ flicting hypotheses. Since it is hard. for the database designer to ex­ press in terms of what requirements the database should not satisfy we will assuming only positive instances to be provided. From the above arguments it is clear that we are unable to resolve connicting hypotheses and indeed even to distinguish between these and over­ loaded functions. Therefore, as a last resort we will turn to the database designer (user) to provide some crucial information which will aid the task of distinguishing between connicting hypotheses and overloaded functions and resolve connicting hypotheses.

We will brieny give an overall picture of how the interaction with the user is carried and then illustrate it through an example. A common representation will be adopted to express both confiicting hypotheses and overloaded functions. They are represented by a disjoint union. For instance, Jl: A or 8, is a disjoint union where hypothesis Jl is either A or B. Let us assume we have such a set Jl. Now from the additional information (the existing partial database schema or the incoming data) say a hypothesis, h1, is inferred and h 1 is also part of Jl. Since we have gathered more evidence on a hypothesis belonging to the disjoint union we could use this infor­ mation to assess the other hypotheses in the disjoint union. At this stage we initiate the interaction with the user by asking it the other hypotheses in Jl, i.e., {JI- h1}, can be discarded. If the user's response is 'yes' then }I can be thought of as connicting hypotheses and it can be resolved in favour of h 1 . If the user's response is 'no' then }I can be construed as overloaded functions. The following ex­ ample illustrates this, Consider we have formed the disjoint union, )(, for the connict­ ing hypotheses inferred from query Q2. Next from the additional information it we infer the following database structure

·····we will use· the terms eon/lidinf Aypotlanu and eon/lidinf 4ata6ate ltruduru interchanceably.

h 1 : take(student)-+ course······

Obviously the above database structure is one of the hypothesis in Jl hence at this stage the user is asked the explicit question

Can {take(student)-+ <course, department>} be discarded! If user's response is 'yes' then the connicting hypotheses Jl can be resolved in favour of h 1 . If user's response is 'no' then }I is construed 1as overloaded function.

1.1.1. Conel~~eneu of repre.entatlona Type hlerareh)o

It is possible to encode information economically by arranging the objects or the database in a hierarchy using the notion or sub­ type. A database type a is a subtype of a database type fJ it all functions defined on fJ must be defined on a but a may have other functions defined on it. That is, the subtype inherits all the properties of its supertype. This provides an economy in represen­ tation since we need represent the common properties of the subtype and the supertype only once at the supertype. The information per­ taining to the type hierarchy can be inferred but due to space limita­ tions we shall not discuss them here.

The notion of 8ubtype is also used for another purpose, to iden­ tify whether two functions are the same. For example, from the query - 'What are the names of the persons in the university!'; we infer the database structure,

• (i) name(person)-+ string and from the query - 'What are the names of the students enrolled for cisllO course!'; we infer

(ii) name(student) -+ string

If 8tudent is a subtype of per8on then both (i) and (ii) can be con­ strued as a single function and a single procedure can be attached to both these functions.

3. Summary

In this paper we have indicated an approach to the problem of automatically inferring database schemas. Our motivation is to make the task for the database designer easier. The designer need only provide an idea of how s/he expects the database to be used and that the sy8tem synthesises a schema from this information. We have chosen the functional data model to express database schemas. The crux of the inference mechanism is to exploit certain features of natural languages, namely, the syntactic structure of sen­ tences, to form abstractions.

4. Acknowledgments

I acknowledge gratefully the support and encouragement provided by Aravind Joshi and Rob Gerritsen. Many helpful ideas and criticisms were provided by Julia Hirschberg, Kathy McCoy and Gopalan Nadathur.

5. References

• [1[ Mitchell, T.M. ·Generalization as search", Artificial Intelligence. Vol. 18, No. 2, (1982) 203-266.
• [21 Nikhil, R.S. · An Incremental, Strongly typed, Database Query Language· PhD thesis, Dept. of Computer and Information Science, University of Pennsylvania, Philadelphia, 1984.
• [31 Plotkin, G.D. · Automatic Methods of Inductive Inference· PhD thesis, Edinburgh University, 1971.
• [41 Shapiro, E. "Inductive inference of theories from facts· Tech. report 192, Dept. of Computer Science, Yale University, New Haven, 1982.
• [51 Shipman, D.W. "The Functional Data Model and the Data Language DAPLEX· ACM transactions on database systems 6(1), (1981) 140-173.

······This can be in( erred from a query, 'which student U takin1 a databue coursef'