Science, Faculty of
Computer Science, Department of
DSpace
UBCV
McClement, Gregory J.
Master of Science - MSc
University of British Columbia
One major concern with natural language interfaces is dealing with the problem of porting the system from one domain to another. Early approaches required that significant parts of the system be rewritten. Improvements have been made to the point that a system can be configured for a new database by a database expert who has no special knowledge of Computational Linguistics. Unfortunately, this has not yet lead to the widespread use of natural language interfaces. Proposed here is a natural language interface that can he configured by a user that has no knowledge of Computational Linguistics and no knowledge of databases ie - no knowledge of formal query languages, no knowledge of relational databases and no knowledge about how the data is organized in the database. Such a user merely needs to know some specific information about the domain that is modelled by the database. For an employee database, specific information is knowledge about a particular employee, eg - their name, address, and department.
6973307 bytes
application/pdf
Improving the Portability ofNatural Language InterfacesThrough LearningbyGregory John McClementB.Sc., The University of Regina, 1989A THESIS SUBMITTED IN PARTIAL FULFILMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF COMPUTER SCIENCEWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIANovember, 1993© Gregory John McClement, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)Department of Cc-AA r -ker. SCleV\C eThe University of British ColumbiaVancouver, CanadaDate ^6 (993DE-6 (2/88)AbstractOne major concern with natural language interfaces is dealing with the problem of portingthe system from one domain to another. Early approaches required that significant parts ofthe system be rewritten. Improvements have been made to the point that a system can beconfigured for a new database by a database expert who has no special knowledge ofComputational Linguistics. Unfortunately, this has not yet lead to the widespread use ofnatural language interfaces. Proposed here is a natural language interface that can heconfigured by a user that has no knowledge of Computational Linguistics and noknowledge of databases ie - no knowledge of formal query languages, no knowledge ofrelational databases and no knowledge about how the data is organized in the database.Such a user merely needs to know some specific information about the domain that ismodelled by the database. For an employee database, specific information is knowledgeabout a particular employee, eg - their name, address, and department.iiTABLE OF CONTENTSAbstract ^iiTable of Contents ^ iiiList of Figures ^viiiAcknowledgement ^ xiiiChapter 1 Introduction ^11.1 Contributions ^31.2 What Follows ^3Chapter 2 Natural Language Interfaces ^ 62.1 Question Answering Systems 62 1 1 ELIZA (Pattern Matching) ^ 72.1.2 LUNAR (Linear Paradigm) 82.1.3 PLANES/LIFER (Semantic Grammars) ^ 112.1.4 Case Frame Based ^ 13iii2.2 Desirable Characteristics ^ 172.2.1 Internal Characteristics ..... . .^................... . ^ 172.2.1.1 Portability ^182.2.1.2 Semantic Productivity ^ 202.2.1.3 Minimum Coverage 212.2.2 User Interface ^ 222.2.2.1 Habitable (User-friendly) ^ 222.2.2.2 Cooperative ^ 232.2.2.3 Robust with Respect to "Noise ^ 272.2.2.4 Handling of Discourse Phenomena 282.3 Learning Language ^ 312.3.1 Syntax 312.3.2 Semantics ^ 32Chapter 3 System Overview ^ 383.1 Objectives 383.2 Knowledge Base Components ^ 383.2.1 Domain Independent Knowledge ^ 393.2.2 Domain Dependent Knowledge 403.3 Processing Flow of Control ^ 413.4 Implementation Details 473.5 Examples ^ 47ivChapter 4 Linguistic Knowledge ^ 574.1 Lexicon ^ 574.1.1 Word Classes ^ 584.1.1.1 Domain Independent (Predefined) ^ 584.1.1.2 Domain Dependent ^ 594.1.2 Morphing ^ 604.1.3 Implementation of the Lexicon ^ 604.1.3.1 Inverted index 604.1.3.2 Implementing the Inverted index ^ 624.2 Grammar^ 644.2.1 Coverage ^ 644.2.1.1 Passives ^ 644.2.1.2 Relative Clauses 654.2.1.3 Wh-Question ^ 654.2.1.4 Possessives 664.2.1.5 Imperatives ^ 664.2.1.6 Noise Phrases 674.2.1.7 Semantic Grammar Based-Phrases ^ 674.2.2 Representation ^ 69Chapter 5 Becoming Portable Through Learning ^ 715.1 Tokenization ^ 715.2 Parsing 715.3 Learning Frames ^ 735.3.1 Case Frames 735.3.2 Object Frames ^ 745.3.3 Minimal spanning Trees ^ 755.3.4 Ambiguity ^ 1105.4 Learning Word Meanings 111Chapter 6 Question Answering ^ 1146.1 Example ^ 1146.1.1 Tokenizing ^ 1146.1.2 Parsing 1196.1.3 Semantic Analysis ^ 1236.2 Response Generation 1346.3 Learning Word Meanings ^ 1346.4 Handling Ambiguity 1356.5 Controlling the Dialogue ^ 136v iChapter 7 Conclusion ^ 1387.1 Contributions of this Thesis ^ 1387.2 Possible Enhancements 1407.2.1 Enhancements to Noun Phrase Interpretation ^ 1407.2.2 Learning Grammatical Structures ^ 1467.2.3 Enhancements to Verb Phrase Interpretation ^ 1467.2.4 Enhancements of the Parser ^ 1477.2.5 Enhancements Using Learning 1477.2.6 Enhancements Using Frames ^ 1487.2.7 Enhancements to the Database Interface ^ 1497.2.8 Inferences ^ 149Bibliography ^ 151Appendices ^ 155A Relational Database Terminology ^ 156B Grammar^ 159C Database Listing ^ 172D Database Interface 178E Test Runs ^ 180viiList of FiguresFigure 2.1 - Match - Response Patterns ^7Figure 2.2 - Sample Cases ^ 14Figure 2.3 - Case Frame For Fix 15Figure 2.4 - Non-passive Sentence ^ 16Figure 2.5 - Passive Sentence 16Figure 2.6 - Ambiguous Question ^ 26Figure 2.7 - Paraphrases ^ 26Figure 2.8 - Simple Choices 27Figure 2.9 - Ellipses ^ 28Figure 2.10 - Anaphora 29Figure 2.11 - Vagueness ^ 30Figure 2.12 - Part of a Concept Hierarchy ^ 34Figure 2.13 ^ 35Figure 2.14 - Arithmetic Field Acquisition (MAP83) ^ 36Figure 3.1 Knowledge Source Diagram ^ 39Figure 3.2 - Data Flow Diagram ^ 43Figure 3.3 - Case Attachment 45Figure 4.1 - Word Classes ^ 59Figure 4.2 - Part Table 61Figure 4.3 - Inverted Index for the Producer Column ^ 61Figure 4.4 - Part of a TRIE ^ 63viiiFigure 4.5 - Different Tokens ^ 63Figure 4.6 - Sentence Form 64Figure 4.7 - Relative Clauses ^ 65Figure 4.8 - Possessives 66Figure 4.9 - Imperative Sentences ^ 66Figure 4.10 - Noise Phrases 67Figure 4.11 - Example Employee Frame ^ 67Figure 4.12 - Semantic Grammar for Recognizing Object and Attributes ^ 68Figure 5.1 - Cases and Fillers for Sample Sentence ^ 72Figure 5.2 - Case Frame for Works ^ 74Figure 5.3 - Employee Object Frame 75Figure 5.4 - Tables Used by Examples ^ 77Figure 5.5 - Database Graph for Table of Figure 5.4 ^ 77Figure 5.6 - Three Minimal Spanning Trees for "Smith works as a clerk for 800dollars" ^ 78Figure 5.7 - GMST 80Figure 5.8 Example minimal spanning trees connecting "Smith", "Clerk", "800","Research", and "Ford" ^ 83Figure 5.9 - Another Spanning Tree For "Smith", "Clerk", "800", "Research", and"Ford" ^ 84Figure 5.10 - Generalized Minimal Spanning Tree ^ 85Figure 5.11 - 'Join' Edge Cost ^ 86Figure 5.12 - Tree Cost Calculation 88ixFigure 5.13 - Establish Value to Database Graph Node Correspondence ^ 90Figure 5.14 - Values Queue ^ 91Figure 5.15 - First MST 92Figure 5.16 - New Values Queue ^ 92Figure 5.17 - Connecting Ford 94Figure 5.18 - New Values Queue ^ 95Figure 5.19 - Connecting in 800 96Figure 5.20 - New Values Queue ^ 97Figure 5.21 - Connecting "Research" to "Smith" ^ 98Figure 5.22 - Next Values Queue^ 99Figure 5.23 - Connect in "Clerk" 100Figure 5.24 Pseudo-Code Which Generate GMSTs such that M <=cost(GMST)<= N ^ 101Figure 5.25 - Choice 1 ^ 102Figure 5.26 - Choice 2 102Figure 5.27 - Value to Node Mapping ^ 105Figure 5.28 - Presenting the User with Different Interpretations ^ 107Figure 5.29 - Search from Each New Node to GMST ^ 109Figure 5.30 - Search from GMST to all New Nodes 109Figure 6.1 - Example Sentence ^ 114Figure 6.2 - Initial Position in the Sentence ^ 115Figure 6.3 - Initial Position in the TRIE 115Figure 6.4 - Sentence ^ 115Figure 6.5 - Inverse Index 115Figure 6.6 - Sentence After 'h' ^ 116Figure 6.7 - TRIE after 'h' 116Figure 6.8 - Sentence after 'o' ^ 116Figure 6.9 - TRIE after 'o' 116Figure 6.10 - Tokens of the Sentence ^ 117Figure 6.11 - Possible Sentence Structure 120Figure 6.12 - Possible Syntactic Structure ^ 120Figure 6.13 - Possible Syntactic Structure 120Figure 6.14 - Possible Syntactic Structure ^ 121Figure 6.15 - Cases of the Only Parse Accepted 121Figure 6.16 - verbPhrase/3 ^ 121Figure 6.17 - nounPhrase/5 122Figure 6.18 - Case Frame for Earn ^ 124Figure 6.19 - Case Frame for Work 124Figure 6.20 - Object Frame for Employee ^ 125Figure 6.21 - Selecting Frames ^ 126Figure 6.22 - Query Groups 129Figure 6.23 - Graph 1 ^ 130Figure 6.24 - Graph 2 130Figure 6.25 - Union ^ 130Figure 6.26 - Main Query GMST ^ 131Figure 6.27 - Sub-query GMST 131Figure 6.28 - SQL for the Sub-query ^ 132xiFigure 6.29 - SQL for the Main Query ^ 133Figure 6.30 - Possible Ambiguity ....................................^135Figure 6.31 - Asking for Input ^ 136Figure 6.32 - Selection Option #1 136Figure 7.1 - Job Class ^ 144Figure 7.2 - Another Form of Classes ^ 144Figure 7.3 - Preposition used as Particles 147Figure A1.1 - Oracle Sample Database ^ 156Figure D.1 - whereLocation/2 ^ 178Figure D.2 - where_prefix/3 178Figure D.3 - SQL Access Predicates ^ 179xiiAcknowledgementsI am indebted to my research advisor Dr. Richard Rosenberg. His initial advice helped meto select a concrete problem to solve and his insight, patience, and supervision fostered thedevelopment of a realistic solution. His careful editing and suggestions enhanced my work.I would also like to thank my parents, John and Joan, who have always supported me inmy endeavours and special thanks to my wife, Dawn, who encouraged me to further myeducation.Chapter 1IntroductionEveryday, more people begin to use databases for their work. Many of these people are notexperts on database technology and do not want to become experts, but they still wantaccess to the information in databases. In many cases, access to the information in thedatabase is obtained through a programmer who writes programs to produce report., for theuser. Many people are unhappy with both the cost of producing a report and the delaybetween asking for a report and receiving the report. This has lead to the demand for user-friendly database management systems which a naive user can employ directly.A number of different approaches have been taken to try to achieve user friendliness. Foreach approach, there is a different tradeoff between ease of use and sophistication of theresults. The two most common approaches are to provide a menu driven interface and aformal query language. A less common approach is to use interfaces which interpret naturallanguage.Most commercial database management systems (DBMS) have a menu driven interfacewhich allows the user to produce reports. Typically, the user is asked to select a number of2database tables to use in the production of the report. The system then presents the userwith a report template which can be manipulated manually to produce the final form of thereport. After the user is satisfied with the template, the report can be generated. Thedisadvantages of this approach are that production of arbitrarily complicated reports is notpossible and the user must know something about the internal structure of the database.Another approach to providing access to databases has been to provide query languagessuch as SQL. Query languages are a powerful tool for generating reports quickly andaccurately. Unfortunately, query languages are not easy to master for people inexperiencedwith computer programming languages. Many people do not have the background necessaryfor learning query languages. Although they provide a means to produce reports quicklyand accurately, many users find query language too difficult to use. Another problem withquery languages is that users still must know about the structure of the database.The less common approach to providing access to information in databases is to use naturallanguage interfaces. The goal of this approach is to allow the user to access the database ina familiar way. This approach does not require that the user learn unnatural querylanguages or that the user know how the database is structured internally. Ideally, the userswould be able to tell the natural language interface what they wanted using concepts thatare familiar. One of the problems with natural language interfaces is that a database expertwith some knowledge of Computational Linguistics must be used to transfer them from onedatabase to another. This thesis explores one approach that could be used to allow the usersthemselves to configure the natural language interface for a database.31.1 ContributionsThe contribution of this thesis is to provide a simple means to translate the user'sknowledge into the knowledge of the system. The approach presented in this thesis, allowsthe system to access the knowledge of the user in order to configure itself to a newdatabase. In order to achieve this, the user does not need to know about the internalstructure of the database or learn a formal language. The user merely describes the data inthe database using words and concepts of his or her own choosing.The interpretations of sentences are represented with a special type of semantic net called aminimal spanning tree. The relationship between utterances of the user and the data in thedatabase is determined through use of these minimal spanning trees. The minimal spanningtree and its use in configuring a natural language interface comprise the major contributionsof this thesis. This is what allows the system to be configured so easily.1.2 What FollowsThis section briefly describes the contents of the remaining chapters of this thesis. Chapter2 contains a review of other approaches to developing natural language interfaces. Thisincludes general purpose natural language interfaces as well as systems that were developedto explore how learning could be used to enhance performance. A summary of desirablecharacteristics of interfaces is included.4Chapter 3 contains an overview of the system. A description of the high-level controlstructures of the system is presented along with information about the derivation ofknowledge. A sample run of the system concludes the chapter.Chapter 4 contains background information about the handling of the lexicon and thegrammar. Implementation details are presented along with information about the extent ofcoverage of the lexicon and grammar.Chapter 5 describes the major contribution of this thesis - the spanning tree approach toconfiguring a natural language interface. This chapter proceeds by examining a number ofexamples of the analysis process in action. The algorithm is presented along with a numberof considerations related to implementing the algorithm efficiently.Chapter 6 shows how the spanning tree data structure is used when interpreting questions.The process of analysis is examined in detail for a sample sentence, from the initialtokenization of the sentence to the final response to the question.Chapter 7 contains a summary of the contributions of this thesis along with a detaileddescription of a number of enhancements that could be made to the system to produce amore robust and powerful natural language tool.The appendixes contain information for readers unfamiliar with relational databaseterminology (Appendix A), the definite clause grammar used by the parser (Appendix B), alisting of the tables in the database used for the examples (Appendix C), a description ofthe interface to ORACLE (Appendix D), and test runs of the system (Appendix E).5Chapter 2Natural Language InterfacesMany attempts to develop natural language interfaces have been made during the last 30years. Some have been more successful than others but all serve to illustrate that naturallanguage analysis is a difficult problem. What follows is a description of some of theseattempts. Some well known systems are presented as examples of a particular approach todealing with the problem of interpreting language. After discussing these examples, generalobservations about natural language interfaces will be summarized. This section concludeswith a description of natural language systems that have used learning to enhanceperformance.2.1 Question Answering SystemsDuring the first 30 years of computational linguistics many approaches to natural languageprocessing were proposed. This section reviews some approaches which are related to thework done in the thesis.62.1.1 ELIZA (Pattern Matching) 7SentencePattern MatchingSemantics ResponseELIZA is a pattern matching system developed in the mid-60's by Weizenbaum(WEWEN66, WEIZEN67). This program attempts to maintain a conversation with aperson. The program has the role of a therapist and the person is a patient. For this system,pattern matching provided a simple means of analyzing input sentences in order todetermine a reasonable response. No sophisticated analysis of the input was attempted,instead the system associated a response pattern with each sentence recognition pattern.Some typical patterns are shown in Figure 2.1.Match Pattern Response PatternI am X How long have you been X?X you Y me What makes you think I Y you?Figure 2.1 - Match - Response PatternsThese examples illustrate that the system is not analyzing potentially large parts of theinput sentences. In order to analyze the sentence entirely, the system would have to beprovided with a large number of patterns. The need to provide large number of patternsmakes this approach impractical as a base for modern question answering system, althoughpattern matching can still be used to enhance other methods of sentence analysis or toprovide sentence analysis where the number of possible responses is limited. Further workin pattern matching approaches was explored in COLBY71.2.1.2 LUNAR (Linear Paradigm) Syntax Semantics RetrievalSentence Structure Query ResponseLUNAR, WOODS85, is characteristic of systems which were developed according to alinear paradigm. Under this approach, syntactic and semantic analysis were performedseparately. After initially analyzing the input using only syntactic information, the resultswere analyzed by a component that used semantic information. Unlike pattern matchingapproaches, the interpretation of the sentence was developed by combining the results ofanalysis of the components of the sentence. The theoretical base for syntactic analysis wasChomsky's Transformational Generative Grammars, developed in the late 1960's.Transformational Generative Grammar is a mathematical formalism which is used to definethe mapping of the surface structure of a sentence to it's deep structure. The surfacestructure is the sentence itself and the deep structure represents an equivalence class ofsentences with common meaning. One purpose of this mapping is provide a means toignore insignificant differences between sentences. The mapping from surface to deepstructure is defined using a grammar that generates parse trees and transformations of thoseparse trees. The following sentences have the same deep structure and are related to eachother by the passive transformation.John bought a car.A car was bought by John.89Augmented Transition Networks (ATNs) were proposed in WOODS70 as a means toefficiently analyze the syntax of sentences. ATNs are derived from recursive transitionnetworks (push down automata) by adding registers to keep track of information collectedduring parsing and adding tests on the transitions of the machine. The ATN analysisproduces the "deep structure" of the sentence which is then analyzed by the semanticcomponent of the system.The analysis of the deep structure of the sentence produces a domain dependentinterpretation which is used to answer questions or perform some task. Proceduralsemantics (WOODS85) is a common method of providing this interpretation. Forprocedural semantics, the meaning of a sentence is defined using procedures that areevaluated to implement a command, or answer a question. The procedures are defined interms of the information in a particular domain.Because syntactic and semantic analysis are separate, the syntactic information is relativelydomain independent. While this is a desirable property it has an undesirable consequence.Since no semantic analysis is performed by the ATN during the parse of a sentence, manyparses which are not semantically sound can be generated. The ATN does not stopanalyzing the sentence as soon as a semantic inconsistency is detected, so much work canbe wasted producing parses which did not need to be produced. There are alsodisadvantages which are associated with using an ATN itself.The ATN after backtracking will reanalyse components of the sentence because it does not10keep track of previous work. To avoid this problem, the ATN control structure must bemodified to keep track of partial parses. Problems also arise when the input containsdeviations from expected syntax. The ATN is dependent on the current state during theparse to control the alternatives expected and so it does not respond well to deviations.Procedural semantics is also a source of some problems.Under procedural semantics, the semantic information is domain dependent. Providing thesemantic information requires an expert and is time consuming. Procedural semantics isdefined in terms of the underlying database. This means that general facts such as "Allflights serve meals." and disjunctive facts such as "Flight Fl serves breakfast or lunch"cannot be represented in the system because they must be defined in terms of the querylanguage of the database management system and query languages do not have suchexpressive power, ALLEN87. Attempts to address this problem involve the use of anintermediate representation language (IRL) which serves as a domain independentrepresentation of semantic information as well as an interface to different DBMS querylanguages.Most of the significant problems with ATNs arise from the underlying approach - theseparation of syntax and semantics. Later approaches attempted to reduce this problem bycombining these stages of analysis. Semantic Grammar-based systems represented the firstattempt to address the problem of combining syntax and semantics.112.1.3 PLANES/LIFER (Semantic Grammars)SentenceSyntaxSemantics ResponseSemantic Grammars were developed to try to deal with the problems of approaches thatseparated syntactic and semantic analysis. Semantic grammars instead of using syntacticcategories of phrases such as noun phrase or verb phrase, used semantic categories such as"plane name" or "present command". Semantic grammars provided a simple yet effectivemeans for applying semantic constraints during the parse. But as a result each differentdomain of discourse required different semantic categories.SOPHIE (BUBR79) is a semantic grammar-based system developed to teach debugging ofelectronic circuits. For this system, measurements, voltages and parts are some of thesemantic categories. The PLANES systems (PLANES76) which accessed a database aboutaircraft contained semantic categories such as plane type, flights and flight hours. TheLIFER system (LIFER77) used with a naval database had ship, attribute, and port assemantic categories. There is a considerable variety of semantic categories among thesesystems.Semantic grammars are not a new way of representing sentence structure. They are a newway of using existing formalisms to represent structure. Because of this, tools for producingparse trees of inputs can be used to produce semantic grammar parses. During the parsingprocess the interpretation of the input can be constructed.12To handle interpretation of the input, there are query templates associated with the semanticgrammar rules. During analysis of the input, components can be identified and laterinserted into a particular query template. These templates are combined to produceprocedures that are implemented as a result of the query. ATNs or DCGs provide anenvironment where the construction can occur.A number of benefits are derived from the use of semantic information during the parsingprocess. The parser will not generate parses that have no meaning. A related benefit is thatthere is a reduction in the total number of grammatical parses. This means that inputs thatare syntactically ambiguous will not be ambiguous using the semantic grammar, so thissystem will be able to generate all parses quickly and there will be fewer parses. Spellingchecking is also more efficient because the semantic categories limit the number ofalternative words that must be checked. Not all of the benefits are related to efficiency.These systems can handle complex discourse phenomena effectively as well. Ellipsis can behandled by partially parsing inputs and determining their semantic categories. Once thecategories are known, previous inputs can be scanned looking for components in the samecategory. Once found the old component can be replaced by the new component in order toproduce an interpretation. Semantic grammars were found to limit the number ofalternatives enough to make this approach effective.The disadvantages of semantic grammars arise directly from the use of semantic categories.Different domains have different semantic categories and so have different semantic13grammars. To move the system from one domain to another requires specifying thegrammar again. Defining the grammar is time consuming and complex. The use ofsemantic categories affects the generality of semantic grammars. Other problems arise fromthis lack of generality. Semantic grammars need to contain many rules in order to havebroad coverage of the language. One reason for this is that general syntactic phenomena arestored redundantly in the grammar. For example, handling the passive form of sentencesrequires that productions be added for each semantic verb type. If some verbs are missedthen the system will not always accept passive sentences. This can frustrate users.A semantic grammar is one means to integrate syntactic and semantic analysis. However,the problems with this approach prevent the development of general purpose naturallanguage interfaces. Of the other approaches developed to try to handle the problem ofintegrating syntax and semantics, case frame based approaches were the most successful.2.1.4 Case Frame Based SyntaxSentence ResponsetSemanticsCase frame systems are basedupon case frames which contain syntactic and semantic information about a verb andrelated noun phrases. The case frame has two main components, patterns for recognizing aninvocation of the frame in the input and a number of cases that are semantically related to14the concept the case frame represents. The case frame represents some relation betweenthings and the cases represent what is related.Semantic and syntactic constraints are associated with each case of the case frames.Semantic constraints typically are based upon the role that the case has in the relation thatthe case frame represents. There have been numerous attempts to define a complete set ofroles. Such a definition is called a case system. Figure 2.2 contains some sample casesfrom FILLMORE71.Agent The instigator of the eventObject The entity that moves or whose position or existenceis in considerationInstrument The stimulus or immediate physical cause of an eventFigure 2.2 - Sample CasesIn addition to the semantic information about roles, the case frame contains informationused to recognize cases in the input. Case markers are associated with each case. Duringanalysis of the input, case markers are used to identify case fillers. Case fillers are thesentence components that fill the role of a case. Markers are simple constraints on theposition of the case in the input or they are patterns which precede the case filler. Patternsusually recognize prepositions.Figure 2.3 contains a case frame for the verb "fix". As mentioned earlier, associated witheach case frame there is a pattern that is used to recognize an occurrence of the case frame.For this case frame, an occurrence of "fix" (or any variation of it) in a sentence wouldindicate that this case frame should be used to interpret the sentence. This case frame hasthree cases, the agent, theinstrument and the object. Eachof these cases is associated witha pattern (called case marker)for recognizing an occurrenceof the case, and semantic15FixCase Marker DescriptionAGENT Logical Subject • a personINSTRUMENT with • a toolOBJECT Logical Object • inanimateFigure 2.3 - Case Frame For Fixconstraints. The first case is the agent case. The agent appears as the syntactic subject ofnon-passive sentence or the filler of a case marked with 'by' for passive sentences. In otherwords, this case is marked by position for non-passive sentences or with the preposition'by' for passive sentences. There is a semantic constraint that the filler of the case be aperson and so only noun phrases that refer to people could fill this case. The second case isthe instrument. The instrument case represents the tools used to perform the act of fixing.This case is marked by the preposition "with". That means that the case filler must be partof a prepositional phrase beginning with the word "with". The semantic constraint on thefiller is that it must be a tool. Semantic constraints depend on the application and havebeen arbitrarily chosen for this example. The last case is the object case. The object case ismarked by position. The filler appears as a syntactic object for non-passive sentence or asthe syntactic subject for passive sentences. The semantic constraint on the object is that itmust be inanimate. As seen in this example, case frames provide both syntactic andsemantic information which can be used to analyze sentences.Consider the non-passive sentence in Figure 2.4. In the sentence, the verb "fixed" is amarker of the case frame in Figure 2.3. Once this is realized, the system can use the case16frame to analyze the sentence. According to the case frame, "Jack" is taken to be the agentbecause of position. The sentence is not inJack fixed the bench with a hammer.passive form so the agent appears as thesyntactic subject. The semantic information in^Figure 2.4 - Non-passive Sentencethe case frame can be used to confirm this choice. "Jack" refers to a person. Because thesentence is not passive, the object case which appears as the syntactic object is filled by"the bench" which is inanimateThe bench was fixed by Jack with a hammer.according to the semantic constraintsFigure 2.5 - Passive Sentencefor the object case. The instrument caseis filled by "the hammer" which is marked by the preposition "with" according to the caseframe. For the passive form of sentence shown in Figure 2.5, the syntactic subject is notthe agent case but instead it is the object case. The agent case filler is to be found markedwith the preposition 'by'. This transposition occurs because the sentence is in passive form.As shown, the parser can apply both syntactic and semantic constraints by using caseframes.In addition to constraints on each individual case, there are constraints on the cases as awhole. Constraints may require that certain cases always be present, that some cases cannotoccur together or that some cases must occur together. There is no constraint that caseframes can only represent verb relations. Case frames can be used to represent noun phraselevel structures.Case frames are accessed during the parsing process to obtain syntactic and semantic17constraints. ATNs have been used to parse sentences in many case frame-based naturallanguage interfaces (TAYROS75, WHITE85, BOOTH83). The additional semanticconstraints brought to bear early on in the analysis were able to alleviate some problemsnormally associated with ATN parsing. The problem of grammatical errors still remains.Other approaches to parsing using case frames have attempted to deal with these problems(Hayes & Carbonnell - CARHAY83).Case frames are able to effectively combine syntactic and semantic information. By usingsemantic information during the parsing process, case frame systems are able to reduceambiguity and the parsing time but unlike semantic grammar systems the grammar remainscompact and easy to understand. Case frames are also able to handle different forms ofexpression without requiring the extensive coding that semantic grammars require.2.2 Desirable CharacteristicsDuring the development of natural language interfaces, many design issues came to light.These issues involve how easy the interface is to use and how easily it can be transferredto other systems. This section examines some of these issues with respect to the systemsdescribed earlier.2.2.1 Internal CharacteristicsIf natural language interfaces are to have widespread use, they must not only be easy to use18but they must possess characteristics which facilitate application to different problem areas.Many systems although easy to use, did not become popular because they were not easilytransferred. This section covers the different ways that a system can be easy to transfer aswell as some characteristics that increase the ease with which a system can be transferred.2.2.1.1 PortabilityPortability of a natural language interface is the ease with which it can be reused. There aretwo aspects of portability, domain portability and database portability - actually databasemanagement system (DBMS) portability. Domain portability is the ease with which theinterface can be used with a different database, i.e. - a different domain of discourse.Database portability is the ease with which the interface can be used with a differentdatabase management system (for example, transferring from a relational DBMS to anetwork DBMS).The systems described earlier had portability of varying degrees. LUNAR attainedportability by separating syntactic from semantic analysis. The syntactic analysiscomponent of LUNAR increased portability by using a single grammar for every domain.The reference to the domain as well as the DBMS was contained in the proceduralsemantics of the systems and in the lexicon. As a consequence, the semantic componentand the lexicon were neither domain independent nor database independent and had to berewritten after a change of either. LUNAR had portability of only the part of the syntacticcomponent that contained the grammar. In contrast to LUNAR, semantic grammar systems19were in no significant aspect portable. By combining syntactic and semantic informationinto the grammar in order to increase parsing efficiency, semantic grammars sacrificedportability. Changing the domain required the grammar to be reconstructed from scratchusing semantic concepts of the new domain.One technique for increasing domain portability is to use an inverted index' of words inthe database. This approach was used successfully by Harris in ROBOT' (HARRIS77,HARRIS84). Although still based upon the linear paradigm - syntactic parsing using anATN followed by semantic analysis, Harris was able to make use of information in thedatabase to such a degree that he reported that systems could be ported from one domain toanother by a DBA in a week to two weeks.A technique for increasing database portability is to use an intermediate representationlanguage, IRL, PG87. For systems using IRLs, the result of parsing and interpreting aninput is a sentence in the IRL which can later be converted to a database query. The IRL isan interface between the database management system and the natural language interface.Having a clearly defined interface means that transferring the system from one DBMS toanother requires only rewriting of the component that translates IRL to the query language.Another advantage as shown in the Natural Language Corporation's NLI, is that the systemmay use the meaning in the IRL sentence to do things other than access a database.- see section 4.1.3.1- Later INTELLECT20Closely associated with the portability of a system is the ease with which it can bemaintained. During the life of a database not only will changes to the database occur butnew users with varying expectations will use the system. It is important that the cost ofmaintaining the system not be too great otherwise it will not be maintained and then,eventually, not used as it fails to keep up with changes to the database.2.2.1.2 Semantic ProductivityIn order to interpret utterances, natural language interfaces must contain syntactic andsemantic knowledge in declarative or procedural form. This knowledge determines theutterances that the system can interpret - its coverage. Coverage can be too broad so thatincorrect interpretations are made or too narrow so that intelligible inputs will not beinterpreted. The knowledge base must be large enough to provide acceptable coverage.Semantic (or syntactic) productivity is a qualitative measure of how effective a formalismis in producing acceptable coverage.Semantic productivity relates how implicit the knowledge of language is represented in thesystem. The least productive systems list every allowable utterance and its interpretation.Semantic grammars are at the low end of the productivity scale because they must containrules for the different forms of expression for each group of semantic categories. Caseframe based systems are more productive because the case frames provide a compact formfor representing information and yet still allow many forms of expressions to be parsed.High productivity is closely related to high portability.212.2.1.3 Minimum CoverageThe systems described earlier attained broad coverage of language by increasing theamount of grammatical knowledge they contained. The goal was to be able to parse asmany of the inputs as possible. The systems contained a single grammar for use with manydifferent users who had many different styles of English. As observed in LEHMAN, if thesystems instead had different grammars for each user then they would not have to handlesuch a large variety of forms of expression because each user's statements tend to have acertain fixed style. Minimizing coverage is the problem of trying to make sure that theparser will not accept more forms of expression than the current user will offer.Benefits can be achieved by minimizing coverage. Sentences that were ambiguous relativeto the grammars set up to handle all user's utterances, will not be ambiguous relative to agrammar set up for a particular user. By reducing the number of acceptable sentences, theparsing process becomes faster. It is demonstrated in LEHMAN that using a singlegrammar for all users is not as efficient as having a separate grammar for each user,because each user has to pay for other users' different forms of expression. Minimizingcoverage is a difficult problem because it requires that the grammar be customized for eachuser.2 12.2.2 User InterfaceThe standards used to judge a natural language user interfaces are based upon theexpectations of the users. Much work has been devoted not only to developing naturallanguage interfaces that satisfy user expectations but also to determining what the userexpectations are. Meeting user expectations is important to ensure that the interfacebecomes a valuable tool and not a source of frustration. This section attempts to provide asummary of the characteristics that users expect a natural language interface to have.2.2.2.1 Habitable (User-friendly)A system is habitable if it can correctly interpret many different utterances that express thesame idea. Habitable systems seem consistent to the user. Systems that are not require thatthe user search for an acceptable form of expression. With nothing to guide the user, thissearch can involve several tries and lead to frustration. Systems that are not habitable forceusers to learn what is acceptable and what is not acceptable. As a consequence the usersmust use restricted forms of English, if they want to use the system.Pattern matching and semantic grammar based systems are more likely to not be habitablebecause general syntactic rules must be incorporated in each pattern or semantic grammarrule. Syntactic parsers have been able to achieve broad coverage. This is demonstrated bythe commercial system of Harris, INTELLECT. He reports that one of the primary issuesthat had to be dealt with to satisfy commercial expectations, was coverage of the grammar23(HARRIS84). Prototype versions without broad coverage were thought to be inconsistentand annoying and were not commercially acceptable. INTELLECT did not find broadacceptance until habitability was dealt with.Making a system more habitable requires that the coverage of the system be increased tohandle more forms of expression. This can lead to problems because the coverage is notminimized. There is a compromise between habitability and minimizing the coverage.2.2.2.2 CooperativeHuman communication is a complex form of interaction which is not only performed usinglanguage. In contrast to this, many natural language interfaces constrain interaction with theuser to be questions followed by direct answers from the system. Much work has beendone to try to increase the sophistication of natural language interfaces. Cooperative userinterfaces provide more sophisticated dialogues in an attempt to work with the user and notjust respond to the user's explicit requests. Many features have been developed to provide acooperative system. This section describes a few.A system that provides cooperative responses to questions does not necessarily answer aliteral interpretation of the question. There is an attempt to anticipate follow-up questions,to respond before being explicitly requested, and to provide more information than wasrequested. Anticipating can involve simple pattern matching or complex modelling of theuser's intentions and plans.24One problem to deal with is responding to questions with a negative answer(RENDEZVOUS, COOP - KAPLAN84). The questionWhich of Dr. Lee's students is enroled in cs503?could be answered "none", but there may be many different reasons that there are none.There might be no Dr. Lee and so there are no students of Dr. Lee. There might be a Dr.Lee but he may have no students. There might not be a class called cs503 and so therecould be no students enroled in it. Finally, Dr. Lee may have students and there may be aclass called cs503 but none of the students are enroled in it. The response "none" isambiguous and would probably be misinterpreted by the user. The problem of analyzing thefailure to find any students can be handled by removing part of the query and reissuing it(ALLEN87). Analyzing the cause for the failure involves determining whichpresuppositions of the question are wrong.By not treating questions literally, the system can also become more cooperative. Questionssuch as "Can you list employees working in research" could be answered by listing theemployees instead of by confirming that the system was capable of listing them. Sometimesyes/no questions require more than just a yes or no answer.In this case the products must be sold at a Can I sell an ace tennis net for 69 dollars?No, the lowest price allowed is 72 dollars.price in a particular range. "No" answers thequestion literally but is not satisfactory because the system in not working with the user tosolve the problem. These examples show it is important to provide a reason for a "no"25response.Ambiguity is the reason for many of the problems that a natural language interface mustdeal with. In the previous section, the concern was to avoid ambiguity in the responses.Ambiguous responses can cause the user to develop misunderstandings. This sectionconcerns how the system can deal with input that is ambiguous. This process involvesdetecting the ambiguity and interacting with the user to resolve it.Ambiguity can arise when there is more than one choice for the interpretation of a word orphrase. In ROBOT such a problem occurs for:Who lives in New York?Does "New York" refer to New York state or New York city? Harris solves this problemby printing paraphrases of the interpretations and asking the user to select one. This isconfirmation by paraphrase. The other approach to resolving the ambiguous reference isconfirmation by effect.The CHAMP system of LEHMAN89 is an adaptive user interface that is capable oflearning the syntax as well as the meaning of statements. For CHAMP's confirmation byeffect, when there is more than one interpretation of an input, the system will analyze theconsequences of each alternative and ask the user to select an interpretation by presentingthe potential consequences of each input. This means that the contents of the database canaffect the selection of the intended meaning of an utterance. Confirmation by effect can26also be used to eliminate alternatives before even asking for a selection by the user. For thesentenceWhich of the New York employees live in Buffalo?ROBOT is able to determine whether "New York" refers to New York city or to New Yorkstate by issuing the queries corresponding to both interpretations. For the interpretationwhere "New York" is taken to be a city there is no result. ROBOT decides without askingthe user that "New York" must refer to the state because that produces a result.When using paraphrase to resolve ambiguity it is important to avoid providing informationthat is not needed to make a decision. For the ROBOT system, the request in Figure 2.6 isambiguous.What is the family status of the area managers that live in New York?Does "NewFigure 2.6 - Ambiguous QuestionYork" refer tothe state or the city? ROBOT characterizes the two choices with the paraphrases shown inFigure 2.7.Choke 1:PRINT THE FAMILY STATUS, STATE AND CITY OF ANY EMPLOYEE WITH STATE=NY AND JOB=AREA MANAGERChoke 2:PRINT THE FAMILY STATUS, STATE, AND CITY OF ANY EMPLOYEE WITH CITY=NEW YORK AND JOB=AREAMANAGERFigure 2.7 - Paraphrases27More information is provided than is needed to make thedecision. A simple approach would be to provide enoughinformation to distinguish the alternatives as shown inFigure 2.8. Choice 1:CITY = NEW YORKChoice 2:STATE = NYFigure 2.8 - Simple Choices2.2.2.3 Robust with Respect to "Noise"Inevitably, a natural language interface will be forced to deal with inputs that contain errorsor unforeseen forms of expressions. Spelling errors, unknown words, missing words, extrawords, ellipsis and strange phrase orderings are all part of this problem. Simply rejectingthe input without explanation or alternatives is not acceptable. Systems that cannot dealwith simple forms of these problems will be seen as inflexible.Spelling errors can be dealt with by searching for close matches in a list of words.Semantic grammar and case frame grammar systems are able to offer good spellingchecking because the semantic information can be Used to reduce the size of the word listthat must be checked. This reduction is possible because the semantic information isavailable during the parsing process to constrain the search.What is the length of the Constellation> (LENGTH 1072 feet)of the Nautilus> (LENGTH 319 feet)displacement> (STANDARD-DISPLACEMENT 4040 tons)length of the fastest American Nuclear sub> (LENGTH 360 feet NAME LOS ANGELES SPEED 30.0 knots)Figure 2.9 - Ellipses282.2.2.4 Handling of Discourse PhenomenaAnother important issue for natural language interfaces is managing the dialogue with theuser. The scope of the interface must exceed the individual sentence if the system is to beable to respond to the shortcuts people take when communicating. Anaphora is commonduring conversations. Anaphora is the use of reduced linguistic forms such as pronouns (he,they, it), demonstratives (that, this) or definite noun phrases for purposes of reference.People also employ ellipsis, or sentence fragments, to ease communication. This sectionbriefly describes some dialogue phenomena.2.2.2.4.1 EllipsisThrough the use of semantic information gained during the processing of previoussentences, case frame and semantic grammars are able to effectively deal with ellipsis. TheexampleinFigure 2.9is takenfromLIFER.LIFER is able to determine the correct interpretations by partially parsing the inputs todetermine what type of phrases they are and then looking for phrases of the same type inthe originating sentence. A substitution of the new phrase for the old is used to produce anWho manages Smith?> FordWhat is the manager's salary?> 3100Who else makes at least that much?> Jones and King.What do they make?> Jones makes 3100 and King makes 5000.Figure 2.10 - Anaphora29interpretation. The use of semantic information during parsing makes this approach feasible.Syntactic constraints are often not enough to correctly interpret ellipsis. Case framegrammars can also effectively deal with this type of ellipsis because of the availability ofsemantic information during the parsing process.2.2.2.4.2 AnaphoraHandling anaphora is as important as dealing with ellipsis, and as difficult a problem.There are many differentforms of anaphora. Thedialogue of Figure 2.10illustrates a few of theseproblems. Pronouns can beused to reference thingsmentioned not only in the previous sentence but in the current sentence or in sentencesbefore the previous one. As described in ALLEN87 (pp 334-365), the history list is aneffective technique for solving this problem.The history list is a list of objects mentioned in previous sentences in reverse chronologicalorder. Semantic information can be associated with the objects. Upon encountering ananaphoric reference the history list can be searched for objects with compatible semanticinformation. Additional constraints can be derived from syntactic information as describedin HOBBS78.302.2.2.4.3 VaguenessIn KAPLAN84 vague statements are portrayed as a means employed by the user to reducethe size of statements as well as to provide the responder with fewer restrictions on whatthe response should be. The utterer of the statement expects that the user can makereasonable inferences and so a cooperative system must be able to respond to vagueness.Vagueness and ambiguity are similar in that the correct interpretation cannot beobtained from a literal reading. They are different because ambiguity arises when there ismore than one interpretation immediately available and vagueness arises when the systemmust fill in unstated connections. Vagueness does not imply ambiguity.Dealing with vagueness involves making inferences about additional unstated constraints.These constraints can be related to how the query is to be interpreted as well as to whatresponse the userQ: What is the quantity-on-hand of each size of radial tire?expects. The^R: 125, 0, 500, 32, 40following example Figure 2.11 - Vagueness(Figure 2.11) from KAPLAN84 illustrates how literal interpretations of vague questions isnot satisfactory. A better response would include the sizes of the tires as well as theinformation that was explicitly asked for.312.3 Learning LanguageThis section briefly describes how learning has been used by natural language systems toobtain information necessary to improve performance. Natural language systems canenhance their performance by learning a combination of syntax and semantics as well aslexical information. Problems that any learning system must deal with are inputs thatcontain errors and so should not be learned, learning with the fewest number of examples,being able to correct previous misunderstandings, and producing similar results if examplesare ordered differently. The systems described here solve these problems with varyingdegrees of success.2.3.1 SyntaxBERWICK85 is an example of a system which attempts to learn syntactic information only.The goal of this system was to explore how children can learn language. It is based on theMarcus parser [MARCUS80] and X-bar theory of grammars. The system learns X-bargrammar rules and transformation rules by being presented with a number of grammaticalsentences. Learning arises from each input and the results of analysis immediately modifythe existing grammar.This system has a number of problems, some of which are due to the lack of semanticinformation. Words must have feature markers (+noun for example) in order for the systemto learn properly. This information is not likely to be available to a child. The ordering of32input sentence also affects learning. If a question such as "Is Fred a postman" is presentedfirst, the system would incorrectly learn that verbs come first in sentences. The system alsohas no way of correcting structures that were learned but should not have been, such as theprevious example. The main advantage of the system is that it will learn quickly. Thissystem illustrates that there is a trade off between learning quickly and learning onlycorrect forms. If a system is learns too quickly then there must be some mechanism tocorrect mistakes. Without such a mechanism, the system will not perform effectively.2.3.2 Semantics23.2.1 CHAMPLEHMAN89 presents a technique for developing a natural language interface that can learnsyntax and simple semantics of utterances related to a table of data - an adaptive interface.Lehman identifies three types of user interfaces, adaptable, customizable and instructible.The difference lies in the method used to provide domain dependent information about thesyntax and semantics of the grammar and lexicon. Customizable user interfaces asrepresented by INTELLECT (HARRIS84) and TEAM (MAP83) are configured by anexpert using a special facility. Instructible user interfaces such as ASK, (THOMP85),require that the user provide customization using a simple command language. Anadaptable user interface reconfigures itself during interaction with the user. No specialcommand language is required. The system presented in this thesis is an example of anadaptive user interface which doesn't learn syntax but focuses on learning semantics.33There are many advantages of adaptable user interfaces. The reasons for these advantagescan be seen after exploring characteristics of users of the systems. These observations arederived from empirical research presented in (LEHMAN89). Users can be knowledgable incommand languages and database structure, or they can be relatively naive in terms ofdatabase management system technology. The former is a sophisticated user and the latter anaive one. These observations concern the naive users who would most benefit from naturallanguage interfaces. The main observation is that users tended to limit not only the wordsbut also the structure of their utterances. Forms of expression that are not ambiguous to agrammar customized to the user are ambiguous to a grammar common to all users. Theseobservations lead to several reasons for preferring adaptive interfaces.Most natural language interfaces have a single grammar that is to be used by everyone.Relative to a single user, this parser would be able to analyze sentences that the user isnever going to utter. Thus parse time is spent trying to interpret utterances in a way thatthe user would never employ. Users have idiosyncratic forms of expression. Extending theparser to be able to handle each user's forms would result in a parser that ran too slowly.The parser would also see ambiguity where relative to an individual user's form ofexpression there is no ambiguity. The final problem with extending the parser is that everyuser would have to pay for the extra parse time needed to handle some users' strange formsof expression. Having an adaptive interface which is customized to each user eliminatesthese problems and provides a system that is more effective for each user.CHAMP is the system that is used by Lehman to implement an adaptive parser. CHAMP isFigure 2.12 - Part of a Concept Hierarchy34a bottom up parser that selects the least deviant parse to learn from. Deviation is measuredfrom the current grammar of the system in terms of the number of insertions, deletions,substitutions, or transpositions that must be performed to the utterance to allow it to berecognized by the current grammar. Recognizing an utterance results in a database actionrecord. The database action record has four allowable functions, to add, delete, modify orprint a row in a table of the database. The database action record approach is a form ofprocedural semantics.CHAMP uses a combinationsemantic and case framegrammar. The grammarcontains constituents torecognize expressions referringto time intervals, meetings andplaces, etc. These are domaindependent structures which thesystem updates as it learns. Tosupport recognition CHAMPmaintains a concept hierarchy.The concept hierarchy provides information that can be used to simplify the grammar andfacilitate interpretation. The concept hierarchy is specified by an expert before system use.Figure 2.12 depicts part of a concept hierarchy. The boxes represent concepts and thearrows represent isa links.35In addition to the isa links each node of the concept hierarchy contains information that canbe used to provide default values and constraints. In the sentence of Figure 2.13, the timeor the place that the people will eat at is notSchedule a lunch with John on June 4.specified. The concept hierarchy can be usedFigure 2.13to obtain additional information. In this casethe time is derived from the lunch concept and the place is derived from the meal concept.The lexicon contains many domain dependent components as well. The words that are inthe database appear in the lexicon and are put there manually. There are words that refer toconcepts in the concept hierarchy such as arrival, meeting, and dinner in the lexicon. Thedefinitions for these words identify them as marking slots in the frames or as referring to aconcept in the concept hierarchy.The end result of the parse is a database action record. The only actions allowed are to add,delete, modify or show a row in the database table. The system is not capable ofperforming any other action to the database nor can an utterance refer to more that onetable at a time. The system never learns new meanings to sentences only new ways ofreferring to one of these actions or to one of the objects in the database. The new ways ofreferring can be synonyms of known words or new orderings of component phrases.Several other researchers have developed systems to investigate how children learnlanguage or how effective a particular approach is in learning language. CHAMP is theonly such system which actually interfaces with a database. A comprehensive review of36these other systems can be found in LEHMAN89.2.3.2.2 TEAMTEAM is an example of a customizable user interface. For this approach, a databaseadministrator (DBA) interacts with a menu driver interface in order to provide domaindependent information. This section briefly describes how the system gathers information.TEAM learns by asking a DBA, structured questions. The actual learning process of TEAMis not as interesting as what the system is learning, however. TEAM contains domainindependent knowledge of certain concepts such as numbers, features, and measurements.This information is stored in a hierarchy of objects called the sort hierarchy. The userextends this hierarchy through the process of adding new concepts to the knowledge base.Associated with each type of concept are a number of items. For an arithmetic field theinformation shown in Figure 2.14 is obtained.Value Type - DATES MEASURES COUNTSAre the units implicit? YES NOEnter implicit unit - DOLLARAbbreviation for this unit?Measure type of this unit -TIME WEIGHT SPEED VOLUME LINEAR AREA WORTH OTHERMinimum and Maximum numeric values - 0. 100000.Positive adjectives - (HIGH PAID)Negative adjectives - (LOW PAID)Figure 2.14 - Arithmetic Field Acquisition (MAP83)The main disadvantage of TEAM is the process that is used to derive domain dependent37knowledge. The DBA must first determine which words the users will want to use. Thenthe definition must be standardized. Standardization involves compromise and compromiseimplies settling for less than was wanted. After that, the words must be entered into thesystem along with additional information. Of course the users want new words added later.This means the DBA must start the process all over again. A better approach would allowusers to independently configure the NLI on their own time.2.4 SummaryMany different approaches to providing natural language interfaces have been proposed.The more recent case frame-based approach which provides a means to combine syntacticand semantic information seems to be the most promising. During the course ofdevelopment of natural language interfaces, a number of design principles were developed.One of the most important was portability, i.e. - the ease with which the natural languageinterface can be transferred to a new domain of discourse. Portability issues play a majorrole in this thesis. A number of researchers have investigated the advantages of usinglearning to enhance system performance. Recently a learning approach to configuring anatural language interface has been developed and experimentally evaluated. This thesispresents another aspect of the use of learning to enhance natural language interfaces. Herelearning is used as a means of increasing portability of a natural language interface.Chapter 3System Overview3.1 ObjectivesThe goal of this system is to make it easier to transfer a natural language interface fromone domain to another. This has been a goal (not the only one) of a number of othersystems such as COOP (KAPLAN84), and TEAM (MAP83). For early natural languagesystems, an expert in setting up grammars and in databases was needed to transfer a systemfrom one domain to another. Later work resulted in systems that could be transferred by adatabase expert. This thesis advances portability by providing a means that allow naiveusers to set up a natural language interface. In this case, a naive user is a user who doesnot necessarily have knowledge of the database structure or formal query languages.3.2 Knowledge Base Components38This section briefly describes the components used to represent knowledge and where theyare derived from.MorpherEl Domain IndependentEi Domain DependentKnowledge TransferLexical Knowledge(7)Lexicon(inverseIndex)(8)DatabaseGrammatical KnowledgeSemantic KnowledgeFrameKnowledgeFunctionWords(9)UserDictionaries(4)Grammar393.2.1 Domain Independent KnowledgeFigure 3.1 - Knowledge Source Diagram40Domain independent knowledge is knowledge that remains fixed during program execution.For this system, domain independent knowledge includes part of the lexicon, the grammarand part of the semantic knowledge. These are represented in Figure 3.1 by the boxes withthicker outlines (knowledge stores (3), (4), (5), and (6)). The domain independent part ofthe lexicon (knowledge store (5)) includes prepositions, auxiliary verbs, articles, andfunction words (average, total). The entire grammar (knowledge store (4)) and the morpher(knowledge store (6)) are domain independent. The grammar developed for the systempresented in this thesis is listed in DCG form in appendix B. Some of the knowledge usedto interpret sentences is also domain independent. This includes information on how toconvert questions, queries involving function such as "average", and queries involvingcomparisons such as "more than", into SQL (knowledge store (3)).3.2.2 Domain Dependent KnowledgeDomain dependent knowledge is knowledge that depends on the particular database beingused. In order to function properly with a new database, domain dependent knowledge forthat database must be given to the system. For this system, parts of the lexicon and thesemantic knowledge are domain dependent. These are marked in Figure 3.1 by boxes withoutlines of lesser thickness (knowledge stores (1), (2) and (7)). There are two different typeof words added to the lexicon (knowledge store (7)), words or phrases that are databaseelements and words referring to knowledge structures that the system constructs such ascase frames or slots in case frames. The words that are database elements are derived41directly from the database prior to program execution. This is depicted as a transfer ofknowledge (represented by the arrow) from the database (knowledge store (8)) to thelexicon (knowledge store (7)). Words that refer to case frames or case frame slots areadded to the lexicon as the system learns them during interaction with the user. This isdepicted in Figure 3.1 as a transfer from the user (knowledge store (9)) and the database(knowledge store (8)) to the lexicon (knowledge store (7)) and the dictionaries (knowledgestore (1)).The semantic information that the system learns mainly concerns the frame knowledge(knowledge store (2)). There are two type of frames in this system, case frames for verbsand object frames for objects. An object frame is used to keep information about casefillers. Object frames keep track of object names, and attributes. Case frames keep track ofevent dates, and cases for the verbs. Associated with the frame information is a number ofdictionaries (knowledge store (1)) that map various words and types to frames. These arealso maintained by the system and are part of the domain dependent information. Asdepicted in Figure 3.1, the frame knowledge (knowledge store (2)) and the dictionaries(knowledge store (1)) are derived from both the user (knowledge store (9)) and thedatabase (knowledge store (8)).3.3 Processing Flow of ControlThis section describes the flow of control through the system which is depicted inFigure 3.2. The processing starts with reading a sentence which is then tokenized, parsed42and then interpreted. After interpretation, the system either updates its knowledge base for adeclarative statement or generates SQL and prints the results for a question. The followingsection describe each step in more detail.SemanticInterpreter(vii)LexiconinInverseIndex0 ProcessData StoreData Flow(vil.1) Updates(g.2) LookUps(g.1) Database ValuesLexiconServer(f.2) Tokensand Meanings(83) Utterance \(d)QueryGeneratorLearnMeaningOracleInterfaceResponseGenerator-,c.2) Frames(b.4) Productions(a.2) Token and possible Meanings(t.3) Utterancetz(c.1) ^0.2)Phrases^NodesModifier (d.1) terPrtilatk(b)^Attachments^(c)(1.1) Response to SQL(e.1) Response to Query(e)(b.1)AllTokenizations c3) Type Defs4!)Dictionaries (I)CaseFramesObjectFrames(LI) Asking User for Decisions(4.1) Utterance(1.2) Query Results(e.2)SentenceInterpretation(v)Database(vi)DataDictionary43Figure 3.2 - Data Flow Diagram443.3.1 TokenizingTokenization occurs at process (a) of Figure 3.2 where the utterance (flow (a.1)) arrivesfrom the user (process (i)). The tokenizer (process (a)) passes the utterance (flow (f.3)) tothe ORACLE interface (process (0) which in turn passes the utterance to the lexicon server(process (g)) along flow (g.3). The lexicon server uses the inverted index (data store (vii))to break the utterance up into tokens (words or phrases). Associated with each token ispossible meanings which may indicate that the token is in a fixed word class (preposition,article, etc), that the token refers to a case frame or a slot in a case frame, or that the tokenappears in the database. There may be more than one way to break the sentence intotokens. After the lexicon server (process (g)) determines all tokenizations, the results arepassed back to the tokenizer (process (a)) along flows (f.2) and (a.2) through the ORACLEinterface (process (0).3.3.2 ParsingThe parser (process (b)) receives the tokenizations from the tokenizer (process (a)) alongflow (b.1). The parser then uses the grammatical information obtained from the grammar(data store (iv)) along data flow (b.4), to analyze the sentence. The grammar is in the formof a definite clause grammar (DCG) as described in PERWARR80. In order to avoidproducing non-sense parses, the parser accesses semantic information. The informationfrom the dictionaries (data store (iii)) is used to determine which case frames are associatedwith which words. The case frames (data store (i) and (ii)) are accessed along data flow45(b.3) to help resolve^Who earns over the average salary of a person working in research.attachments of cases Figure 3.3 - Case Attachmentto verbs. For thesentence of Figure 3.3, this information is used to help determine whether "in research" is acase of "working" or of "earns".3.3.3 InterpretationThe semantic interpreter (process c) receives the partial parses of the utterance from theparser (process b) along data flow c.l. Each parse contains information about noun phrasesand verb phrases mentioned and constraints on modifier attachments. The semanticinterpreter (process c) accesses the dictionaries (data store iii) along dataflow c.3, and theframes (data stores i and ii) along data flow c.2. This information is used to produce aninterpretation of the utterance. During this process, the system will detect that some of theparses are unintelligible and discard them. At this point there are two major alternatives forthe processing flow of control depending on whether the sentence is declarative orinterrogative.33.3.1 Declarative SentenceThis part of the processing is described in detail in chapter 5. Declarative sentences areused to define new concepts. The 'learn meaning' process (process (j)) is invoked after thesemantic interpreter (process (c)), if the utterance is declarative. The 'learn meaning'46process (process (j)) receives the interpretation from the semantic interpreter (process (c))along data flow (j.1). At this point, interaction occurs with the user to determine a correctinterpretation for the meaning of the concept that the user is describing in the sentence.Interaction occurs with the user (process (i)) along data flows (i.1) and (j.3). During theprocess of interacting with the user, the database and the inverted index are accessed alongdata flows (f.4) and (j.2). This interaction occurs as long as the user has not helped todetermine a meaning for the utterance. At some point, if the user is satisfied with theinterpretation, the system updates the dictionaries (data store (iii)) along data flow (iii.1)and the frames (data store (i) and (ii)) along data flow (i.1) and (ii.1). Processing of theutterance is now complete.3.3.3.2 QuestionsThis part of the processing is described in detail in chapter 6. This processing stream isinvoked after the semantic interpreter (process (c)) if the utterance is a questions. Thequery generator (process (d)) receives the sentence interpretation from the semanticinterpreter (process (c)) along data flow (d.1). The interpretation is converted into an SQLquery which is passed to the ORACLE interface (process (0) along data flow (f.3). TheORACLE interface (process (0) then passes the SQL query to the DBMS (process (h)) forprocessing along data flow (h.1). The results of the SQL query are returned from theDBMS (process (h)) along data flow (f.1) to the ORACLE interface (process (0) whichpasses them on to the response generator (process (e)) along data flow (e.1). The responsegenerator (process (e)) also receives the sentence interpretation from the query generator47(process (d)) along data flow (e.2). The response generator presents the results to the user(process (i)) along data flow (i.2). The response generator for. this system merely prints outthe data returned by the DBMS rather than producing a more elaborate display. This endthe processing of the utterance.3.4 Implementation DetailsThis system currently accesses the ORACLE RDBMS only. Because the systems is writtenmainly in Prolog and ORACLE does not support access with Prolog, a C server was set upto access ORACLE (process (f) of Figure 3.2). The C server makes use of ORACLE'sPRO*C compiler that contains extensions for accessing the database. The lexicon server(process (g)) (an inverted index - see section 4.1.3.1) was set up in C++ as a separateprocess accessed only through the ORACLE interface (process (f)). The reason for aseparate process was that the C++ compiler used BSD Unix and the ORACLE PRO*Clibraries required UNIX System V libraries and so could not be compiled together. Due tolicensing agreements the Prolog interpreter ran on one platform and the Oracle server ranon another so communication between the Prolog process and the C server occurred thougha TCP package in Prolog and with TCP in C.3.5 ExamplesWhat follows is a brief example of how the system works. A more complete session can be48found in appendix E. For this system, the user is a person who has little or no knowledgeof DBMS. This means little or no knowledge of relational database theory, formal querylanguages and the structure of the database that he or she will be using. It is assumed thatthe user knows about the data in the database. For example, if the database was anemployee database the user must know about some particular employees (perhapsthemselves). For a movie database, the user must know about some particular movies. Whatthe user lacks in knowledge can be obtained from more traditional sources such as reports,data collection forms, or other people.smith works for ford. To configure the system for a newdatabase, the user (in bold) enterssentences that describe data in thedatabase. By using these sentences andaccessing the database the system candetermine the meaning of nouns and verbs.(Users tend to know a lot about some ofthe data in the database).EMPO.ENAME EMPLENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seemreasonable?: yes.49: smith works in research.EMPO.ENAME DEPTO.DNAME Examples are presented to provide feedbackCLARK^ACCOUNTINGKING ACCOUNTINGMILLER^ACCOUNTINGSMITH RESEARCHDo these examples seem reasonable?: yes.I : smith is managed by ford.EMPO.ENAME EMPLENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seem reasonable?: yes.: smith's salary is 800.EMPO.ENAME EMPO.SALALLEN^1600JONES 2975SMITH^800WARD 1250Do these examples seem reasonable?I : yes.: the manager of smith is ford.EMPO.ENAME EMPl.ENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seem reasonable?: yes.: the salary of smith is 800.EMPO.ENAME EMPO.SAL50ALLENJONESSMITHWARD160029758001250Do these examples seem: yes.: smith earns 800.EMPO.ENAME EMPO.SALALLEN^1600JONES 2975SMITH^800WARD 1250Do these examples seemreasonable?I : yes.I : what is smith's salary.EMPO.SALreasonable?That's it. System configuration iscomplete (for now). Questions can nowbe asked about the database. Note thatquestions can be asked as soon as theuser has defined the words that willappear in the question. After asking somequestions, more words can be defined ifdesired.First an easy question to get warmed u800I : which person's manager's salary is 2975.EMPl.ENAME SCOTTFORD: which person's salary is over ford's salary.Possessives and comparison.EMPl.ENAMEKING 51I : who earns over an employee's average salary.Functions such as average, total,highest, and lowest are provided.EMPO.ENAMEJONESBLAKECLARKSCOTTKINGFORDI : who earns over an employee working in research's average salary.EMPO.ENAMEJONESBLAKECLARKSCOTTKINGFORD: what is the lowest salary of the people who earn over the average salary of anemployee.MIN(EMPO.SAL)2450I : how many people earn over the average salary of an employee.COUNT(EMPO.ENAME)6can you list the name manager and salary of the employees working in research.EMPO.ENAME EMPO.SAL EMPLENAMESCOTT^3000^JONESFORD 3000 JONESSMITH^800^FORDJONES 2975 KINGADAMS^1100^SCOTT 52: tkb sport shop paid 58 for ace tennis net.Let's teach the system a wordwith a complicated meaning.This one has ambiguity andrequires 4 table joins. Theuser is presented with achoice of two meanings.2 Interpretations. They Are:Option #1"58" refers to ACTUALPRICE in theITEM tableOption #2"58" refers to ITEMTOT in theITEM tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definition: can you show me some more options.[moreOptions]3 Interpretations (1 are new).They Are:Option #1"58" refers toACTUALPRICE in the ITEM tableOption #2"58" refers to ITEMTOT inthe ITEM tableOption #3 (New)"58" refers to STDPRICE in the PRICE tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definitionI: more.[moreOptions]There are no more alternativeinterpretations.All alternatives have been listed.3Interpretations. They Are:Option #1"58" refers to ACTUALPRICE in theITEM tableOption #2"58" refers to ITEMTOT in the ITEM tableOption #3"58" refers to STDPRICE in the PRICE tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definition: i like option number 1.[pickAnOption(1)]Asking for more options gets the user anadditional interpretation which is lesslikely to be the correct one.There are no moreoptions so the user mustselect an interpretationor give up. 53: who has paid under 58 for ace tennis net.Let's try a couple questions.CUSTOMERO.NAMEJOCKSPORTS: what did jocksports pay for ace tennis net.ITEMO.ACTUALPRICE50I added another database about movies. Let's try using it for a while.: steven spielberg directed jurassic park.MVDIRO.DIRNAME^MVMOVIEO.MVNAMEPENNY MARSHALL^LEAGUE OF THEIR OWNSPIKE LEE^MALCOLM XSTEVEN SPIELBERG JURASSIC PARKDo these examples seem reasonable?: yes.: who directed malcolm x?MVDIRO.DIRNAMESPIKE LEE: league of their own starred torn hanks.MVMOVIEO.MVNAME MVSTARO.STNAMEJURASSIC PARKLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNJEFF GOLDBLOOMGEENA DAVISMADONNATOM HANKSDo these examples seem reasonable?1: yes.: who did jurassic park star?54MVSTARO.STNAMEJEFF GOLDBLOOM: steven spielberg directed jurassic park.MVDIRO.DIRNAME^MVMOVIEO.MVNAMEPENNY MARSHALL^LEAGUE OF THEIR OWNSPIKE LEE^MALCOLM XSTEVEN SPIELBERG JURASSIC PARKDo these examples seem reasonable?Now well try defining twodifferent senses for theverb direct. Let's start withdirector directing movie.Notice that we defined thisearlier. The system canhandle such mistakes.: yes.: steven spielberg directed jeff goldbloom.Now we'll define the othersense of the verb direct -director directing star.MVDIRO.DIRNAMEPENNY MARSHALLPENNY MARSHALLPENNY MARSHALLSTEVEN SPIELBERGMVSTARO.STNAMEGEENA DAVISMADONNATOM HANKSJEFF GOLDBLOOMDo these examples seem reasonable?: yes.I : who directed malcolm x.MVDIRO.DIRNAMESPIKE LEE: who directed tom hanks.MVDIRO.DIRNAMEPENNY MARSHALLI : smith works for ford.EMPO.ENAME EMPLENAMEALLENFORDSCOTTWARDBLAKEJONESJONESBLAKE55Let's try two different senses of the verb works.One will relate to the employee database and onewill relate to the movie database. Will start withemployee works for manager.Do these examples seem reasonable?: yes.: tom hanks works for penny marshal!.MVSTARO.STNAME MVDIRO.DIRNAMEGEENA DAVIS^PENNY MARSHALLJEFF GOLDBLOOM STEVEN SPIELBERGMADONNA^PENNY MARSHALLTOM HANKS PENNY MARSHALLNow we'll define the 'movie starworks for director' sense.Do these examples seem reasonable? : yes.: who works for king.A couple of test questions.EMPO.ENAMEJONESCLARKBLAKEI : who works for steven spielberg.MVSTARO.STNAMEJEFF GOLDBLOOM563.6 SummaryThe main objective of this system is to provide a means to increase the portability ofnatural language interfaces. This has been facilitated by separating the components of thesystem based upon whether or not they are domain dependent (change with the domain ofdiscourse) or domain independent (constant over all domains of discourse). An overview ofthe control structures of the system has been presented to provide the reader with anunderstanding of how and what information is used during the analysis process. Thechapter concluded with a brief session with a program implemented to demonstrate theconfiguration process.Chapter 4Linguistic KnowledgeThis chapter discusses the components of the system that contain linguistic knowledge - thelexicon and the grammar. The purpose is to provide the reader with a feel for the extent ofthe coverage of the grammar.4.1 LexiconIn order to analyze utterances, knowledge about words is needed. This knowledge does notonly comprise knowledge about the possible meanings of words. Words also have structurewhich encodes meaning. For example, 'cow' refers to a single cow and 'cows' refers tomore than one cow. Morphology is the study of the internal structure of words. In order toavoid storing many different forms of a word, morphological analysis is used to extractadditional meaning from the structure of words. Words obviously have a function in anutterance. The function of the word affects how it can be used. For example, words used asa conjunction cannot appear at the end of a sentence. "I bought some eggs, cheese and", isnot a well formed sentence. In order to effectively analyze utterances, knowledge about the5758function of words is also necessary. A more detailed discussion of the function of wordsand morphology can be found in WINOGRAD83.The lexicon is used to store information about the function and meaning of words. Thelexicon is a dictionary which associates meanings with each word. In most cases, the rootform of a word is the only form stored in the lexicon. Exceptions are made for words withirregular forms which the morpher cannot analyze. The irregular forms are stored in thelexicon in addition to the root forms.The lexicon contains entries that are derived from many sources. Some sources are domaindependent and some are not. This section considers all of the information sources needed tobreak the utterance into tokens and assign interpretations to those tokens. Tokens, in thiscase, may be individual words or complex phrases.4.1.1 Word ClassesThe word classes used by the system are based upon common functional categories. For thepurposes of this discussion, the domain independent classes will be presented first, followedby the domain dependent classes.4.1.1.1 Domain Independent (Predefined)Domain independent words are defined before the system is used. Figure 4.1, contains the59word classes used by this system. The lexicon marks words as belonging to the classeslisted in this table where appropriate.Class Examples NotesPrepositions of, out of • used as markers for cases ofthe case framesAuxiliary Verbs had, been • includes tense, person, numberand root verbIrregular Verbs seek/sought • includes irregular form and rootformDeterminers the, a, which • marked as definite or indefinite• marked as question wordRelative Clause Markers that, which, who • can mark start of relativeclausesFunction Word Modifiers average, total • includes SQL function nameFigure 4.1 - Word Classes4.1.1.2 Domain DependentVerbs and nouns comprise a major part of the domain dependent part of the lexicon. Verbsare learned during interaction with the user. They are defined in terms of case frameswhich describe the meaning of the verb. Nouns that refer to frames or case frame slots suchas "employee" or "salary" are also learned during interaction with the user. After they arediscovered by the system, the morphological analyzer produces a root form which is thenadded to the lexicon.604.1.2 MorphingMorphology is the study of the structure of words and how that structure is used to affectthe meaning of words. Structure changes that affect word features, such as changing 'cow'(singular) to 'cows' (plural), are called inflections. Structure changes that affect themeaning of words, such as changing 'logical' to 'illogical', are called derivations. Themorpher, which is based upon an algorithm presented in WINOGRAD72 on page 72, cananalyze a large number of morphological structures but the system itself will only interpreta limited number of features marked by these structures (inflections). The system will notinterpret derivations. The morpher is employed during tokenization of the sentence. Forverbs, it is used to determine the verb tense (the difference between kill and killed). Thecode for the morpher is listed in the appendix.4.1.3 Implementation of the LexiconThis section describes the data structures used to implement the lexicon. The first sectiondescribes the data structure used to organize the lexicon, an inverse index, and the secondsection describes the data structure used to implement the inverted index.4.1.3.1 Inverted indexFigure 4.2 depicts a file containing information about the parts produced by a fictitiouscompany. The top row of the table contains the names of each column. The address columncontains a physical address of each row. This column is not an explicit part of the table. It61i-1.^ Address P# PNAME COLOR PRODUCER1001101120, 210'L^P1P2P3P4WidgetGizmoGadgitThingRedBlueRedBlueAcmeAcmeParts Inc.AcmeFigure 4.2 - Part Tableis shown to be referenced by the example. The P# column contains the number of each partproduced. The names of the parts are in the PNAME column. The remaining two columnsprovide information about each part. The COLOR column contains the color of the partsand the PRODUCER column contains the name of the company that produces the part.Producer Address Address Address ...AcmeParts Inc.100120110 210Figure 4.3 - Inverted Index for the Producer ColumnAn inverted index is constructed on a particular column of a table of data. Typically not allof the columns are indexed due to the cost of setting up an inverted index. For thisexample, an inverted index on the PRODUCER column will be described. The invertedindex is depicted in Figure 4.3. For each distinct value in the PRODUCER column of thetable of Figure 4.2, there is a row in the inverted index. In this case, there are only twovalues, "Acme" and "Parts Inc." in the inverted index. The inverted index associates rowaddresses with each value. The addresses are of rows that have the same value for thecolumn that the inverted index is set up on. So for the 'Acme' row in the inverted index,the address of all the rows in the parts table that contain 'Acme' in the PRODUCERcolumn are listed. These are rows 100, 110, and 210. This example illustrate that the62number of addresses associated with each value in the inverted index varies.The main reason for using an inverted index is to decrease processing time. For example, ifa list of red parts produced by Acme was desired and there was no inverted index, then alinear search must be performed on the parts table. However by using the inverted index,all the rows containing parts produced by Acme can be quickly accessed and then justthese rows can be searched linearly for red parts. Results could be even faster if theCOLOR column also was inverted. Then to find red parts produced by ACME, the list ofred parts and the list of parts produced by ACME could be intersected. The inverted indexis a means to produce results faster. A more detailed description of inverted indexing canbe found in BRADLEY82.4.1.3.2 Implementing the Inverted indexThe lexicon is an inverted index implemented using a TRIE data structure as described inSEDGE90. It is constructed by first loading the predefined words of the domainindependent part of the lexicon (knowledge store 5 of Figure 3.1) and then accessing thedatabase (knowledge store 8) of the user to load the domain dependent values. All columnsof the database are added to the inverted index. During the interaction with the user newnouns and verbs are added to the index.A TRIE is short for reTRIEval tree. The TRIE is an m-degree tree. Each record stored inthe tree has a key with a number of levels. In this case each level is a character. At a given63 • •^•^• Entry for Smith•^• Entry for toN).^• Entry for theFigure 4.4 - Part of a TRIEInput: The man shop is ....Output: (The) (man) (shop) (is) ...(The man shop) (is) ...Figure 4.5 - Different Tokensnode there is onebranch out for eachcharacter value atthe current level inthe key (seeFigure 4.4). In otherwords, each edge corresponds to a character. Techniques were employed to compress theTRIE. Due to compression, the TRIE for the test database had a depth of 7 although thelongest key in the TRIE was over 30 characters in length.The TRIE has an advantage over hashing for this application. When the sentences aretokenized prefixes of characters are pulled off and treated as a single token. There might bemore than one way to do this asshown in Figure 4.5. For the first case"the", "man" and "shop" are treated asindividual token in this domain. "Theman shop" is also a token, perhaps a store in a customer database. A TRIE allows thesystem to make use of the current position in the TRIE after processing the first alternative,in order to process output two. Under a hash table approach, the prefixes would have to bepicked off individually and have separate hash values computed. There is no reuse ofcomputation. For other flavours of trees the prefixes would also have to be picked off andsearched for individually. The TRW is able to reuse computation where the others do not.644.2 GrammarEffective natural language systems must analyze the structure of sentences. A grammar is adefinition of the structure of sentences that can be analyzed. There are a number ofsyntactic phenomena which a grammar must handle in order to be acceptable. Thefollowing sections outline which structures are in the coverage of the grammar of thissystem and the means used to represent and apply the grammar.4.2.1 Coverage4.2.1.1 PassivesThe subject and objects of a case frame are marked by position in a sentence. This positioncan be affected by the form of the sentence. If it is passive, then the syntactic subject, if itappears, must follow the verb and an object must precede it. This is the distinction betweenthe active and passive form of a sentence. Figure 4.6 lists some examples.Active Sentence Passive SentenceSally took the pen The pen was taken by SallyThe seals will raise the pups The pups will be raised by the sealsI closed the door The door was closedFigure 4.6 - Sentence Form4.2.1.2 Relative ClausesRelative clauses are a simple means for qualifying referents in a statement. They aremarked by function words such as that, who or which. A reduced relative clause is arelative clause that is not marked by one of those words. In Figure 4.7, examples fromALLEN87 3 , the relative clauses are underlined.The man who hit Mary with a book has disappearedThe man who(m) Mary hit with a book has disappeared.The man hitting Mary with a book is angry.The man Mary is hitting with a book is angry.The man Mary hit John with has disappeared.The man whose book was used to hit John has disappeared.The man with whom Mary disappeared wore a red hat.Figure 4.7 - Relative Clauses4.2.1.3 Wh-QuestionWh-questions are questions in which the wh-phrase has been moved to the start of thesentence such asWho does Smith manage.Who(m) does smith work for.For who(m) does smith work.The parser will handle only the cases where the phrase moved to the start of the sentence isnot marked (by a preposition). It will not accept the third example. This form of expression653 see page 13666is described in detail in ALLEN87.4.2.1.4 PossessivesPossessive noun phrases are marked with ' or 's after the final word of the phrase. Thissystem will accept multi-word possessive noun phrases with embedded relative clauses. Itwill also accept recursive embeddings of possessive markers. It will not recognise 'whose'as a possessive marker. Figure 4.8 lists some examples. The interpretation of the possessivemarker (described in section 4.2.1.7), is limited.Who is Smith's manager?What is the person working in research's average salary?What is Smith's manager's salary?Figure 4.8 - Possessives4.2.1.5 ImperativesImperatives are sentences in which the subject is the hearer and so is not stated explicitlyin the sentence. The parser will accept all imperatives although the system will onlyinterpret imperatives whose main verb is 'print', 'list', or 'show'. Figure 4.9 contains someexamples of imperative sentences that the system will accept.List employees working in research for Ford.Print the name, manager and salary of employees working in research.Figure 4.9 - Imperative Sentences674.2.1.6 Noise PhrasesNoise phrases are phrases that can be ignored when interpreting the sentence because theycannot be represented in the system's interpretation. The grammar will accept only somepolite sentence introductions as are shown in Figure 4.10. Although they are accepted, theywill not be interpreted.Would you please ...Can you ...I would like you to ...Please ...Figure 4.10 - Noise Phrases4.2.1.7 Semantic Grammar Based-PhrasesAnother aspect of the grammar is the use of productions that are defined in terms of thesemantic categories of phrases. This approach was only briefly explored and would benefitgreatly from more work.The system keeps track of frames that represent objects. The object frames have cases forobject names, and attributes. Inthis way, these objects are similarto the objects represented inobject-oriented languages althoughthe objects of this system have noCase Class Case FillerNames Last Name EMPLOYEE.NAMEAttributes Salary EMPLOYEE.SALCommission EMPLOYEE.COMMFigure 4.11 - Example Employee Framemethods. Figure 4.11 shows an example of a frame for employee information. This frame68contains one name for the employee, the employee's last name, and it can be found in theNAME column of the EMPLOYEE table. There are two attributes of the employeerepresented in the frame, the employee's salary which is found in the SAL column of theEMPLOYEE table and the employee's commission which is found in the COMM columnof the EMPLOYEE table. The object frames also contain information that ties theindividual cases together in terms of the database (described in detail in chapter 5).In order to use these object frames, special productions were set up to recognize referencesto these categories. The productions are defined in terms of phrases that representreferences to attributes and objects as opposed to noun phrases and so in this sense this partof the grammar can be regarded as a semantic grammar. The following DCG productions(Figure 4.12) which are simplified for illustration purposes recognize phrases referring toobjects. The actual productions which are integrated with the syntactic analysis forefficiency, are listed in appendix B.AttributeReference --> Determiner, AttributeWord, "OF", ObjectWordPossessiveObjectWord AttributeWord.AttributeList -->^Attribute, (",",!1[]), AttributeListl, "OF", ObjectWord, !(].AttributeListl -->"AND", Attribute, !1 Attribute, (",",!1(]), AttributeListlH.Sentence -->AttributeReference BEVerbPhrase, AttributeValuePrintVerbPhrase, AttributeList.Figure 4.12 - Semantic Grammar for Recognizing Object and Attributes69The AttributeReference production recognizes references to the attributes of objectssuch as, "the salary of Smith", or "Smith's salary". In both these examples, "Smith" is theobject and salary is the attributes. The AttributeList production recognizes a list ofattributes of an object such as "the name, age and salary of Smith". For this example,"Smith" is the object and "name", "age" and "salary" are attributes of Smith. The lastproduction Sentence recognizes the use of attribute phrases in sentences such as"Smith's salary is 800", or "Print the name, salary, and department of Smith". The formersentence is used to define salary and the latter is used to get a list of employee information.4.2.2 RepresentationThe previous section described the grammar of the system. In order to be employed, thegrammar must be encoded in a computational mechanism. For this system a definite clausegrammar (DCG) formalism is used. A detailed discussion of DCG can be found inPERWARR80. Appendix B contains a listing of the definite clause grammar of this system.4.3 SummaryLinguistic knowledge consists of knowledge about words and knowledge about phrases. Inaddition to being associated with a concept, the structure of a word can contain meaning. Alexicon is used to associate words with concepts and morphological knowledge is used to70analyze the structure of words to derive additional meaning. The lexicon is implementedusing an inverse index which provides a number of advantages over other techniques. Agrammar is used to contain knowledge about phrases. There are a number of different typeof phrases that the grammar must be able to recognize in order to function effectively. Therange of phrases that can be recognized by a grammar is called its coverage. The grammarof this system is implemented using the definite clause grammar notation.Chapter 5Becoming Portable Through LearningThis section describes the main knowledge representation structure of this system and howit is constructed. A brief introduction is given in order to help the reader understand wherethis structure fits into the overall system.5.1 Tokenization4After a sentence is read in, the system tokenizes it. The result is a sequence of words andphrasess referring to case frames, unknown words and words and phrases that appear in thedatabase. Some lexical information is produced as well. After tokenization, parsing occurs.5.2 Parsing4The parser produces a list of phrases. For each verb mentioned, there is a list of the casesfor that verb, and for each object there is a list of the attributes of that object. The table of4 - see Chapter 6 for a detailed example5 - such as 'The Body Shop' which appears in the database as a store name7172Figure 5.1 illustrates this information for the following sentenceWhich t mane working 3 in4 research5 works6 for, under8 Ford' s9 salary lo?Frame MarkerCaseMarker FillerWORK3 Syntactic Subject MAN2 (question)IN4 RESEARCH5WORK6 Syntactic Subject MAN2FOR, RANGE OVERSALARY 1 ,3FORD9 (marked by type) Attribute SalarYloFigure 5.1 - Cases and Fillers for Sample SentenceThere are two case frame markers shown in the table, WORK 3 and WORK6. Thesecorrespond to the different occurrences of "work" in the example sentence. For each ofthese case frame markers there are two cases present which are shown in the table. Thetable also contains one object frame marker, FORD 9. Type information that is known about"Ford" is used to determine which object frame should be used for interpretation. Only onecase is associated with "Ford", the salary attribute. The parse also contains otherinformation. Associated with each noun phrase is determiner information if there is any.Each verb phrase (case frame marker) has tense, number, auxiliary verbs and main verbinformation.735.3 Learning FramesThe systems learns the meaning of words by analyzing the relationship between statementsthat the user makes about the database and the data in the database. The results of thisanalysis are stored in frames - case frames for verbs and object frames for objects.5.3.1 Case FramesA case frame is used to store information about object relationships. The case frame ismarked by a verb. The system will not perform inferencing using case frames and so theonly way to access a case frame is to explicitly mention the marker.Case frames contain a number of cases which are determined through interaction with theuser. Each case has a marker. The marker is either a position number or a preposition.Position numbers are ordinals which indicate the surface position of the phrase in thesentence. A case can have more than one marker, and a case marker may mark more thanone case.The system supports multiple senses for a verb. This corresponds to a verb that is a markerfor more than one case frame. There is currently no way to tell the system that a new verbis a marker for a known case frame. Figure 5.2 is a sample case frame for works. It wasproduced from the sentences "Smith works for Ford", "Allan works for 1100" and "Fordworks in Research". In order to produce it, the values "Smith" and "Ford", "Allan" and1100, and "Ford" and "Research" wereindependently connected and latercombined into one frame.74Marker MeaningSyntactic Subject (1) EMPLOYEE.ENAMEFor MANAGER.ENAMEEMPLOYEE.SALIn DEPT.DNAMEFigure 5.2 - Case Frame for WorksAs described earlier, a case framecontains a number of cases - roles thatare played in the event corresponding to the case frame. In Figure 5.2, there are four caseswhich are shown along with their markers. The first case is the subject case which is filledby an employee. The employee is referenced by the name which appears in the ENAMEcolumn of the EMPLOYEE table. This case is marked by position. There are two caseswhich are marked by the preposition "for". One case is the role of manager of theemployee who fills the subject case. The manager case is filled by a name in the ENAMEcolumn of the MANAGER table. The other case marked by "for" is the employee's salarywhich is filled by a value in the SAL column of the EMPLOYEE table. The final case isthe department that the employee works in. This is marked by the preposition "in". Inaddition to this information, there is a data structure which describes how these cases arerelated. This data structure (which is not shown) is the spanning tree which is described indetail in section 5.3.3.5.3.2 Object FramesObject frames are used to keep track of information about objects. The only informationthat the system currently has about objects are names, and attributes. Attributes must beClass Marker FillerName "Name" EMPLOYEE.ENAMEAttribute "Salary" EMPLOYEE.SAL"Manager" EMPLOYEE.MGR"Department" DEPT.DNAMEFigure 5.3 - Employee Object Frame75defined in terms of the database information. There is no object hierarchy. Object framesare marked by the object frame names, such as employee, or by the type of an objectmentioned such as "Fred"'s type which is EMP table - ENAME column. As describedearlier, some grammar productions exist especially for recognizing references to objectframes.Attributes of an object are marked by words such as salary or manager (the system doesnot calculate manager from manage). The following object frame (Figure 5.3) wasproduced from the sentences"Smith's manager is Ford", "Thedepartment of Smith is research",and "Allen's salary is 800" whichwere independently analyzed andcombined. The filler informationactually references the spanning trees described later in this section and not the databasedirectly. The fillers are shown for illustration only.5.3.3 Minimal spanning TreesThe knowledge structure used in the frames of the system is a type of semantic net. Thesemantic net is viewed as a spanning tree over a database graph. The semantic net in thiscontext is called a generalized minimal spanning tree of the database graph for the set ofdatabase graph nodes, N. The next section defines these terms and presents an algorithm76for calculating these spanning trees.5.3.3.1 Definitions5.3.3.1.1 Database GraphThe database graph (DBG) is implicitly represented by the database. Each node in thedatabase graph is the entry at a particular row and column of a table in the database 6 .There is an edge between two database graph nodes if they are in the same row or if theyhave the same value' (used for joins). Associated with each edge between nodes that havethe same value is the join condition required to connect the tables corresponding to each ofthe nodes. Figure 5.5 depicts the database graph for the portion of the database shown inFigure 5.4. In the graph in Figure 5.5, the thicker edges connect nodes of the same valueand the thinner edges connect nodes in the same row. The observant reader will note thatnot all of the thinner edges have been shown. For each pair of nodes in the same row, thereshould be a thin edge incident. All of these thin edges are not shown because the drawingwould need to contain 212 thin edges to accurately reflect the connections among nodes inthe same row. The algorithm will act as though all of these edges are present.6 - See appendix A for a brief description of relational database terminology7 - Exceptions:• nodes cannot be in the same column of the same table• no reflexive edges (edge from a node to itself)77DEPTDEPTNO DNAME10 ACCOUNTING20 RESEARCHEMPEMPNO ENAME JOB MGR HIREDATE SAL COMM DEPTNO7369 SMITH CLERK 7902 17-DEC-80 800 207876 ADAMS CLERK 7788 12-JAN-83 1100 207902 FORD ANALYST 7566 03-DEC-81 3000 20Figure 5.4 - Tables Used by Examples5.3.3.1.2 Minimal spanning TreeA minimal spanning tree (MST) is a sub-tree of the database graph. The minimal spanningtree is defined relative to a set of database graph nodes, N. Spanning means that the treecontains the set of database graph nodes, N. The tree is minimal in the sense that there isno proper sub-tree of the tree which spans the given database graph nodes, N. The databasegraph nodes correspond to phrases mentioned in the defining sentences. Figure 5.6 containminimal spanning trees for the connecting the values "Smith", "Clerk", and "800".Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol:DEPTNORow: 2Value: 20Table: DEPTCol: DNAMERow: 1Value:ACCOUNTINGTable: DEPTCol: DNAMERow: 2Value:RESEARCHTable: EMPCol: EMPNORow: 1Value: 7876Table: EMPCol: ENAMERow: 1Val: SMITHTable: EMPCol: JOBRow: 1Value:CLERKTable: EMPCol: MGRRow: 1Value: 7902Table: EMPCol: SALRow: 1Value: 800Table: EMPCol:DEPTNORow: 1 ^-Value: 20Table: EMPCol: EMPNORow: 2Value: 7369Table: EMPCol: ENAMERow: 2Val: ADAMSTable: EMPCol: JOBRow: 2Value:CLERKTable: EMPCol: MGRRow: 2Value: 7788Table: EMPCol: SALRow: 2Value: 1100Table: EMPCol:DEPTNORow: 2Value: 20Table: EMPCol: EMPNORow: 3Value: 7902Table: EMPCol: ENAMERow: 3Val: FORDTable: EMPCol: JOBRow: 3Val:AnalystTable: EMPCol: MGRRow: 3Value: 7566Table: EMPCol: SALRow: 3Value: 3000Table: EMPCol:DEPTNORow: 3Value: 20Figure 5.5 - Database Graph for Table of Figure 5.45.3.3.1.2.1 Formal Definition of MSTsFor the following definitions, G is a database graph, Values are a set of values that appear78in the database, and Nodes is a set of database graph nodes that correspond to the values in79Table: EMP •• Table: EMPCol: EMPNO _ 04:1(10- ,1•1^Col: MGRRow: I .^...... ROsk Row: IValue: 7876 -1. • Vik.:310811:•::.:: VaiteLlitt Value: 7902 ValtiO1•800?: . :Table: EMPCol:DEPTNORow: 1Value: 20Table: EMPCol: EMPNORow: IValue: 7876Table; EIWPCO JOBRow: IVataBRKTable: EMPCol: MGRRow: IValue: 7902Table: EMPCot SALRow: IValue: 800Table: EMPCol:DEPTNORow: 1Value: 20Table: EMP Tale RAP:: Table: EMP TOW EMP Table: EMPCol: EMPNO •C .:•.:R.014E• Col: MGR CSC::: Col:Row: 1 Row: I Row; I DEPTNOValue: 7876 . V*:$/filFra::; • Value: 7902 %duel 800 . Row: 1Value: 20Figure 5.6 - Three Minimal Spanning Trees for "Smith works as a clerk for 800 dollars"the set of values, Values.SpanningTreesG(Nodes) - STG(Nodes) - {tit QG A isTree(t) A Nodes zNodes(t)} (1)MinSpanTreesG(Nodes) - MSTG(Nodes) - {tit ESTG(Nodes) A 3(t i ESTG(Nodes)) t/ ct(2)Table: EMPRow: 1ENAMESMITHJOB• CLERICSALARY: 800Figure 5.7 - GMST80Meaning of Values is select one of^U^MSTG(Nodes)Each Set of Nodesfor Values(3)As seen in equation (3), the meaning is an arbitrarily selected tree of a set of MSTs. Thegoal was to try to avoid using structural properties of the tree as the sole criteria forselecting the meaning. In some cases, interaction with the user is necessary to determinethe correct interpretation (WHITE85). By providing this leeway, the system is able toimpose other selection constraints automatically or to interact with the user in order toselect a meaning.5.3.3.1.3 Generalized Minimal spanning Tree5.3.3.1.3.1 A Problem with MSTAlthough minimal spanning trees effectively capture meaning, they are not efficient. Largenumbers of equivalent trees can be produced for a given setof values. As shown for the sentence, "Smith works as aclerk for 800 dollars", there are three equivalent spanningtrees (see Figure 5.6). By using a generalized minimalspanning tree (GMST), the number of alternatives is reducedto one (see Figure 5.7).These problems with the MSTs arise because the nodes in the same row form a complete81sub-graph of the database graph. Each of the different minimal spanning trees select adifferent path through this sub-graph. The generalized minimal spanning tree (GMST) wasdefined to avoid this.5.3.3.1.3.2 GMST DefinitionThe GMST is an equivalence class of MSTs. The nodes of the GMST are sets of columnsin the same table and row. There is an edge between GMST nodes iff there is an edge inthe MST between columns in each GMST node. For example, the GMST in Figure 5.10corresponds to the MST in Figure 5.8 (and Figure 5.9). Notice that there is a node in theGMST for each row in the MST and the edges in the GMST corresponds to the 'join'edges of the MST. The algorithm is given in terms of the MST because that is easier tounderstand and changing the algorithm to work with GMSTs only requires converting thedata structure that represents the MST to a data structure that represent the GMSTequivalence class.5.3.3.2 ExamplesThe following example illustrates the various definitions for the sentence "Smith works asclerk in research under Ford for 800 dollars". This sentence is hard to process becausethere is a lot of ambiguity about how the database is encoding this information. Thepurpose of using this sentence is to generate a complicated example.825.3.3.2.1 Values to DBG Node MappingsThe first step in the process of generating trees is to associate values in the sentence withnodes in the trees. This will be shown in detail in a later example (section 5.3.3.3.2).5.3.3.2.2 MSTsFigure 5.8 and Figure 5.9 depict two MSTs for the example. The thick line marks theMST. Nodes that are in the MST are darkened. There are many others which are not shownfor the sake of brevity.Table: EMPCol: EMPNORow: 1Value: 7876Table: EMPCol: EMPNORow: 2Value: 7369Table: EMPCol: ENAMERow: 2Val: ADAMSTable: EMPCol: JOBRow: 2Value:CLERKTable: EMPCol: MGRRow: 2Value: 7788Table: EMPCol: SALRow: 2Value: 1100Table: EMPCol:DEPTNORow: 2Value: 20 Table: EMPCol: JOBRow: 3Val:AnalystTable: EMPCol: MGRRow: 3Value: 7566Table: EMPCol: SALRow: 3Value: 3000Table: EMPCol:DEPTNORow: 3 —Value: 20Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol: DNAMERow: 1Value:ACCOUNTING83Figure 5.8 Example minimal spanning trees connecting "Smith", "Clerk", "800","Research", and "Ford"84Figure 5.9 - Another Spanning Tree For "Smith", "Clerk", "800", "Research", and "Ford"5.3.3.2.3 GMSTsFigure 5.10 depicts one of the GMSTs for the sentence. Another possibility, not shown, isto associate "Research" with "Ford". Each box in the diagram marks a GMST node whichis identified by the table name and the row number. The edges connecting the nodes mark 85Table: EMPRow: 1Table: DEPTRow: 2ENAMESMITHJOB: CLERKSALARY: 800MGR: 7902DEPTNO: 20 ♦DEPTNO: 20DNAME:RESEARCHTable: EmpRow: 3EMPNO: 7902ENAME: FORDFigure 5.10 - Generalized Minimal Spanning Treethe columns which are used to join the tables corresponding to the nodes which are beingconnected.5.3.3.3 AlgorithmThis section presents the algorithm for calculating the GMSTs. A number of heuristics aredescribed, first followed by an example and then by the definition of the algorithm. Theapproach is based upon well known graph algorithms for calculating spanning trees.5.3.3.3.1 HeuristicsAccording to the definition of the MSTs, the meaning is selected from one of a number of86trees. No additional criteria for selection is given. This section describes some additionalconstraints that are used in order to select a MST.5.3.3.3.1.1 Produce the Best Guesses First (Solution Space Ordering)One common approach used to enhance search is to use a cost function. A cost function isused here but it should be stressed that the cost function is used to affect the order inwhich solutions are generated and is not used to eliminate GMSTs from consideration butonly to possibly postpone their consideration. The goal is to produce the best guesses firstand avoid presenting the user with too many choices at once.5.3.3.3.1.1.1 Tree CostAccording to Occam's Razor the simplest approachmay be the best. In this case, simple was taken tomean the fewest number of table joins (ie MSTedges) and the fewest number of nodes. The cost ofa tree is defined in such a way that ideally theType CostKey 1Foreign Key 2Other 20Figure 5.11 - 'Join' Edge Costsimplest trees will have lowest costs. The cost of a MST is the 'join' edge cost plus the'same row' edge cost. Currently the 'same row' edge cost is 4. The 'join' edge costdepends on the type of nodes joined. These nodes can be keys', foreign keys or other. Thecost of a 'join' edge is the sum of the node type cost of the incident nodes. Currently the8 - See appendix A87cost of a key node is 1, foreign key is 2, and other 20. These values were determined bytrial and error. Figure 5.12 illustrates a tree cost calculation. In this example, the cost ofconnecting the EMPNO node of the EMP table at row 3 to the MGR node of the EMPtable at row 1 is 3 because the former is a key which has cost 2 and the latter is a foreignkey which has cost 1.5.3.33.2 ExampleThe algorithm used for calculating the spanning tree of a given set of values combines aslight generalization of Prim's algorithm for calculating spanning trees of a graph with abest first search (TARJAN83). The basic approach is to start with a tree that spans one ofthe values. This is a tree with only the node corresponding to the value in it. Then for eachother value to be connected, a path is sought from the node for that value to a node in thecurrent spanning tree. The following example illustrates the generation of a minimalspanning tree for the values "Smith", "Clerk", "800", "Research", and "Ford". Note that theexample is generating a MST not a GMST in order to better illustrate important points. Theexample is a depth first search that makes correct decisions at all points. The algorithmdefined later is a best first search.5.3.33.2.1 Establish Value to Node MappingThe first step is to establish a correspondence between the values mentioned in the sentenceand the database graph nodes. At this point morphing and spell checking could cause theJoin Cost 3Table: EMPCol: EMPNORow: IValue: 7876Table: EMPCol: EMPNORow: 2Value: 7369Table: EMPCol: ENAMERow: 2Val: ADAMSTable: EMPCol: JOBRow: 2Value:CLERKTable: EMPCol: MGRRow: 2Value: 7788Table: EMPCol: SALRow: 2Value: 1100Table: EMPCol:DEPTNORow: 2 mValue: 20 oin Cost 3Table: DTP^Table: ElseCol: JOB Col: MGRRow: 3^Row: 3Val:Analyst^Value: 7566Table: EMP^Table: EMPCol: SAL Col:Row: 3^DEPTNOValue: 3000^Row: 3Value: 20..BMIPNC)Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol: DNAMERow: 1Value:ACCOUNTINGr-'`)88Total Cost is 30Figure 5.12 - Tree Cost Calculation89value to be mapped to a node that does not have exactly the same value. However this hasnot been implemented. Figure 5.13 depicts the mapping of values to nodes. The values arelisted at the top of the figure and dotted arrows are used to indicate their correspondingnodes.90Figure 5.13 - Establish Value to Database Graph Node Correspondence91After determining the correspondence, a priority queue of node groups is set up. The queuecontains one set of nodes for each value to be connected. The smaller sets are listed first inarbitrary order. Figure 5.14 contains the initial values queue. The front of the queue is tothe left.Smith^Ford^800^ResearchClerkTable: EMPCol: JOBRow: IVal:CLERKTable: EMPCol: ENAMERow: 1Val: SMITHTable: EMPCol: ENAMERow: 3Val: FORDTable: EMPCol: SALRow: 1Value: 800Table: DEPTCol: DNAMERow: 2Value:RESEARCH Table: EMPCol: JOBRow: 2Val:CLERKFigure 5.14 - Values QueueAfter the queue is set up, the frontier is created. The first MST contains one of thedatabase graph nodes in the first set of database graph nodes from the priority queue. Thereis one MST for each node in the set. In this case there is only one MST. Figure 5.15depicts the first MST with one node in it (nodes in the current MST are marked by greyshading) and Figure 5.16 shows the values queue after the first entry is removed.92Figure 5.15 - First MST93Ford^800^ResearchClerkTable: EMPCol: JOBTable: DEPT Row: IVal:CLERKTable: EMP Table: EMP Col: DNAMECol: ENAME Col: SAL Row: 2Row: 3 Row: 1 Value:Val: FORD Value: 800 RESEARCH Table: EMPCol: JOBRow: 2Val:CLERKFigure 5.16 - New Values QueueThe next step is to connect the node for "Ford" to the current MST. This is done bysearching for paths from each node for "Ford" (marked by box with diagonal line shading)to the MST. In Figure 5.17 the dashed line marks the path found from "Ford", the newnode, to the current MST. All nodes along this path including the first are shaded withdiagonal lines. Figure 5.18 shows the values queue after adding "Ford".Table: DEPTCol: DNAMERow: 2Value:RESEARCH("ThIIIIIII• Mir • •Table: EMPCol: EMPNORow: 1Value: 7876Coh-ENAMEAra1:314TIV •Table: EMPCol: JOBRow: 1Value:CLERKTable: EMPCol: SALRow: IValue: 800Table: EMPCol:DEPTNORow: 1 -Value: 20Table: EMPCol: EMPNORow: 2Value: 7369Table: EMPCol: ENAMERow: 2Val: ADAMSTable: EMPCol: JOBRow: 2Value:CLERKTable: EMPCol: MGRRow: 2Value: 7788Table: EMPCol: SALRow: 2Value: 1100Table: EMPCol:DFPTNORow: 2^--r•Value: 20• ' • •■&, s'^•Table: EMPCol: JOBRow: 3Val:AnalystTable: EMPCol: MGRRow: 3Value: 7566Table: EMPCol: SALRow: 3Value: 3000Table: EMPCol:DEPTNORow: 3Value: 20Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol: DNAMERow: 1Value:ACCOUNTING/ThTable: DEPTCol:DEPTNORow: 2Value: 2094Figure 5.17 - Connecting FordTable: EMPCol: SALRow: IValue: 800Table: DEPTCol: DNAMERow: 2Value:RESEARCH800 ^ResearchTable: EMPCol: JOBRow: 1Val:CLERKTable: EMPCol: JOBRow: 2Val:CLERKClerkFigure 5.18 - New Values Queue95Now we add 800 (Figure 5.19). Figure 5.20 contains the queue after adding 800.TiA: Ei4P. T^.MCPTable: EMP Table: EMPCol: EMPNO COI:MAME —^Col: JOB ^ MGRRow: 1 Row: Row: 1 . I ^Value: 7876 Vot.14011/ Value:CLERK 7902Table: EMPCol:DEPTNORow: 1 -Value: 20♦♦Table: EMPCol:DEPTNORow: 2 -Value: 20Table: EMPCol:DEPTNORow: 3 -Value: 20Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol: DNAMERow: 1Value:ACCOUNTINGTable: DEPTCol:DEPTNORow: 2Value: 20Table: DEPTCol: DNAMERow: 2Value:RESEARCHTable: EMP Table: EMP Table: EMP Table: EMP Table: EMPCol: EMPNO Col: ENAME Col: JOB Col: MGR Col: SALRow: 2 Row: 2 Row: 2 Row: 2 Row: 2Value: 7369 Val: ADAMS Value:CLERK Value: 7788 Value: 1100Table: EMPCol: JOBRow: 3Val:AnalystTable: EMPCol: MGRRow: 3Value: 7566Table: EMPCol: SALRow: 3Value: 300096Figure 5.19 - Connecting in 800 97ClerkResearchTable: EMPCol: JOBRow: 1Val:CLERKTable: DEPTCol: DNAMERow: 2Value:RESEARCH Table: EMPCol: JOBRow: 2Val:CLERKFigure 5.20 - New Values Queue"Research" is connected now (Figure 5.21). At this point there is ambiguity about whetheror not to connect it to "Ford" or to "Smith". The real algorithm would allow both. Here, wewill arbitrarily choose "Smith".98Table: DEPTCol:DEPTNORow: IValue: 10Table: DEPTCol: DNAMERow: IValue:ACCOUNTINGTable: EMPCol: EMPNORow: 1Value: 7876Table: EMPCol: JOBRow: 1Value:CLERKTable: EMPCol: EMPNORow: 2Value: 7369Table: EMPCol: SALRow: 2Value: 1100Table: EMPCol: MGRRow: 2Value: 7788Table: EMPCol: JOBRow: 2Value:CLERKTable: EMPCol:DEPTNORow: 2Value: 20Table: EMPCol:DEPTNORow: 3Value: 20Figure 5.21 - Connecting "Research" to "Smith"99ClerkTable: EMPCol: JOBRow: 1Val:CLERICTable: EMPCol: JOBRow: 2Val:CLERKFigure 5.22 - NextValues QueueThe last step is to connect "Clerk" (Figure 5.23). Here we must choose a database graphnode to represent "Clerk" from the two choices. We will arbitrarily select the correct one.The real algorithm which does a best first search would try the other node for "clerk" andthen immediately give up due to cost. It would try that node again later if the user insistedon seeing more alternative interpretations.SIP Table:^PTable: EMP .•:: Table. AV::: •••Col: EMPNORow: 1'-•::•.(WESA141.90 MDR COLS/4',RD*Value: 7876 <Nat SiaTff.•' .. : Va1e::•.800Table: EMP Table: EMP Table: EMP Table: EMP Table: EMPCol: EMPNO Col: ENAME Col: JOB Col: MGR Col: SALRow: 2 Row: 2 Row: 2 Row: 2 Row: 2Value: 7369 Val: ADAMS Value:CLERK Value: 7788 Value: 1100Table: EMPCol:DEPTNORow: 3Value: 20Table: EMPCol: JOBRow: 3Val:AnalystTable: EMPCol: MGRRow: 3Value: 7566ORMTaisloXCAlkReeitel 3Vat EOMTable: EMI'Cot:DEPTNORow: IValue 20Table: EMPCol:DEPTNORow: 2Value: 20Table: EMPCol: SALRow: 3Value: 3000Table: DEPTCol:DEPTNORow: 1Value: 10Table: DEPTCol: DNAMERow: 1Value:ACCOUNTINGTable: ninCotDEMO ^Raw 2Vahie: ^• Table. DEPTCUtDitlAtilE:•••.:.RESEARCW100Figure 5.23 - Connect in "Clerk"At this point the queue is empty and so the tree is complete. This example left out anumber of implementation details which are discussed in later sections. The next sectionpresents a pseudo-code definition of the best first search implementation of this algorithm.1015.3.3.3.3 Definitiongmsts( [M, N], Frontier, Solutions )IF Frontier is Empty THENRETURNget best GMST-ValuesQueue from FrontierIF cost(GMST) > N THENRETURNIF ValuesQueue is empty THENIF cost(GMST) >= M THENAdd GMST to SolutionsELSEget next NodesList from ValuesQueueFOR EACH node IN NodesListfind path, P from node to GMSTIF P union GMST is a Treeadd (P union GMST)-ValuesQueue to the FrontierNEXT nodegmsts( [M, N], Frontier, Solutions )Figure 5.24 Pseudo-Code Which Generate GMSTs such that M <= cost(GMST) <= NFrontier is a priority queue with the lowest cost GMSTs listed first. Values queue is apriority queue with the smallest list of nodes first. As mentioned earlier this is a best firstsearch implementation of the approach demonstrated by the example.5.3.3.4 Implementation Notes5.3.3.4.1 Cycle CheckThe implementation of the algorithm takes advantage of the fact that the frontier contains102only trees. So when a new node is connected to a tree in the frontier, the resulting graph isconnected. Since the graph is connected then it is well knoWn that the graph is a tree if andonly if the number of edges is equal to the number of nodes minus one. This provides anefficient test for performing a cycle check after a node is connected to a tree in the frontier.5.3.3.4.2 Extension of Tree IsomorphismThe GMSTs are used to eliminate redundant MSTs. However it was realized late in thedevelopment stage that there is another form of redundancy the GMSTs do not eliminate.Consider the following GMSTs for the sentence "TKB Sport shop bought an ace tennis netfor 58 dollars".Figure 5.25 - Choice 1 Figure 5.26 - Choice 2103The transitivity property of equality (arising from the join conditions) implies that thesetwo GMSTs are equivalent. To see this, consider the join conditions that are represented bythe graphs in Figure 5.25 and Figure 5.26. There is only one difference between these twotrees. In Figure 5.25, the PRICE table is connected to the PRODUCT table by the dashededge. In Figure 5.26, the PRICE table is not connected to the PRODUCT table but isinstead connected to the ITEM table. Each dashed edge corresponds to a join condition inthe SQL. For the first graph (Figure 5.25), the join condition is PRICE.PRODID =PRODUCT.PRODID and for the second graph (Figure 5.26), the join condition isPRICE.PRODID = ITEM.PRODID. For both graphs there is an edge connecting thePRODUCT and the ITEM nodes. This edge corresponds to the join conditionITEM.PRODID = PRODUCT.PRODID. This implies that the join condition of the twographs are logically equivalent. To see this, consider the graph of Figure 5.25, the joincondition includes PRICE.PRODID = PRODUCT.PRODID and PRODUCT.PRODID =ITEM.PRODID. From this, one can deduce that PRICE.PRODID = ITEM.PROD (ie -(A - B A B - C) D A -C). This is the join condition for the other graph as well. So the twographs describe logically equivalent interpretations.This consideration was incorporated in the definition of GMSTs isomorphism used in theprogram but not directly in the GMST data structure. It should also be noted that the costsof these two graphs are not the same. In one case the join is between two keys(PRICE.PRODID and PRODUCT.PRODID) and in the other the join is between a key anda foreign key (PRICE.PRODID and ITEM.PRODID).1045.3.3.4.3 Can't Join Table to itself by the Same Column (Directly or Indirectly)Another constraint put on the implementation is to not allow a table to be joined to itselfby the same column. This can happen directly or indirectly as a result of joining a numberof tables. For exampleJoin: Customer 1 to Order 1 by Customer 1.CustID = Order 1.CustIDJoin: Order 1 to Customer2 by Order 1.CustID = Customer2.CustIDDue to the transitivity of equality, the effect of these joins is to connect the customer tableto itself by the CustID column. The leeway given in selecting a meaning has been usedhere to eliminate a special case which has no value.5.3.3.4.4 Avoiding Combinatorial Explosion53.3.4.4.1 Value to node mappingsAnother problem that can arise in searches is combinatorial explosion. This is where thenumber of alternatives becomes very large through the effect of making a number of non-deterministic choices. In this context, the problem can arise when mapping values todatabase graph nodes (as in Figure 5.13). For the test database, "1" has over 30 mappings.If the user enters "TKB Sport Shop bought 1 ace tennis net", there would be three values toconnect but the "1" value has more than one possible mapping to a database graph node.The mapping of these values to database graph nodes is shown in Figure 5.27. Only three105of the mappings of "1" are shown.ValueDatabase Graph NodesTable Column Row ValueTKB Sport Shop CUSTOMER NAME 2 TKB Sport ShopAce Tennis Net PRODUCT DESCRIPT 5 Ace Tennis Net1 ITEM QUANTITY 1 1ITEMID 2 1QUANTITY 2 1Figure 5.27 - Value to Node MappingBy ordering the selection of which of these node to consider, the system can try to avoidconsidering the nodes for "1" until it has considered the nodes for the other two values.This will increase the number of constraints on the solution which may help reduce thenumber of alternative mappings of "1" that are kept. Producing the solutions in order ofcost also helps to minimize this problem.5.3.3.4.5 Graph IsomorphismFor general graphs, checking isomorphism is time consuming. In this case, the nodes of thegraph are typed by the table and column. This means that the bijection that maps nodes inone graph to nodes in the other has an additional constraint. The matched nodes must be inthe same table at the same column. There is only one such bijection between two graphswhenever a table is not joined in more than once. The number of bijections is no more thanthe product of the number of times each table is joined in. So if the employee table is106joined in twice and the department table once, then there are at most two times onebijections. In order to cause graph isomorphism to be time consuming, several tables wouldhave to be joined together many times. However this would cause problems for thedatabase as well.10753.3.4.6 Producing the Most Reasonable Tree FirstI: tkb sport shop paid 58 for ace tennis net.2 Interpretations. They Are:Option #1"58" refers to ACTUALPRICE in the ITEM tableOption #2"58" refers to ITEMTOT in the ITEM tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definition1: can you show me some more options.[moreOptions]3 Interpretations (1 are new). They Are:Option #1"58" refers to ACTUALPRICE in the ITEM tableOption #2"58" refers to ITEMTOT in the ITEM tableOption #3 (New)"58" refers to STDPRICE in the PRICE tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definitionI : more.[moreOptions]There are no more alternative interpretations.All alternatives have been listed.3 Interpretations. They Are:Option #1"58" refers to ACTUALPRICE in the ITEM tableOption #2"58" refers to ITEMTOT in the ITEM tableOption #3"58" refers to STDPRICE in the PRICE tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definition: i like option number 1.[pickAnOption(1)]Figure 5.28 - Presenting the User with Different InterpretationsIn order to seem intelligent to the user, the system will select only some of the alternativetrees which can connect a set of values and present them to the user (Figure 5.28). Thesystem presents a summary of the differences between the choices if there is more than one108choice, or a number of examples if there is only one choice. The user can confirm a choiceor ask for more alternatives. The system uses the tree cost to determine the order that thesolutions will be presented. The tree cost is most effective when the keys and foreign keyshave been identified; however, the system does not require that they be identified. In factthey can even be incorrectly identified. A number of heuristics can be used by the systemin order to determine keys and foreign keys.5.3.3.4.6.1 Recognizing Keys and Foreign KeysIn some DBMS, such as DBase, joins can be specified directly in the system and so noinvestigation is necessary. Other DBMS provide means to directly define columns as beingkeys or foreign keys. Some systems, however, have no such facilities. For these systemssome simple rules of thumb can be used.Columns with a large number of unique values are probably keys. Columns with a largenumber of rows but a small number of values are probably foreign keys. The keys can besearched for the parent key of the foreign key. All of these tests can be done with simpleSQL commands and remember that the system does not require that the analysis be correct.It should be noted that the system does not currently determine which columns are keysand which are foreign keys.Figure 5.29 - Search from Each New Node to GMSTFigure 5.30 - Search from GMST to all New Nodes1095.3.3.5 ImprovementsThere are a number of improvements that could be made to the algorithms. Some makethem faster and some make them more general.5.3.3.5.1 Search Direction ChoiceA search occurs whena new node is to beconnected to the bestGMST. Starting atthe new node, pathsto the GMST aresought. This isefficient when the number of new nodes is small. However if there are many new nodes itwould be better tosearch from the GMSTto the new nodes. To dothis the algorithm mustchose the direction ofsearch dynamically. Thedirection of searchchoice would be madeusing branching factors1 10in each direction. This could be estimated with the number of nodes in the GMST and thenumber of new nodes to be connected.5.3.3.5.2 More Sophisticated JoinsThis system allows only simple joins to occur. Single columns are joined using equality. Itis possible to extend the system to multi-column joins that use only equality tests. Thiswould be done on the join conditions of the 'same value' edges in the database graph.When such a join was desired, the additional nodes in the join condition would need to beadded to the GMST. Other type of joins might be also required.Tables might be joined by using calculated values or tests that are not equality. Anotherpossibility is multi-column joins using only a subset of the columns of another multi-column join. Of course it is possible to imagine many strange ways of joining tables. Mostof which are not realistic. No attempt was made to handle these types of joins because itwas unclear how realistic they are.5.3.4 AmbiguityIn some cases the user's example sentence can have a number of interpretations. For these,the system interacts with the user in order to determine which selection is intended. Unlikeother systems which produce paraphrases of the interpretations, this system performs someanalysis of the alternatives to determine what is the difference between them. The user is111only presented with descriptions which distinguish between the alternatives'. The analysisis performed using an identification tree which is a type of decision tree (WINSTON91).A number of other approaches that would provide a better environment in which to resolvethis ambiguity, are considered here. The first approach is to provide examples of theinterpretation using data from the database. When there is only one interpretation thesystem does show examples but the user has no control over the selection of examples.Control over the example generation could be provided by allowing the user to askquestions using the different possible interpretations. Another nice feature would be toallow the user to ask questions about the objects mentioned in the examples. Providinginformation about how things are being connected would also be an interesting extensionbut some work would have to be done to determine a clear form for presentation. It wouldalso be reasonable to allow the sophisticated user to ask for an SQL paraphrase of theinterpretations. All of these features but the 'show how they are connected' one would bestraightforward to implement.5.4 Learning Word MeaningsAside from learning frames the system also learns which words mark which frames orframe slots. The first way this learning occurs is obvious but the second is more subtle.When the user presents example sentences such as "Smith works for Ford", "works" is9 for an example see Figure 5.28.112recognized as a verb marking the "work" case frame. For the sentence "Smith's salary is800", the system learns that the word "salary" marks the "salary" attribute slot of theemployee object frame. The system also learns type information about "Ford" which usedto mark the object frame. It is obvious that the learning of words is occurring here.The second place where word meanings is learned is from user questions. When the userasks "Which employees work for Ford", the system has learned that "employee" 1° marksthe subject slot of the "work" case frame. When the user asks "Which employee's salary is800", the system has learned that the word "employee" marks the "employee" object frame.There are probably many other places where unintrusive learning can occur. This is but onewhich was investigated.5.5 SummaryThis chapter described the spanning tree approach to database configuration. By viewingthe database as a graph, called the database graph, relationships among elements in thedatabase can be found by using straightforward spanning tree algorithms derived fromgraph theory. The minimal spanning tree is used to represent these relationships through itsstructure. It was found that the minimal spanning tree represented information redundantlyand so the generalized minimal spanning tree was defined to eliminate this problem. Inaddition to presenting a pseudo-code algorithm for calculating the generalized minimalspanning trees a detailed example was presented. The chapter concluded with notes about10 - The morpher is usedimplementing an efficient version of the algorithm.113Chapter 6Question AnsweringThe tree structures described in the previous chapter are used during question answering tointerpret sentences. During the process of question answering, the system can also learn themeanings of some words. This section describes this process through an example.6.1 ExampleThe example proceeds by examining the process of analyzing a question using the sentencein Figure 6.1. The stages of processing are described according to the data flow diagram ofFigure 3.2.Who earns over the average salary of an employee working in research?Figure 6.1 - Example Sentence6.1.1 TokenizingThe first stage of analysis of a sentence is the stage where the sentence is broken downinto tokens (Tokenizer - process a of Figure 3.2). The lexicon (inverted index) is accessedin order to determine which sequences of characters should be treated as a single token.The basic idea is to select prefixes of the input string which appear in the lexicon. If a114 through theWho earns ...index forFigure 6.2 - Initial prefixes ofPosition in theSentence^the sentence.t • (What)a/ rh e •• •X y \NS. s•• (Who) •(Why)• e • (Where)e• (Whose)The nextstep is tomove oneposition toWho earns ...Figure 6.4 -Sentencethe left in the sentence(Figure 6.4). The letter" that istraversed (in this case 'w') is used1 15prefix does not appear in the lexicon then spaces and punctuation are used as delimiters inorder to create a token. A search is conductedFigure 6.3contains the inverted index in theform of a TRIE. The initial Figure 6.3 - Initial Position in the TRIEposition (at the root) is marked by the arrow. Figure 6.2 contains the sentence that is beingtokenized. The initial position is before the first letter of the sentence.t • (What)e^(Where)h^e^• ••xtY ^s••• (Who)^• • (Whose)(Why)Figure 6.5 - Inverse Indexto select the arc in the TRIE to traverse (Figure 6.5).11 - not case sensitiveThetraversalWho earns ...4successfulFigure 6.6 - wasSentence After 'h'Figure 6.8contains thesentenceafterWho earns ...4Figure 6.8 -Sentence after 'o'• e • (Where)re• • (Whose)so processing continues. If thetraversal were not successful thenspaces and punctuation would beused as delimiters in order to determine a prefix. The next step in the input sentence(Figure 6.6) traverses 'h' and so in the TRIE the 'h' branch in selected (Figure 6.7).traversing 'o' in the inputsentence. At this point in the TRIE(Figure 6.9), the current position is Figure 6.9 - TRIE after 'o'a node that contains the meaning for "who". Because the next character in the input stringis a delimiter, the first prefix for the sentence is taken to be "Who". If "Who earns"happened to be in the inverted index then processing would continue and there would betwo different choices for the first prefix of the sentence. The tokenizer produces allalternatives which are shown with their meanings in Figure 6.10 (in this case there is onlyone alternative).116Figure 6.7 - TRIE after 'h't • (What)a--"'"----h a/ e •a^aay Y V 3 ••(Why)se• • (Whose)•17.^)y \::' I., (Why)• (Who)a t a (What)h Ve ^r• •• ea (Where)117Token Interpretation Alternatives"WHO" • questionWord"EARNS""OVER" ••rangeMarker(compare(>))preposition(over)"THE" • article(definite)"AVERAGE" • groupFunctionModifier("AVG")"SALARY" • attribute"OF" • preposition(of)"AN" • article(indefinite)"EMPLOYEE" • word not in index is delimited by spaces"WORKING""IN" • preposition(in)"RESEARCH" • node(location(DEPT,DNAME,00000250.0001.0004),value(1,raw(RESEARCH)),cost(other)).,.„Figure 6.10 - Tokens of the SentenceFigure 6.10 presents the only tokenization that is produced. Some information about theinterpretation of words is associated with the tokens at this point. This information isderived from the lexicon entry. Each alternative interpretation in the table is marked by abullet. The meanings listed in the table will be briefly described. The word "Who" ismarked as a questionWord which tells the system that the referents of the word are to belisted in the response. "Earns" has no interpretation at this point. The morpher was to beadded to the indexing process but this was not done and so morphing occurs later."Over" has two different interpretations. For one interpretation, "over" is merely a118preposition that marks a case of some verb. This is indicated by preposition(over) in themeaning. For the other interpretation, "over" marks a range of values. In this case, therange is salaries greater than the average salary of an employee working in research."Over", "more than", "under" and "less than" are treated as markers for ranges of values. Inthe lexicon, they are marked as rangeMarkers/l. The compare/1 argument contains the typeof comparison that is to be used. For "over" the comparison is greater than (>)."The" and later "an" are marked as articles. This is part of the domain independentknowledge of the system. "Average" is one of a number of group function words whichincludes "total", "highest", "lowest" and "how many". Group function words correspond tofunctions performed on sets of values. The group functions that are interpreted by thissystem correspond directly to the SQL group functions (AVERAGE, COUNT, MIN, MAX,and TOTAL). The lexicon marks these words with the groupFunctionModifier/1 predicate.The argument of the predicate is the name of the SQL function that is to be used to do thecalculations. In Figure 6.10, the word "average" is a group function word which iscalculated by the SQL AVG function."Of' is marked in the lexicon as a preposition. Prepositions, as discussed earlier, serve asmarkers for cases of case frames. "Employee" is a word that is not in the lexicon. Thesystem decides that "employee" is a word because it is delimited by spaces. For thissentence, the system later learns that "employee" is a noun which marks the subject casefor the case frame of "work" and marks the object frame for employees. The lexicon willbe updated to reflect this. "Working" is not in the lexicon directly but through morphing119the system determines that "working" marks a case frame. "In" is in the lexicon marked asa preposition.The last word, "research", is a word that is in a field of the database. For each field that thevalue appears in, there is a node/3 predicate in the lexicon entry for the word. In this case,"research" appears in only one position in the database and so there is only one node/3predicate in the lexicon entry of "research". The first term of the node/3 is the location/3term of the node. location/3 contains the table, column and row address of the position thatcontains the word "research", ie - location(TABLE, COLUMN, ROW_ADDRESS 12). Thesecond term is the value/2 term. The value/2 term contains information about the value -the data type and the actual data value, ie - value( Type, Value ). There are two options forthe data value - raw(RawValue) where RawValue is the data in the database, or null whichmarks a null value. It is possible that through morphing or spell checking" that the wordin the sentence would not be the same as the RawValue in the node/3 predicate.6.1.2 ParsingParsing breaks the sentence up into phrases and produces restrictions on the structure of thesentence. The parser (process b of 3.3) is implemented using definite clause grammars"(DCG). A description of definite clause grammars can be found in PERWARR80, and12 - Row address is determined by ORACLE13 - Not Implemented14 - Listed in appendix B120details on how to implement DCG based parsers can be found in ALLEN87. The followingfigures (Figure 6.11, Figure 6.12, Figure 6.13 and Figure 6.14) illustrate four differentparses that could be produced if only syntactic information is used. Semantic information isused to reject non-meaningful parses and so there is only one parse that will be acceptedfor interpretation 15 . Note Figure 6.13 and Figure 6.14 which show "the average salary" asbeing associated with "employee" as an attribute. This is the result of the semanticgrammar productions which were described in section 4.2.1.7.(Who) earns(over (the average salary)) (of ((an employee) working)) (in research)?Figure 6.11 - Possible Sentence StructureAdr'l(WC)earns (over (the average salary)) (of ((an employee) working (in research))?Figure 6.12 - Possible Syntactic StructureAttribute(Who)earns (over (the average salary) (of an employee) working)) (in research)?Figure 6.13 - Possible Syntactic Structure- Shown in Figure 6.14121Attribute(Who) earns(over (the average salary) (of ( an employee) working (in research)))?Figure 6.14 - Possible Syntactic StructureCase Frame Marker: verbPhrase(2,auxiliaries([]),verb("EARNS",[]))Case Marker Case Filler1 nounPluase(1,"WHO",[questionWord],[],[question])2 range("OVER",compare(>),nounPluase(3,"SALARY",[attribute],[groupFunctionModifier("AVG")],[definite]))Case Frame Marker: verbPhrase(5,auxiliaries(0),verb("WORKING",[]))Case Marker Case Filler1 nounPhrase(4,"EMPLOYEE",[],[],[indefinite])prep("IN") nounPhrase(6,"RESEARCH",[node(location(DEPT,DNAME,00000250.0001.0004),value(1,raw(RESEARCH)), cost(other))],[],[])Case Frame Marker: nounPhrase(4,"EMPLOYEE",[],[],[indefinite])Case Marker Case FillerAttribute nounPhrase(3,"SALARY",[attribute],[groupFunctionModifier("AVG")],[definite])Figure 6.15 - Cases of the Only Parse AcceptedFigure 6.15 presents detailed information on the parse that is finally accepted forinterpretation. In this table, there are threeverbPhrase( Position, Auxiliaries, Verb )frame markers. The first two markers are case^Figure 6.16 - verbPhrase/3frame markers which are represented byverbPhrase/3 predicates (Figure 6.16). The first term (Position) of this predicate is a122number indicating the position of the case frame marker in the input sentence. The positionis not based upon the position of the word in the sequence of words but rather the positionof the phrase in the sequence of phrases. In the example, the first verb phrase is in thesecond position after "who" and the second verb phrase is in the fifth position after "who","earns", "over the average salary", and "of an employee". The second term of theverbPhrase/3 predicate is a list of the auxiliary verbs in the verb phrase. Currently thisinformation is only used for detecting passives. The last term in the verbPhrase/3 predicateis the main verb information. This is stored in the verb/2 predicate. The first term of thispredicate contains the verb found in the sentence and the second term is not used.The last frame marker in thenounPhrase(Position, Noun, Meanings, Adjectives, Quantifiers)table is the nounPhrase/5^Figure 6.17 - nounPhrase/5predicate (Figure 6.17). Thefirst term is the position of the phrase in the sentence as described earlier. The second termis the head noun as it appears in the sentence. The third term, Meanings, is a list ofdifferent interpretations of the noun. This list could indicate that the noun appears in thedatabase (using the node/3 predicate described), that the noun marks an object frame, orthat the noun marks a case of some frame. No interpretation of the word "employee" iscurrently known and so the list of interpretations for employee is empty. The fourth term ofnounPhrase/5, Adjectives, is a list of adjectives which were applied to the noun. The onlyadjectives allowed are group function modifiers such as "average", or "total". The last termcontains quantifier information. The only quantifiers currently allowed are definite,indefinite, or questionWord markers.123Figure 6.15 also contains information about the cases recognized for each of the frames.For the first case frame (for "earns"), there are two cases which are both marked byposition. The subject is represented by the nounPhrase/5 for "who". The object is filled bya range/3 predicate. The range/3 predicate is used to mark a range of values. In this case,the range of values are defined using a comparison ('>') to a value, the nounPhrase/3 forsalary. Range/3 phrases arise when there are rangeMarker/1 words in the sentence.The second case frame (for "working") also has two cases. The first case which is markedby position is filled by the nounPhrase/5 for "employee". The second case is marked by thepreposition "in". This case is filled by the nounPhrase/5 for "research". The last frame,which is marked by "employee", has only one case, "salary". Salary is an attribute of theobject frame which is marked by the word "employee". In this case, the nounPhrase/5 forsalary has information that indicates that the average of salary is to be used. Theinformation in Figure 6.15 is passed along to the semantic interpreter (process (c) of 3.3).6.1.3 Semantic AnalysisThe semantic analysis stage of processing (process c of 3.3) begins after parsing. Thissection describes how this analysis proceeds for questions. The analysis of declarativesentences was described earlier in chapter 5.For each parse that is produced, the system attempts an interpretation. Interpretationinvolves selecting frames for the frame markers and combining the results into a number ofEMP - RowACase Filler12•• "---ENAMESALARYFigure 6.18 - Case Frame for Earn124interrelated GMSTs. This section illustrate this process for the one successful interpretationof the example sentence.6.1.3.1 Applying the FramesFor the example, assume that the frames inFigure 6.18, Figure 6.19, and Figure 6.20 arein the dictionary. The case frame ofFigure 6.18 could have been produced usingthe sentence, "Smith earns 800". The caseframe of Figure 6.19 could have been produced with "Ford works in research". The framein Figure 6.20 could have been produced from two sentences such as "Smith's manager isFord" and "The salaryof smith is 800".Figure 6.19 - Case Frame for WorkThese frames are different from the frames which were illustrated in earlier chaptersbecause they contain the GMST data structure which is linked to the case information. Theearlier diagrams did not contain the GMST data structure because when the diagrams werepresented the GMSTs had not yet been defined. For these diagrams, the case fillers (nodesin the GMST) are marked by an arrow from the filler entry to the corresponding node. ThisEMP - RowA DEPT - RowDCase FillerENAMEDEPTH(EPTNONAME1 •►inCase Filler^Name^•Salary^Manager^•125Figure 6.20 - Object Frame for Employeeinformation providesthe means to connectthe components of thesentence to the GMST.The first step in theprocess is to analyze the sentence using the information in the frames. This involvesselecting a frame for each of the frame markers and then ensuring that the cases for theframe are compatible with the frame (Figure 6.21). Consider "earns". The systems knowsthat "earns" marks the "earn" case frame of Figure 6.18 so this frame is used forinterpretation. Next, the case fillers must be considered. According to the parse informationin the table of Figure 6.15, there are two case fillers for "earns". The first one is "who"which fills the subject case. According to the case frame information in Figure 6.18, thesubject, "Who", is mapped to the ENAME node of the database graph. "Who" is allowed torefer to any type of node so this case filler is allowed by this case frame (indicated inFigure 6.21 by an arrow from "Who" in the sentence to the ENAME column in theGMST). The next filler is for the object case. According to the parse information(Figure 6.15), the object of "earns" is a comparison marked by "over". The system in thiscase does some type checking in order to determine compatibility of the case and the filler.The type information used is merely the data type of the filler (text, number or date). Onlythings of the same type may be compared (eg - numbers to numbers). More sophisticatedtype checking can be applied also (described later on in this section for the case marker"working"). For the object case, there is no filler in the sentence. The filler is left126unspecified. Instead a constraint is used. In this case, the SALARY node which is theobject case, must be greater than the average salary". This is represented in Figure 6.21 bythe constraint SALARY > SALARY SUBQUERY. After determining the case fillers of thecase frame the case to filler table is discarded.Figure 6.21 - Selecting FramesThe application of the object frame for employees presents an interesting variation in theanalysis. The mapping of sentence elements to the case frame occurs as just described. Inthis case however, the system does not yet know that the word "employee" marks the caseframe for employees. The case frame for employees is selected using the knowledge that"salary" marks a case of the employee case frame. Additional support for this decision isthat "employee" is also filling the subject frame of "working". In order to do this,127"employee" must refer to something in the ENAME column of the EMP table. But this isexactly what the object name in the object frame for employee (Figure 6.20) must refer to.This is an example of the second form of type information. The first form is the data type(text, number, or date) and the second form is the table and column that the data occurs in.The third form was to be the object frame and the fourth form was the be cases filled butthese were not implemented. Arrows are used in Figure 6.21 to indicate that "salary" refersto SALARY column and "employee" refers to the ENAME column.There is another wrinkle in the analysis. Notice that the GMST for the frame in Figure 6.20contains more nodes than the object frame used in the interpretations for "employee" shownin Figure 6.21. The GMST used to interpret "the average salary of an employee"(Figure 6.21) is smaller than the GMST in the case frame (Figure 6.20). This happensbecause the system uses the GMST, (relative to the cases present in the sentence) of theGMST2 in the frame. The difference is that the GMST 2 is minimum relative to all of thecases mention in the case list for the frame. In Figure 6.20, there are three cases mentioned(the employee name, salary and manager) so GMST 2 must span nodes for all of thesevalue. In the sentence (Figure 6.21), however, only the employee name and salary arementioned so the system selects the subset of the GMST of the frame (GMST 2) that spansthe values mentioned in the sentence. This amounts to using the GMST of the GMST."Working" is the last case marker to be analyzed. The analysis occurs as before. Thesystem accesses the case frame information for work (Figure 6.19). The case to case fillertable is used to associate fillers from the parse table (Figure 6.15) with nodes in the GMST.128Again, the type information is used to verify that correct decisions are being made. Theinterpretation of "working" illustrates what occurs when the sentence contains phrases thatoccur in the database. For this example, "research" occurs in the DEPT table. To handlethis, a constraint is added to the constraint list (Figure 6.21). The constraint is that the node..■corresponding to the appropriate case (DNAME) in the GMST must be equal to the valuementioned in the sentence ("research"), ie - DNAME = "Research". A better approachwould be to constrain the case filler (DNAME) to be one of the nodes referred to by theword in the sentence ("research"). This would allow the system to function properly forwords spelt incorrectly or morphological variations of words.6.1.3.2 Combining the FramesAfter using frame information to interpret the components of the sentence, the systemcombines the interpretations into one interpretation consisting of a number of GMSTs andconstraints. There is one GMST for each group of GMSTs which have a node modified bya group function adjective. After determining how to group the GMSTs, the GMSTs ineach group are combined into one GMST.The first step of combining the GMSTs into one GMST is to form groups of GMSTs. Thegroups are determined based upon the words modified by group function adjectives (eg -"average", or "total"). For this example, there are two groups (Figure 6.22). One groupcontains the GMST and constraints for the "earns" case frame (main query group), and theother group contains the GMST and constraints for the "employee" case frame and the129Figure 6.22 - Query Groups"working" case frame (sub-query group).For each sub-query group there is a phrase with a group function adjective in the sentence.In this example, there is only one phrase with a group function adjective ("the averagesalary"). Corresponding to each phrase with a group function adjective ("the averagesalary") there is a node in a GMST, (the SALARY node in the EMP table - Figure 6.22).Other GMST are added to the group containing this node by considering reachability fromthis node. In this case nodes are neighbours if they are reachable from within the sameGMST or if there is a phrase in the sentence that refers to both nodes (the ENAME nodein the EMP-RowB table and the ENAME node in the EMP-RowC table are both referred toby the word "employee" and so one is reachable from the other). This definition of24Figure 6.24 -0000. 2 .%%,1^ 41/4„44.3Figure 6.25 -Union130reachability implies that the GMSTs for "employee" and for "working" are connected andso they belong to the sub-query group for the "the average salary" phrase (diagonal linesbox of Figure 6.22). All of the GMST that are not put in a sub-query group in this mannerare put in the main query group (wiggly lines in Figure 6.22).After the trees are divided into groups, the trees in each group are combined separately. Aspecial case of graph union is used to combine them. In2general, graph union is performed by combining the sets3Figure 6.23 of nodes of the graphs and the sets of edges of the graph. Graph 2- Graph 1 The graph in Figure 6.25 is the result of combining the graphs in Figure 6.23and Figure 6.24. In these graphs, each node is represented by a number.Nodes with the same number are the same nodes. Node 2 inFigure 6.23 is the same node as node 2 in Figure 6.24 and they arerepresented by node 2 in Figure 6.25. Union of the GMST occurs inthis manner with one exception.The exception is that the system must determine which nodes in the GMSTs should betreated as the same nodes. In the example of graph union, the labelling of the nodes wasused to immediately determine which nodes were the same. For GMSTs, the system mustdetermine which nodes should be the- same. This is done by considering the relationbetween the phrases in the sentence and the nodes in the GMSTs. Consider the phrase, "anemployee". This phrase refers to two different database graph nodes in two differentGMSTs (Figure 6.22). Because one phrase refers to both these database graph nodes, theEMP - RowAENAMESALARYFigure 6.26 - MainQuery GMSTENAME^EPTNODEPTNOSALARYEMP-RowE^DEPT-RowDFigure 6.27 - Sub-query GMST131system decides that they should become the same database graph node. In order to makethem the same database graph node, the symbolic row values which are used to distinguishto different occurrencesof a GMST node(RowB and RowC) arereplaced by onesymbolic row value (inthis case RowE). As a result the two GMSTnodes (EMP - RowB and EMP - RowC) become one. The result of combining the GMSTsfor the "average salary" sub-query group (Figure 6.22) is shown in Figure 6.27. TheEMP - RowB and EMP - RowC GMST nodes have been combined into one node markedby EMP - RowE 16 . This is the only way that nodes are combined during this analysis. Bycombining nodes in this manner, the system can determine that an interpretation is incorrectand the SQL that is generated can be more efficient. No work needs to be done to the mainquery group because there is only one GMST in it. The GMST for the main query isshown in Figure 6.26.6.1.3.3 Producing the SQL QueryAfter the groups are combined, the SQL query can be formulated. Each group is convertedseparately to an SQL query. Consider the sub-query group corresponding to the phrase, "theaverage salary of an employee working in research" (Figure 6.27). For each GMST node16 - Arbitrarily chosen unique value132(identified by a table and row) mentioned in the GMST there is a table alias in the SQL(see FROM list of Figure 6.28). For this case, there are two GMST nodes, EMP-RowE andDEPT-RowD. Each of the symbolic rows (RowE and RowD) are mapped to a uniquenumber. This number is appended to the table name to form an alias for the table. In thiscase RowE is mapped to zero and RowD is mapped to zero. The resulting aliases areDEPTO and EMPO.SELECT AVG(EMPO.SAL)FROM DEPT DEPTO, EMP EMPOWHERE DEPTO.DNAME = 'RESEARCH' AND DEPTO.DEPTNO = EMPO.DEPTNOFigure 6.28 - SQL for the Sub-queryDuring the analysis of the sentence, a number of constraints arose. For the sub-query group,there was only one constraint, DNAME = "Research" (Figure 6.22). This constraint isplaced in the WHERE list of the SQL. Notice that the alias corresponding to the correctGMST node is used to identify the DNAME column properly (Figure 6.28). The joinconditions are also put into the WHERE list of the SQL. Remember from chapter 5 that thejoin edges in the GMST represent the join condition of two tables. For this system, the joincondition is that the nodes connected by the "join" edge must have the same value. In theGMST for the sub-query (Figure 6.27), there is only one "join" edge which connects theDEPTNO column of the EMP table to the DEPTNO column of the DEPT table. In theSQL, the join condition is represented by the constraint thatDEPTO . DEPTNO = EMPO . DEPTNO. Notice that the correct table aliases have beenapplied.133The last component of the SQL query to describe is the SELECTION list. For sub-queries,the column(s) (SAL) that the function word modifies is placed in the SELECTION list. Forthis case, "average" modifies "salary" and so EMPO.SAL is placed in the SELECTION listwith the appropriate SQL function (Figure 6.28).The process of producing the SQL for the main query is essentially the same as for thesub-query. There is one exception. During the analysis of the sentence, a list of nodes thatare to be printed as an answer is produced (the list contains all words that are marked asquestionWords 17). In this case, the list only contains the node referred to by "Who". Thislist is used when producing the main query. All of the nodes in the list are put in theSELECTION list of the main query. As with the sub-query, the constraints and joinconditions are placed in the WHERE clause. For this main query, there is a comparisonthat references the sub-query. The SQL for the sub-query is inserted in the appropriateplace at this time. The final form of the SQL for the main query is shown in Figure 6.29.SELECT EMPO ENAMEFROM EMP EMPOWHERE EMPO.SAL >any ( SELECT AVG (EMPO . SAL)FROM DEPT DEPTO, EMP EMPOWHERE DEPTO .DNAME = 'RESEARCH' AND DEPTO . DEPTNO = EMPO .DEPTNO)Figure 6.29 - SQL for the Main QueryThe query is sent to Oracle for processing and the results are printed by the system.17 - see section 6.11346.2 Response GenerationThere is no sophisticated response generation. Tuples that satisfy the SQL command aremerely listed.6.3 Learning Word MeaningsWord meanings can be learned when the system is interpreting questions. This was shownin the example for the word "employee". There are other types of words that the systemcan learn during question answering. For the sentence, "Which employees work inResearch?", the system learns that "employee(s)" is an noun marking the subject case forthe "Work" case frame. After the question "Which employee's salary is 800", the systemknows that the object frame referenced in this sentence is marked by the noun "employee".Attribute names can be learnt as well. The system determines what the words refer toduring sentence analysis as described earlier. If the system did not know that the wordcould have such a referent then this information is added to the lexicon for use later.Extensions to the system based upon exploiting this type learning are presented in the finalchapter.Who works for 800?Who works for Ford?Figure 6.30 - PossibleAmbiguity1356.4 Handling AmbiguityType information is used by the system to resolve ambiguity. Currently type information isthe ORACLE data type (numbers, dates or text), and the table and column that the dataappears in. The object frames and the case markers were to be used as type information butthis was not developed. Type information is used to mark object frames and can be used toresolve ambiguity when syntactic and case markers do not.As an example of this, imagine that the works case framehas two cases marked by "for", one is a manager and theother is a salary. The type information can be used inFigure 6.30 to determine which case is appropriate. For thefirst sentence, 800 is a number. Only the salary case marked by "for" can be filled by anumber. For the second sentence, "Ford" is known to be in the ENAME column and to betext. There is only one case marked by the preposition "for" that allows such a filler. Thetype information has been used here to eliminate ambiguity. If the words "manager" and"salary" were known to mark the cases then these words could be used to eliminateambiguity (implemented for object frames but not for case frames).There are no more alternative interpretations.All alternatives have been listed.3 Interpretations. TheyAre:Option #1"58" refers to ACTUALPRICE in the ITEM tableOption #2"58" refers to ITEMTOT in the ITEM tableOption #3"58" refers to STDPRICE in the PRICE tableYou may select an option as a correct interpretation,ask for more options, or decide to stop this definitionFigure 6.31 - Asking for Input1366.5 Controlling the DialogueThe dialogue is maintained using a control structure patterned after an ATN. The dialoguemanager doesnot handleellipsis oranaphora. Itonly controlsthepresentationand selection of alternatives. In some situations, a fixed number of responses from the useris expected. For these, the system uses a pattern matching approach to analyze thesentences. This provides a more robust way of analyzing sentences when the number ofdifferent interpretations is limited. At the following point in the dialogue (Figure 6.31),pattern matching is used to interpret theuser's response. The pattern matcher willaccept a large number of sentences thatthe parser will not (Figure 6.32).Figure 6.32 - Selection Option #1gimme 1.1.of these choices the only good oneis 1.number 1.numbr 1no 1.l's the best.1376.6 SummaryThe chapter described the use of spanning trees during the question answering process bypresenting a detailed example. Tokenization of the question is performed taking advantageof the TRIE structure of the inverted index which contains the lexicon. The result ofparsing is a number of cases and associated fillers which are analyzed by the semanticinterpreter. Semantic analysis has two main stages. For the first stage, the spanning trees inthe case frames are accessed and related to phrases in the sentence. The second stage is tocombine the spanning trees. After the semantic analysis, the interpretation is converted toSQL and the results of the SQL query are presented to the user.Chapter 7Conclusion7.1 Contributions of this ThesisThis paper describes a method that can be used to obtain a higher degree of domainportability for natural language interfaces. Early natural language interfaces required adomain and natural language expert in order to be configured. Later systems increaseddomain portability by providing facilities that a DBA could use in order to configure thenatural language interface. The approach presented in this paper produces a system thatcould be almost entirely configured by a naive user (no knowledge of linguistics ordatabase management systems). This represents a significant increase in the portability ofnatural language interfaces. A number of benefits arise because each user configures thesystem for himself or herself.The first benefit is for the DBA. One can imagine that when the DBA configures theinterface, there is a great deal of work to be done. First, meetings must be held with all theusers to determine which words they will want to use. These words must be compiled anddefined in terms of the database. Problems will arise if different users have different138139interpretations of the same word. This will require compromise on the part of the users orthere will be words whose interpretation is ambiguous relative to the grammar of all theusers. After the system is configured by the DBA, new users will want to use new words.Then the DBA will have to combine these new words with the old and iron out anyconflicts. A number of these problems can be avoided when the users configure the systemfor themselves.Each user will have his or her own grammar. This will mean that words that are ambiguousrelative to everyone's grammar will not necessarily be ambiguous to a particular user'sgrammar. As a result, the user will not be asked to select from alternative interpretationswhen relative to the user's grammar there is only one interpretation. This will also increasethe processing speed of the system by reducing the size of the dictionaries. If the usersdiscover that they have not configured the system for a word that they want to use, thenconfiguration can be done immediately without having to wait for the DBA to get aroundto doing it. For the DBA, the main advantage is that very little time need be spent helpingthe users configure the systems. This can amount to a great reduction in work if youconsider that, for some applications, users are only allowed to access the database througha set of customized views. In this case, the NLI would have to be set up once for each ofthe users' different views of the database. This could be a time consuming processdepending on how different the views are and how much is transferrable between them.A program was written to demonstrate that the method of configuration described in thispaper is effective. The program was not developed to be a sophisticated natural language140interface. The system has a rudimentary question answering facility whose purpose was toshow that the system had, in fact, correctly configured itself. When looking at the programdemonstrations, one should not ask whether or not the program is a sophisticated naturallanguage interface but rather one should ask does the program adequately demonstrate thatthe approach described in this paper is effective. We believe so.Although the system was not developed to the point of being a sophisticated naturallanguage interface, it could serve as a basis for one. The remainder of this chapterdescribes enhancements that could be made to the system in order to produce a powerfulNLI. These enhancements include descriptions on improvements to the methods used toconfigure the system.7.2 Possible EnhancementsThe enhancements presented here are not described in great detail. The purpose is toprovide brief notes indicative of straightforward directions for improvements.7.2.1 Enhancements to Noun Phrase Interpretation7.2.1.1 AdjectivesThe system currently does not handle adjectives. This section describes a number of specialcases that could be added to the system.1417.2.1.1.1 Related Adjective - "red ford"Sometimes adjectives are nouns that refer to something related to the noun being modified.For "red Ford", red is the color of a Ford. The relation could be represented as a GMST inthe object frame for "ford". Alternatively, inference could be performed using the objectframes and case frames to find a connection between "red" and "ford" that already exists.For example, "red" could be the color attribute in the object frame for "Ford".7.2.1.1.2 Explicitly Defined - "Rich employees earn over 20000"Another type of adjective is one that is defined explicitly by the user. The approaches usedto handle other problems in the system could be used to handle this one. The first step aftergetting a sentence that is used to define an adjective, would be to produce the GMST forthe sentence. The adjective whose meaning is not known could be ignored. After theGMST is produced, the adjective ("rich") would be defined by noting that it ("rich")referred to the same database graph node that is referred to by the noun ("employee") itmodified. Later when the adjective is used in a sentence, the system could access theGMST associated with the adjective. This GMST would be combined with the GMST forthe head noun of the sentence using the GMST union 18 operation. For this union, the nodereferred to by the adjective in the adjective's GMST would be set to be the same node asthe node referred to by the head noun in the head noun's GMST. Thus, application of themeaning of the adjective would occur through graph union.18 - see section 6.1.3.21427.2.1.1.3 Anaphora - "part number A37"Anaphora is another form of expression employed by users that should be handled. Foranaphora, a noun that marks an object frame and a noun referring to something in thedatabase are listed one after the other. The first noun could be interpreted as a marker foran object frame (or a case of a case frame). The second noun could then be interpretedusing the marked frame.7.2.1.2 Semantic Grammar CategoriesIn this system, the only semantic categories that were used are attribute, and object. Thesystem's performance could be improved greatly if more semantic categories were used.Names is one example of a useful category. Sometimes objects have a number of names(first, middle or last name). Names can also be abbreviated (I.B.M.). Object can also havemore than one distinct name. In order to function effectively, a natural language systemmust be able to work with names. Another semantic category that is useful is units. Unitshave a hierarchy of different type of units. Examples of units include measurements(temperatures, distances, weights) and counts (currency). The TEAM system provides agood source for useful semantic categories. Once new categories are defined, the grammarcould be extended to recognize them.1437.2.1.3 PronounsThe system would be enhanced greatly by being able to handle pronouns and morecomplicated forms of anaphora.7.2.1.4 Words not in the DatabaseWords that are not in the database are not handled properly by the system. The systemshould be extended to handle this in order to provide intelligible feedback to questionsinvolving unknown words.7.2.1.5 Learning Object ClassAn object class is a semantically defined set of objects. This is commonly represented insystems using the isa relation. In order to handle a wide range of questions the systemshould be extended to cover isa relations. This section describes the different ways that theisa hierarchy can be implicitly represented in the database.7.2.1.5.1 Column MembershipCase fillers and objects must be represented by values that appear in the same columns. Forexample, for "Smith works in research", the subject is allowed to be any word in theENAME column of the EMP table. This works well for most cases. However, there areS.I.N. Name Jobl Job2 Job3989-776-090 Jones MGR776 PGR700334-987-909 Smith CLK223Figure 7.2 - Another Form of Classes144several ways of representing data in the database which this will not work for.Sometimes classes of objects are marked by constraints on other columns. For example, inFigure 7.1, the clerks are objects in the EMP table which have JOB = "Clerk". This isnot an unreasonable way to represent data but the system as it is set up will not handlethis.EMPEMPNO ENAME JOB MGR HIREDATE SAL DEPTNO7369 SMITH CLERK 7902 17-DEC-80 800 207876 ADAMS CLERK 7788 12-JAN-83 1100 207902 FORD ANALYST 7566 03-DEC-81 3000 20Figure 7.1 - Job Class7.2.1.5.2 Groups of Columns - (Job1, Job2, ... )Another way of representinggroups of objects is by havinga number of columns with thesame prefix and a differentnumber for a suffix. Forexamples one could imagine a table where the employees could have up to three jobs andthe different jobs would be listed in columns called JOB1, JOB2, and JOB3 (Figure 7.2).The program set up does not recognize groups such as these.1457.2.1.5.3 Through Joins and RestrictionAnother way of representing groups is by using table joins to restrict the values selected.This is closely related to the discussion in section 7.2.1.5.1 for the representation of clerks.In this case, a table join must be performed first before the value that defines the group canbe accessed.7.2.1.5.4 Information contained in file name or pathsFor some systems, filenames and directory paths are used to encode information which thesystem must access in order to function properly. For example, data for different yearscould be stored in different directories or filenames could be used to encode the name ofdifferent sites from which data is collected. Access to the directory paths and file names issometimes necessary.7.2.1.6 Plural NounsThe system does not handle plural nouns. Extending the system to handle them is relativelystraightforward since the morpher will provide information about whether or not a noun inplural.1467.2.2 Learning Grammatical StructuresAn interesting extension to the system would be to have it learn semantic grammar rules.The semantic grammar rule itself could be used as a marker for a case frame that thesystem learned. The meaning of the semantic grammar rule could be determined by usingthe spanning tree approach. The grammar could be extended to include the new semanticgrammar rule and the corresponding spanning tree.7.2.2.1 "Voltage across part is 29" instead of Attribute of Object is ValueThe system currently does not allow prepositional phrases (other than 'of' phrases) tomodify a noun directly. Adding them would be relatively straightforward. The object framecould be used to store information about prepositional phrases that are allowed to modifyeach object. The parser would have to be extended to allow such modifier structure to berecognized.7.2.3 Enhancements to Verb Phrase Interpretation7.2.3.1 Employer/EmployeeA simple improvement to the system would be to calculate employer and employee fromthe verb employ. The GMST from employ could be used and the word (employer oremployee) could be set to refer to one of the database graph nodes in the GMST. Then theLook out below.Bill picked up the book.Bill picked the book up.Figure 7.3 - Prepositionused as ParticlesGMST could be combined with the rest of GMSTs of the sentence as described earlier.1477.2.3.2 ParticlesSometimes verbs can be combined with a particle to yield averb with a new meaning. The role of particle is filled byprepositions. When used as particles, preposition do notmark cases of the verb but instead are part of the verb.Figure 7.3 contains examples of sentences where the preposition is used as a particle.Notice that the particle immediately follows the verb or the object of the verb. The systemdoes not currently handle particles.7.2.4 Enhancements of the ParserThe parser does not take advantage of the fact that the system is based on case frames. Aparser that was constructed to analyze sentences using the case frames directly might bemore robust and flexible (HAYMOU80, and TAYROS75).7.2.5 Enhancements Using LearningIt is possible to set the system up so that is can learn the meaning of words from sentencesthat do not directly reference the database. For example, the system could learn themeaning of "earns" from the sentence "Smith's manager earns 3000". This can be done148because the algorithms for calculating GMSTs expect a list of nodes that are referred to bythe values in the sentence. In order to handle these type of sentences, the step thatcalculates the mapping of the values in the sentence to the database graph nodes must beextended.7.2.5.1 Correcting things that were learned incorrectlyThere is currently no way to correct things that have been learned incorrectly. Handling thiselegantly is a non-trivial problem.7.2.6 Enhancements Using Frames7.2.6.1 Meta-Questions - "What is in the database"For meta-questions such as "What is in the database?" or "Tell me about employees", theframes that the system has could be used to provide a reasonable answer.7.2.6.2 Report FramesThe system currently responds to questions. This is not enough. A facility for dealing withreports should be added. Frames could be used to keep track of different types of reportsand different instances of reports created by the user. The report frames could be used toanswer meta-question or to help the system understand how the user conceptualizes the149domain. The second use would be interesting to investigate.7.2.7 Enhancements to the Database Interface7.2.7.1 What if underlying database structures are changed?One problem, not dealt with here, is what happens when the underlying database structuresare changed (eg - new tables, new columns, deletion of tables). Is there a way to automatethe conversion of the system?7.2.8 InferencesAdding inference to the system would enhance the performance of the system in a numberof ways. This section describes a few.7.2.8.1 Filling in the Blanks - "average salary in research"Sometime when people speak they leave information out of the sentence when they believeit can be reasonably inferred. For example, one might ask for "the average salary inresearch" and expect the system to infer that one is talking about "the average salary of anemployee who works in research". This could be performed by using the frames that thesystem has to determine connections among the frames (or cases) that are mentioned.1507.2.8.2 EllipsisIt was hoped that by having many types of information in the system and by usingsemantic grammars that the system would be able to handle ellipsis as effectively assemantic grammars of the 1970's. Unfortunately, no work was done on ellipsis in thissystem.7.3 SummaryThe goal of this thesis is to provide a means to increase the portability of natural languageinterfaces. This has been achieved by using the spanning tree approach. A system wasimplemented to demonstrate the effectiveness of this configuration method. The systemallows a naive end user to configure the interface in a simple and straightforward way.There is much room left for development of this approach to configuration as well as to theprogram itself.151BibliographyALLEN87 Allen, J., Natural language understanding, The Benjamin/Cummings PublishingCompany, Inc., Menlo Park, California 1987.BERWICK85 Berwick, R, The Acquisition of Syntactic Knowledge, MIT Press,Cambridge, MA, 1985BOOTH83 Booth, D. A., Designing a Portable Natural Language Database Interface,M.Sc. Thesis, University of British Columbia, Vancouver, 1983.BRADLEY82 Bradley, J., File and data base techniques, CBS College Publishing, NewYork, NY, 1982.BROWSE77 Roger Browse, A Knowledge Identification Phase of Natural LanguageAnalysis, M.Sc. Thesis, University of British Columbia, Vancouver, 1977.BUBR79 Burton, R. R. and Brown, J. S., "Toward a Natural-Language Capability forComputer-Assisted Instruction," reprinted in Readings in Natural Language Processing,editors Grosz, B. J., Sparck Jones, K., and Webber, B. L., Morgan Kaufmann Publishers,1986 pp 605-626.CARHAY83 Carbonell, J. G., and Hayes, P. J., "Recovery Strategies for ParsingExtragrammatical Language," American Journal of Computational Linguistics, Vol 9, No 3-4, 1983.COLBY71 Colby, K., Weber, S., and Hilf, F., "Artificial Paranoia,", Artif. Intell 2, 1, pp 1-25 (1971)DATE86 Date, C.J., An introduction to database systems, Addison-Wesley PublishingCompany, Inc., Reading, MA, 1986.FILLMORE71 Fillmore, C., "Types of lexical information," in Semantics: AnInterdisciplinary Reader, Steinber and Jakobovits, eds., Cambridge University Press,London, 1971152HARRIS77 Harris, L. R., "User oriented data base query with the ROBOT naturallanguage query system," Int. J. Man-Machine Studies 9, 1977, pp 697-713HARRIS84 Harris, L. R., "Experience with INTELLECT," The Al Magazine, Vol. V, No.2, 1984HAYMOU80 Hayes, P.J., and Mouradian, G.V., "Flexible Parsing.", in Proceedings of 18'Annual Meeting of the Assoc. for Comput. Ling, Philadelphia, June 1980, pp 97-103.HOBBS78 Hobbs, J. R., "Resolving Pronoun References," in Readings in NaturalLanguage Processing, editors Grosz, B. J., Sparck Jones, K., and Webber, B. L., MorganKaufmann Publishers, Inc. 1986, pp 339-352KAPLAN84 Kaplan, S. J., "Designing a Portable Natural Language Database QuerySystem," ACM Transactions on Database Systems, Vol 9, No. 1, March 1984, Pages 1-19.LEHMAN89 Lehman, J. F., Adaptive Parsing: Self-extending Natural Language Interfaces,Kluwer Academic Publishers, MA, 1989LIFER77 Hendrix, G., Sacerdoti, E., Sagalowicz, D., and Slocam, J., "Developing aNatural Language Interface to Complex Data," ACM Trans. Database Sys, #(2), 1978, pp105-147MAP83 Martin, P., Appelt, D., and Pereira, F., "Transportability and Generality in aNatural-Language Interface System," in Proceedings of the Eighth International JointConference on Artificial Intelligence, Karlsruhe, West Germany, Los Altos:WilliamKaufmann Inc., 1983, pp 573-581.MARCUS80 Marcus, M., A Theory of Syntactic Recognition for Natural Language, MITPress, Cambridge, MA, 1980PERWARR80 Pereira, F., Warren, D., "Definite Clause Grammars for LanguageAnalysis", Artificial Intelligence 13, North-Holland Publishing Company, 1980153PG87 Perrault, C. R., and Grosz, B. J., "Natural Language Interfaces" in ExploringArtificial Intelligence: Survey Talks from the National Conferences on ArtificialIntelligence, editor, Shrobe, H. E., Morgan Kaufmann Publishers, 1987, pp 133-172PLANES76 Waltz, D. L., Finin, T., Green, F., Conrad, F., Goodman, B., and Hadden, G.,"The Planes System: Natural Language Access to a Large Data Base,", Technical Report T-34, University of Illinois, Urbana Illinois, November 1976SEDGE90 Sedgewick, R., Algorithms in C, Addison-Wesley Publishing Company, Inc.,Reading, MA, 1990TARJAN83 Tarjan, R. E., Data Structures and Network Algorithms, Society for Industrialand Applied Mathematics, Philadelphia, PA, 1983.TAYROS75 Taylor, B. H., and Rosenberg, R. S., "A Case-Driven Parser for NaturalLanguage", American Journal for Computational Linguistics, AJCL Microfiche 31.THOMP85 Thompson, B. H., and Thompson, F. B., "ASK is Transportable in Half aDozen Ways," ACM Trans. Off. Inf. Syst, 3, 2 (April 1985), pp 185-203WEIZEN66 Weizenbaum, J., "ELIZA - A Computer Program For the Study of NaturalLnaguage Communication Between Man and Machine," Communications of the ACM, Vol9, No 1, January 1966WEIZEN67 Weizenbaum, J., "Contextual Understanding by Computers," Communicationsof the ACM, Vol 10, No 8, August 1967WHITE85 White, S.J., A Portable Natural Language Database Query System, M.Sc.Thesis, University of British Columbia, Vancouver, 1985.WINOGRAD75 Winograd, T., Understanding Natural Language, Academic Press,NewYork, NY, 1972.WINOGRAD83 Winograd, T. Language as a Cognitive Process. Vol 1: Syntax., Addison-Wesley Reading, MA, 1983154WINSTON91 Winston, P. H., Artificial intelligence 3rd ed., Addison-Wesley Pub. Co.,Reading, MA, 1992WOODS70 Woods, W. A., "Transition Network Grammers for Natural LanguageAnalysis," Commun. ACM, 13, pp 591-602WOODS85 Woods, W. A., "Semantics and Quantification in Natural Language QuestionAnswering," reprinted in Readings in Natural Language Processing, editors Grosz, B. J.,Sparck Jones, K., and Webber, B. L., Morgan Kaufmann Publishers, 1985.Appendices155A Relational Database TerminologyThis appendix briefly describes some aspects of relational database theory. For a detaileddiscussion see DATE86."A relational database is a database that is perceived by its users as a collection of tables(and nothing but tables)" 19 . A table is a data structure made up of columns each of whichhas a name. A table also contains a number of rows of data. Two tables are shown inFigure A1.1.DEPTDEPTNO DNAME LOC10 ACCOUNTING NEW YORK20 RESEARCH DALLASEMPEMPNO ENAME JOB MGR HIREDATE SAL DEPTNO7369 SMITH CLERK 7902 17-DEC-80 800 207876 ADAMS CLERK 7788 12-JAN-83 1100 207902 FORD ANALYST 7566 03-DEC-81 3000 20Figure A1.1 - Oracle Sample Database15619 - CODD86, page 96157The department table contains information about departments. It has three columns -DEPTNO, DNAME, and LOC. A value that uniquely identifies each department is storedin the DEPTNO column. The name of the department is contained in the DNAME columnand the city that the department is located in is stored in the LOC column. Each rowcontains information describing a single department.The employee table contains information about each employee. It has eight columns whichare called EMPNO, ENAME, JOB, MGR, HIREDATE, SAL, and DEPTNO. As with thedepartment table, there is a column (EMPNO) which contains values that uniquely identifyeach employee. The name of each employee is stored in the ENAME columns. Theemployee's job description is in the JOB column. The MGR column contains the EMPNOof the manager of the employee. The HIREDATE, and SAL columns contain the date ofhiring, and salary of the employee, respectively. The last column, DEPTNO, contains thedepartment number of the employee. Each row in the employee table contains informationabout one employee.Under the relational model, information is not only derived directly from each table butalso from the relationships that exists among tables. Consider the employee table. There isa column that contains the department number of the employee's department (DEPTNO)but the employee table does not contain the department name. The name can be accessedby looking in the department table at the row with the corresponding department number.For example, the first employee, SMITH, is in department number 20. By looking updepartment number, 20 in the DEPT table, the department name can be found, ie -158RESEARCH. This approach of connecting rows in different tables by matching columnsvalues is a common method of accessing information in relational databases. This methodof connecting tables is called a (natural) join.Key columns are important in order to join tables effectively. The key of a table is acolumn or number of columns that are guaranteed to contain a unique value or combinationof values for each row in a table. For example, the EMPNO column of the employee tableis a key. Note that the relational model does not require that each table have a key. When acolumn of a table can contain only values that are in the key of another table than thiscolumn is called a foreign key. For example, the DEPTNO column of the employee table isa foreign key of the employee table because all of the values in the column are in theDEPTNO key column of the department table.A number of other important concepts associated with the relational database model can befound in DATE86.B GrammarThis appendix contains a listing of the grammar taken directly from the source code. Thegrammar is implemented using the DCG feature of Quintus Prolog.sentence(parseInfo(PIIn,PIOut), CaseMappings) -->noiseWords, (PI1^PIIn, CM1^CM1T-CM1T),present(parseInfo(PI1,PI2), CM2 ),parseInfo_send( position, PI2, SubjPosition, PI3 ),parselnfo_send( position, PI3, VPPosition, PI4 ),parselnfo_send( mood, PI4, question, PI5 )),unmarkedCase(parseInfo(PI5,PI6),Case,CM3),terminator(parseInfo(PI6,PI7)),% fake a what is <np> questionVerbPhrase =verbPhrase(VPPosition, auxilliaries(M), verb( "BE", [] )),parselnfo_send( marker(VPPosition), PI7, Markerl, PI8 ),CM4 = (noun(SubjPosition,"WHAT",[questionWord],[],[question])-(Markerl-VerbPhrase)1T41-T4,case_object( Case, Object ),parselnfo_send( marker(VPPosition), PI8, Marker2, PI9 ),parselnfo_send( mainVerb, PI9, VerbPhrase, PIOut ),CM5 = [Object-(Marker2-VerbPhrase)IT5]-T5,diffList_appends( [CM1,CM2,CM3,CM4,CM5], CaseMappings )sentence(parselnfo(PIIn,PIOut), H-T) -->noiseWords,(PI1 = PIIn),unmarkedCase(parseInfo(PI1, PI2), Case, LO),^% What does questions(parselnfo_send(level(carry), PI2, Case, PI3)),auxilliary(parseInfo(PI3,PI4)),parselnfo_send( mood, PI4, question, PI5 ),parseInfo_send( mainVerbDefined, PI5, yes, PI6 )},unmarkedCase(parseInfo(PI6,PI7), Subject, L1),vp(parseInfo(PI7,PI8), VerbPhrase)parselnfo_send( level(takeCarry), PI3, Subject, P14 ),Ll = L1T-L1T),vp(parseInfo(PI4,PI8), VerbPhrase)verbPhrase_position( VerbPhrase, VPPos ),parselnfo_get( voice(VPPos), PI8, Voice ),Voice = passive-> parselnfo_send( marker(VPPos), PI8,^PI10 ); % Skip SubjectVoice = possiblePassive-> (parselnfo_send( voice( VPPos ), PI8, passive, PI9 ),parselnfo_send( marker(VPPos), PI9,^PI10 ); % Skip SubjectPI10 = PI8);PI10 = PI8) ,parselnfo_send( marker(VPPos), PI10, Marker, PIll ),case_object( Subject, SObject ),L2 = [SObject-(Marker-VerbPhrase)1L2T]-L2T159),unmarkedObjects(parseInfo(PI11,PI12), VerbPhrase, L3 ),markedObjects(parseInfo(PI12,PI13), VerbPhrase, L4 ),terminator(parseInfo(PI13,PI14)),parselnfo_send( level(takeCarry), PI14, Carry, PI15 )-> (verbPhrase_position( VerbPhrase, VPPOS ),parselnfo_send( marker(VPPos), PI15, ObjMarker, PI16 ),verbPhrase_verb( VerbPhrase, Verb ),(Verb="BE"• Verb="HAVE"; Verb="DO")-> ObjMarker < 3;true),case object( Carry, CarryObject ),L5 = [CarryObject-(ObjMarker-VerbPhrase)IL5T]-L5T);L5 = L5T-L5T, P116 = PI14),diffList_appends( (LO, Ll, L2, L3, L4, L5], H -T ),parseInfo_send( mainVerb, PI16, VerbPhrase, PI17 ),PIOut = PI17terminator( parselnfo(PIIn,PIOut) ) -->[" " -_ -_l, I, {PIOut = PIIn}{parselnfo_send( mood, PIIn, question, PIOut )}.auxilliary(parseInfo(PIIn,PIOut)) --> MODAL [_Modal-ModalAlts-_],memberchk( auxilliary(modal,_,_,_), ModalAlts ),parseInfo_send( auxilliary(ModalAlts), PIIn, PIOut )1^ HAVE ^[_Have-HaveAlts-_],memberchk( auxilliary(have,^tense(_HaveTense)), HaveAlts ),parselnfo_send( auxilliary(HaveAlts), PIIn, PIOut )^ BE 1 ^[_-BelAlts-_],memberchk( auxilliary(be,tense(_BelTense)), BelAlts ),parselnfo_send( level(up(be)), PIIn, PI1 ),parselnfo_send( auxilliary(BelAlts), PI1, PIOut )},DO[_-DoAlts-_],memberchk( auxilliary(do,^tense(_DoTense)), DoAlts ),parseInfo_send( auxilliary(DoAlts), PIIn, PIOut )vp(parseInfo(PIIn,PIOut), verbPhrase(Position, auxilliaries(Auxs), verb( Verb, VerbInfo )) )MODAL[_Modal-ModalAlts-_],{ memberchk( auxilliary(modal,^_), ModalAlts ),parselnfo_send( auxilliary(ModalAlts), PIIn, PI1 )}[], (PI1 = PIIn)1,^ HAVE(_Have-HaveAlts-_],memberchk( auxilliary(have,^tense(_HaveTense)), HaveAlts ),parselnfo_send( auxilliary(HaveAlts), PI1, P12 )160[], (P12 = PI1)BE 1[_-BelAlts-_],memberchk( auxilliary(be,^tense(_BelTense)), BelAlts ),parseInfo_send(level(up(be)), PI2, PI3),parselnfo_send( auxilliary(BelAlts), PI3, PI4 )}[],(PI4=PI2}),BE 2[_-Be2Alts-_],memberchk( auxilliary(be,^tense(_Be2Tense)), Be2Alts ),parselnfo_send(level(up(be)), PI4, PI5),parselnfo_send( auxilliary(Be2Alts), PI5, PI6 )(],{PI8=PI4}),verb(Verb, VerbInfo),{parselnfo_send( position, P16, Position, PI7 ),parselnfo_get( level(be), PI7, BeCount )-> true; BeCount = 0parselnfo_get( auxilliaries, PI7, Auxs ),BeCount > 0-> (BeCount = 2-> parselnfo_send( voice(Position), PI7, passive, P18 )morph_irregular( Verb, [_Root-MorphlnfolTail] )-> truemorph_roots( Verb, [_Root-MorphInfolTaill )Tail =member( tense(Tenses), Morphlnfo )memberchk( pastpart, Tenses )-> parseInfo_send( voice(Position), PI7, passive, PI8 );P18 = PI7);parselnfo_send( voice(Position), PI7, possiblePassive, PI8 ));PI8 = PI7), % Example sentences do not need the main verb defined but% questions doparselnfo_get( mainVerbDefined, P18, _ )-> (Verb = "BE"-> Roots = ["BE"-[]];Verb = "HAVE'-> Roots = ["HAVE"-(]];Verb = "DO"-> Roots = ["DO"-[]];r_get( caseFrameDictionary, entry( Verb ), _ )-> Roots^[Verb-[]]:morph_irregular( Verb, Roots ),someChk( Root-_ in Roots,r_get( caseFrameDictionary, entry( Root ), _ ) )-> true;morph_roots( Verb, Roots ),someChk( Root-_ in Roots,r_get( caseFrameDictionary, entry( Root ), _ ) )-> true161);true),% some simple tense checking stuff for the main verbAuxs =parseInfo_get(^level(embedded),^PI8,^_ ),^r_get( caseFrameDictionary,^entry(^Verb ), _ )-> Roots^=^[Verb-[]];morph_irregular( Verb, Roots ),someChk( Root-_ in Roots,r_get( caseFrameDictionary,^entry( Root ), _ )^)-> true;morph_roots( Verb, Roots ),someChk( Root-_ in Roots,r_get( caseFrameDictionary,^entry( Root ), _ )^)-> true-> (mapList( _-Morphlnfo in Roots,memberchk( tense(Tenses), MorphInfo ),(member( prespart, Tenses );member( pastpart, Tenses )))^)-> fail;true);true),% For Reduced Relative ClausesP19 = PI8),PIOut = PI9).objects(parselnfo(PIIn,PIOut), VerbPhrase, CaseMappings) -->object(parseInfo(PIIn,PI1), Case, CMO),verbPhrase_position( VerbPhrase, VPos ),case_type( Case, marked )-> (PI2 = PI1,case_marker( Case, Markerl ),parselnfo_get( voice(VPos), PI1, passive ),Markerl = prep("BY")-> Marker = 1;Marker = Markerl);parselnfo_send( marker(VPos), PI1, Marker, PI2 )),case_object( Case, CObject ),CM1 = [CObject-(Marker-VerbPhrase)ICM11]-CM1T,diffList_appends( [CMO, CM1, CM2), CaseMappings )),objects(parseInfo(PI2,P/Out), VerbPhrase, CM2);H. {CaseMappings = T-T, PIIn=PIOut}.markedObjects(parseInfo(PIIn,PIOut), VerbPhrase, CaseMappings) -->markedCase(parseInfo(PIIn,PI1), Case, CMO),verbPhrase_position( VerbPhrase, VPos ),P12 = PI1,case_marker( Case, Markerl ),parselnfo_get( voice(VPos), PI1, passive ),Markerl = prep("BY")-> Marker = 1;Marker = Markerl),case_object( Case, CObject ),CM1 = [CObject-(Marker-VerbPhrase)ICM1T]-CM1T,diffList_appends( [CMO, CM1, CM2], CaseMappings )),markedObjects(parseInfo(PI2,PIOut), VerbPhrase, CM2);[1, {CaseMappings = T-T, PIIn=PIOut}.unmarkedObjects(parseInfo(PIIn,PIOut), VerbPhrase, CaseMappings) -->unmarkedCase(parseInfo(PIIn,PI1), Case, CM0),162verbPhrase_position( VerbPhrase, VPos ),parseInfo_send( marker(VPos), PI1, Marker, PI2 ),verbPhrase_verb( VerbPhrase, Verb ),(Verb="BE"; Verb="HAVE"; Verb="DO")-> Marker < 3;true),case_object( Case, CObject ),CM1 = [CObject-(Marker-VerbPhrase)ICM1T]-CM1T,diffList_appends( [CMO, CM1, CM2], CaseMappings )}(case_object( Case, range(^_ ) )}-> [], {CM2 = T-T, PIOut=PI2};unmarkedObjects(parseInfo(PI2,PIOut), VerbPhrase, CM2));[], (CaseMappings = T-T, PIIn=PIOut).object(parseInfo(PIIn,PIOut), Case, CaseMappings) -->markedCase(parseInfo(PIIn,PIOut), Case, CaseMappings), !;unmarkedCase(parseInfo(PIIn,PIOut), Case, CaseMappings).unmarkedCase(parseInfo(PIIn,PIOut),case(unmarked, 'NA', Nounlnfo),CaseMappings )--> nounPhrase(parseInfo(PIIn,PIOut), Nounlnfo, CaseMappings);nounPhrase_range(parseInfo(PIIn,PIOut), Nounlnfo, CaseMappings).markedCase( parseInfo(PIIn,PIOut), Case, CaseMappings ) -->preposition(Preposition),nounPhrase(parseInfo(PIIn,PIOut), Nounlnfo, CaseMappings),Case = case(marked, prep(Preposition), Nounlnfo))^InounPhrase_range(parseInfo(PIIn,PIOut), Range, CaseMappings),Case = case(marked, prep(Preposition), Range))^InounPhrase(parseInfo(PIIn,PIOut), Nounlnfo, CaseMappings);nounPhrase_range(parseInfo(PIIn,PIOut), Range, CaseMappings)-> {fail};parseInfo_send( level(takeCarry), PIIn, case(unmarked, _Marker, Nounlnfo ),->Case = case(marked,prep(Preposition),NounInfo));PI1 = PIIn),PIOut = PI1,CaseMappings = T-T% Possessive = possessive then head noun must be possessive% Possessive = anything else for not possessivenounPhrase( parseInfo(PIIn,PIOut), HeadNounlnfo, CaseMappings ) -->questionWord( parseInfo(PIIn, PI1), HeadNounlnfo ),nounPhrase_qualifiers(parseInfo(PI1,PIOut),HeadNounInfo,CaseMappings)nounPhrase_other( parseInfo(PIIn, PI1), Nounlnfol, CM1 ),[possessiveMarker],nounPhrase possessive( parseInfo(PI1,PIOut), Nounlnfol, HeadNounlnfo, CM2 ),(diffList_appends( [CM1, CM2], CaseMappings )};163{HeadNounInfo = Nounlnfol, CaseMappings = CM1, PIOut = PI1}nounPhrase_qualifiers( parselnfo( PIIn, PIOut ), Nounlnfo, CaseMappings ) -->nounPhrase_relativeClause(parseInfo( PIIn, PIOut ), Nounlnfo, CaseMappings)% Followed by a marked Case (OF for attributes)markedCase( parseInfo(PIIn,PI1), ObjectCase, CM1 ),case_marker( ObjectCase, ()Marker ),OMarker = prep("OF"),case_noun( ObjectCase, ObjectNoun ),CM2 = [Nounlnfo-(OMarker-ObjectNoun)1CM2T]-CM2T,%nounPhrase(position(OPos),0Word,OMeanings))1CM2T]-CM2T,diffList_appends( [CM1, CM2], CaseMappings ),PIOut = PI11^% Just not followed by anything directly related[], {CaseMappings^T-T, PIOut=PIIn}.nounPhrase_relativeClause( parselnfo( PIIn, PIOut ), Nounlnfo, CaseMappings ) -->parselnfo_send( push, PIIn, PI1 ),parselnfo_send( level(carry), PI1, case(unmarked, 'NA', Nounlnfo), PI2 )),relativeIntro( parseInfo(PI2,PI3) )-> {true};[1, % not quite right because plural form counts as% a determinernoun_determiner( Nounlnfo, [_] ),% Unmarked relative clause must be for% things with determinersparselnfo_send( level embedded), PI2, yes, PI3 )%PI3 = PI2),relativeClause( parseInfo(PI3,PI4), CaseMappings ),parselnfo_send( pop, P14, PIOut )nounPhrase_other( parselnfo(PIIn,PIOut), Nounlnfo, CaseMappings ) -->determiner(parselnfo(PIIn, PI1), _Determiner, Modifiersl, Determinerinfo);(],{PI1=PIIn, Determinerinfo^[], Modifiersl = [])),( % ModifiersnounModifiers(parseInfo(PI1,PI2), Modifiers2, CM1 ),{append( Modifiersl, Modifiers2, Modifiers )}),parselnfo_send( position, PI2, Position, PI3 ),Nounlnfo = noun( Position, Noun, Meanings, Modifiers, Determinerinfo )},commonNoun( not_possessive, parseInfo(PI3,PI5), Noun, Meanings );parselnfo_get( and, PI3, AndCount ),AndCount > 0-> (attributes( parseInfo(PI3, PI4), Attributes, Meanings ),Noun = Attributes,parselnfo_send( down(and), PI4, PIS )}),nounPhrase_qualifiers( parselnfo( PI5, PIOut ), Nounlnfo, CM2 ),diffList_append( CM1, CM2, CaseMappings )nounNodifiers3( parseInfo(PI,PI), Modifiers, CM-CM ) -->164[_Word-Meanings-_Lex],member(groupFunctionModifier(Mod), Meanings)-> Modifiers = [groupFunctionModifier(Mod)](1, (Modifiers = []).nounModifiers( PI, Modifiers, CM-CM )andList( PI,(Parse,TheWord,TheMeaningsl-nounModifier(Parse,TheWord,TheMeanings),_Words, Modifiers )nounModifier( PI, _Word, Modifier ),{Modifiers = [Modifier]}[1, {PI = parselnfo(P,P), Modifiers = []).nounModifier( parselnfo(PI,PI), Word, Modifier )[Word-Meanings-_Lex],member(groupFunctionModifier(Mod), Meanings)-> Modifier = groupFunctionModifier(Mod)andList(parseInfo(PIIn,PIOut), Component, Words, Meanings) -->parselnfo_get( and, PIIn, AndCount ),AndCount > 0,parselnfo_send( down(and), PIIn, PI1 )),andList( parseInfo(PI1,PIOut), Component, Words-fl, Meanings-[], first ).andList(parseInfo( PIIn, PIOut ),Component,Comp,Mean,First ) -->PAND"-[] - (]], (\+ First = first)-> {copy_term( Component, CompForm ),[parselnfo( PIIn, PIOut ),Compl, Mean1]-CompCall^CompForm),CompCall,Comp = [Compl CT]-CT,Mean = [Meanl M1]-M1);-> (true) (true))-> {copy_term( Component, CompForm ),[parselnfo( PIIn, PI1 ),Compl, Mean1]-CompCall^CompForm),CompCall,diffList_append( (ComplIC1T]-C1T, Comp2, Comp ),diffList_append( [MeanlIM1T]-MiT, Mean2, Mean )),andList(parseInfo( PI1, PIOut ), Component, Comp2, Mean2, notFirst).% range = range( Marker, Compare, NounPhrase )nounPhrase_range( Parselnfo, range(Marker,Compare,HeadNoun), CaseMappings ) -->rangeMarker( Marker, Compare ),nounPhrase( Parselnfo, HeadNoun, CaseMappings ).rangeMarker( Marker, Compare ) -->[Marker-WordMeanings-_LexInfo],memberchk( rangeMarker(Compare), WordMeanings )}nounPhrase_possessive( parseInfo(PIIn,PIOut), LastPossessiveNoun,HeadNoun, CaseMappings ) -->% PossessivesnounPhrase_other( parseInfo(PIIn,PI1), NounInfo, CM1 ),CM2 = [NounInfo-(possessive-LastPossessiveNoun)ICM2T]-CM2T,diffList_appends( [CM1, CM2, CM3], CaseMappings )/,[possessiveMarker]-> nounPhrase_possessive( parselnfo( PI1, PIOut 1,Nounlnfo, HeadNoun, CM3 );165166{NounInfo = noun( IPosition, INoun, IMeanings, IMods, IDeterminerinfo ),HeadNoun = noun( IPosition, INoun, IMeanings, IMods, (possessivelIDeterminerInfo]CM3 = CM3T-CM3T,PIOut = PI1determiner( parselnfo(PIIn,PIOut), Determiner, Modifiers, Info ) -->determiner_questionWord( parseInfo(PIIn,PI1), Determiner, Modifiers, Info )-> {parselnfo_send( mood, PI1, question, PIOut )};determiner_article( parselnfo(PIIn, PIOut), Determiner, Modifiers, Info ).determiner_article( parselnfo( PI, PI ), Word, (], Info ) -->[Word-_-_],atom_chars( Atom, Word ),article( Atom, Info )article( 'A', [indefinite] )•article( 'AN', [indefinite] ).article( 'THE', [definite] ).relativelntro(parselnfo(PI,PI)) -->[Word -_-_],atom_chars( Atom, Word ),relativeIntro( Atom )relativeIntro( 'WHO' ).relativelntro( 'WHICH' ).relativeIntro( 'THAT' ).determiner_questionWord( parselnfo(PIIn,PIOut), Word, Modifiers, [question] ) -->[Word-WordMeanings-_],member( determiner_questionWord(Modifiers), WordMeanings ),parselnfo_send( mood, Plin, question, PIOut )relativeClause(parseInfo(PIIn,PIOut), CaseMappings) -->unmarkedCase(parseInfo(PIIn,PI1), Subject, L1),vp(parseInfo(PI1,PI2), VerbPhrase){parselnfo_send( level(takeCarry), PIIn, Subject, PI1 ), Ll = L1T-L1T},vp(parseInfo(PI1,PI2), VerbPhrase)),verbPhrase_verbInfo(VerbPhrase,VPInfo),\+ member( auxilliary( , ^, ^), VPInfo )},verbPhrase_position( VerbPhrase, VPPos ),parselnfo_get( voice(VPPos), PI2, Voice ),P13 = PI2,Voice = passive-> parselnfo_send( marker(VPPos), PI3,^PI5 ); % Skip SubjectVoice = possiblePassive-> (parselnfo_send( voice( VPPos ), PI3, passive, PI4 ),parseInfo_send( marker(VPPos), PI4,^PI5 ); % Skip SubjectPI5 = PI2);P15 = PI2),parseInfo_send( marker(VPPos), PI5, Marker, PI6 ),case_object( Subject, SObject ),L2 = [SObject-(Marker-VerbPhrase)IL2T]-L2T),unmarkedObjects(parseInfo(PI6,PI7), VerbPhrase, L3),markedObjects(parseInfo(PI7,PI8), VerbPhrase, L4),parselnfo_send( level(takeCarry), PI8, Carry, PI9 )-> (verbPhrase_position( VerbPhrase, VPP0s ),parseInfo_send( marker(VPP0s), PI9, ObjMarker, PI10 ),case_object( Carry, CarryObject ),L5 = [CarryObject-(ObjMarker-VerbPhrase)1L5T]-L5T);L5 = L5T-L5T, PI10 = PI8diffList_appends( [L1, L2, L3, L4, L5], CaseMappings ),PIOut = PI10questionWord( parseInfo(PIIn,PIOut),noun( Position, Word, [questionWord], [], [question] ) ) -->[Word-WordMeanings-_LexInfo],parselnfo_send( position, PIIn, Position, PI1 ),memberchk( questionWord, WordMeanings )-> parselnfo_send( mood, PI1, question, PIOut )% Meaning = attributes( ["Word", "Word", "Word", ... ], OfObjects )attributes(PI, Attributes, attributes(Attributes, OfObjects)) -->attributesl( PI, Attributes-[], OfObjects-[], first ).attributesi(parselnfo( PIIn, PIOut ), Attributes, OfObjects, First ) -->([","- -_] -> (true); (["AND"-_-_] -> (fail); (true)))-> attribute( parselnfo( PIIn, PI1 ), Attributel, OfObjectsl),diffList_append( [Attributel A1T]-A1T, Attributes2, Attributes ),diffList_append( [OfObjectsl 01T]-01T, OfObjects2, OfObjects )},attributesl(parselnfo( PI1, PIOut ), Attributes2, OfObjects2, notFirst);("AND"-[]-[]], (\+ First = first)-> attribute( parselnfo( PIIn, PIOut ), Attribute, OfObjectsi),Attributes = [Attribute AT]-AT,OfObjects = [OfObjectsl O1]-01attribute( parselnfo( PIIn, PIIn ), Word, OfObjects) -->[Word-_-_],r_get( attributeToObjectFrame_Dictionary, entry(Word), OfObjectsl )-> true;OfObjectsl = []),morph_roots( Word, Roots )-> mapSome( Root-_ in Roots, OfObjects2 in OfObjectssl,r_get( attributeToObjectFrame_Dictionary, entry(Root), OfObjects2 ));OfObjectssl = []),OfObjects = [-1—],ord_union( [OfObjectsl 1 OfObjectssl], OfObjects )).commonNoun(Possessive, parseInfo(PI,PI), Word, WordMeanings) -->[Word-WordMeanings-LexInfo],Possessive = possessive-> memberchk( possessive, LexInfo );\+ memberchk( possessive, Lexlnfo )),memberchk( questionWord, WordMeanings )-> (member( questionWord, WordMeanings )-> fail;true;member( Alt, WordMeanings ),167functor( Alt, auxilliary, _ );functor( Alt, preposition, _ );Alt = groupFunctionModifier(_);Alt = determiner_questionWord(_);morph_roots( Word, Roots ),member( _Root-LexI, Roots ),member( prespart, LexI );member( pastpart, LexI ));^WordMeanings^[],\+ ( \+ ascii_isPunctuation(Word),atom_chars( Atom, Word ),^\+ Atom^'WHICH',\+ Atom = 'THAT',\+ Atom = 'MANY',\+ Atom = 'AND',\+ article( Atom, _ ),\+ member( preposition(_), WordMeanings ),\+ member( possessive, Lexlnfo ) )) -> fail;true),Word = [Chi_], \+ is_punct( Ch )% jan 12 93% january 12 93% ? 12th% year = 93 1993 none% month jan 1-12 january% day 1 1st% separated by -, /, "% order mmm dd yyyy^dd mmm yyyy%date( Parselnfo, Date-{] ) -->%[Word],verb(_Verb, _) --> preposition( _ ), !, (fail).verb(VerbOut, Info) -->[Verb-Info-Lexlnfo],\+ ascii_isPunctuation(Verb),\+ ascii_isNumber(Verb),atom_chars( Atom, Verb ),\+ relativelntro( Atom ),\+ determiner_questionWord( Atom ),\+ member( determiner_questionWord( _ ), Info ),\+ Atom = 'MANY',\+ Atom^'AND',\+ article( Atom, _ ),\+ member( preposition(_), Info ),\+ member( possessive, Lexlnfo )),Info = [], VerbOut = Verb, !;member( VerbInfo, Info ),\+ auxilliarY_Modal( VerbInfo ),auxilliary_root( VerbInfo, VerbOut ),% auxilliary( RootAtom, RootWord, AtomForm, PerNo, Tense )auxilliary_root(auxilliary(_RootAtom,RootWord,_Form,_PerNo,_Tense),RootWord ).auxilliary_modal( auxilliary(modal, _RoiotWord, _AtomForm, _Type) ).preposition( Preposition ) -->[Preposition-Meanings-_Lexlnfo],(member(preposition(_), Meanings)).sentence_yes -->[_-Meanings-_], (memberchk( yesWord(_), Meanings )}(_], sentence_yes.sentence_no -->[_-Meanings-_], (memberchk( noWord(_), Meanings )}168[_], sentence_no.parser_anything -->[_], !, parser_anything[ I .^% [DayName] Year^[ 1 - 1/] Month^[ I-1/] DayMonth Day [Year]Day [Month [Year]]% Today% Yesterday% Tommorrow% 1st Saturday in Month% Time Units Hfromlbeforelafter] Date% units = Month I Day 1 Year% Year = yyyy 1 yy% Month = mm 1 mmm 1 mmmmmmmm% Day = dd 1 dd_thparser date( Date ) -->yymmdd( Date ) 1 mmddyy( Date ) 1 ddmmyy( Date ).% [DayName] Year^[ 1-1/] Month^[ 1-1/] Day%^Month Day [Year]% Day [Month [Year]]datel( Date ) -->yymmdd( Date )mmddyy( Date )1 ddmmyy( Date ).yymmdd( date( Year, Month, Day ) ) -->year( Year ),separator( Sep ),month( Month ),separator( Sep ),day( Day ).mmddyy( date( Year, Month, Day ) ) -->month( Month ),separator( Sep ),day( Day ),separator( Sep ),year( Year )-> [];{Year=none})•ddmmyy( date( Year, Month, Day ) ) -->day( Day ),separator( Sep ),month( Month ),separator( Sep ),year( Year )-> [] ;{Year=none}separator( Sep ) -->[Sep],Sep =-> true;Sep = "/"-> true-> {true};spaces.spaces -->. . -> spaces; [].% A.D. or B.C.year( Year ) -->parser_number( Ascii, Number ),169mapList( A in Ascii, is_digit( A ) ), % integer testNumber = [_,_]-> Year is Number;Year is Number - 1900month( Month )^-->monthAbbrev( Month )->^{true);parser_number( Ascii, Month->mapList( A in Ascii,Month =< 12, Month >=monthAbbrev( Month )^-->^"JAN"^-> {Month = 1};"FEB"^->^{Month^2);"MAR"^-> {Month = 3);"APR"^-> {Month = 4);"MAY"^-> {Month = 5};"JUN"^-> {Month = 6);"JUL"^-> {Month^7);"AUG"^->^{Month = 8);"SEP"^-> {Month = 9);"OCT"^-> (Month = 10);"NOV"^-> {Month = 11};"DEC"^-> {Month = 12))is_digit(A)^),^% integer test1),([Char],{is_alpha(Char)} -> (fail); {true)).day( Day ) -->parser_number( Ascii, Day ),mapList( A in Ascii, is_digit(A) ),Day >= 0, Day =< 31},(["ST"-_-_] -> {true);^-> {true};^-> {true); M.dateVerify( date(_Year, Month, Day) ) .-monthDays( Month, DaysInMonth ),Day =< DayslnMonth.monthDays( 1, 31 ).monthDays( 2, 28 ).monthDays( 3, 31 ).monthDays( 4, 30 ).monthDays( 5, 31 ).monthDays( 6, 30 ).monthDays( 7, 31 ).monthDays( 8, 31 ).monthDays( 9, 30 ).monthDays( 10, 31 ).monthDays( 11, 30 ).monthDays( 12, 31 ).% show to me show me show% list for me list% give to me give me give% print for me print% display for me displaypresent(parseInfo(PI,PI),C-C ) -->(["LIST"-_-_]I["PRINT"-_-_]1["DISPLAY"-_-_]),(((["TO" -_-_];[]), ["ME" -_-_]); (1)% This structure derived from Steven John White - A Portable Natural% Language Database Query System (1980) pp 142% i want you to ....170noiseWords -->(["WOULD"-_-_] 1 ["COULD"-_-_] 1 PCAN"-_ -_]), [^YOU"-_-_]1 ([^WANT"-_-_]1[^WOULD"-_-_],["LIKE"-_-_]), ["TO"-_-_]1 []),noise_please,noise_please -->["PLEASE"-_-_], noise_please;noise_like;(PTELL" -_-_]1PLETfl-noise_tell;noise_mia;H.noise_like -->noise_tell -->(["ME"-_-_]1["US"-_-_]),noise_mid.noise_mid -->(PPLEASE" -_-_l1[ ^ KNOW" -_ -_]),noise_mid(PIF"-_-_];["WHETHER_____]), [][].171C Database ListingDEPTDEPTNO DNAME^LOC10 ACCOUNTING^NEW YORK20 RESEARCH DALLAS30 SALES^CHICAGO40 OPERATIONS^BOSTONEMPEMPNO ENAME JOB MGR^HIREDATE SAL COMM DEPTNO7369 SMITH CLERK 7902 17-DEC-80 800 207499 ALLEN SALESMAN 7698 20-FEB-81 1600 300 307521 WARD SALESMAN 7698 22-FEB-81 1250 500 307566 JONES MANAGER 7839 02-APR-81 2975 207654 MARTIN SALESMAN 7698 28-SEP-81 1250 1400 307698 BLAKE MANAGER 7839 01-MAY-81 2850 307782 CLARK MANAGER 7839 09-JUN-81 2450 107788 SCOTT ANALYST 7566 09-DEC-82 3000 207839 KING PRESIDENT 17-NOV-81 5000 107844 TURNER SALESMAN 7698 08-SEP-81 1500 0 307876 ADAMS CLERK 7788 12-JAN-83 1100 207900 JAMES CLERK 7698 03-DEC-81 950 307902 FORD ANALYST 7566 03-DEC-81 3000 207934 MILLER CLERK 7782 23-JAN-82 1300 10172ORDORDID ORDERDATE C CUSTID SHIPDATE TOTAL610 07-JAN-87 A 101 08-JAN-87 101.4611 11-JAN-87 B 102 11-JAN-87 45612 15-JAN-87 C 104 20-JAN-87 5860601 01-MAY-86 A 106 30-MAY-86 2.4602 05-JUN-86 B 102 20-JUN-86 56604 15-JUN-86 A 106 30-JUN-86 698605 14-JUL-86 A 106 30-JUL-86 8324606 14-JUL-86 A 100 30-JUL-86 3.4609 01-AUG-86 B 100 15-AUG-86 97.5607 18-JUL-86 C 104 18-JUL-86 5.6608 25-JUL-86 C 104 25-JUL-86 35.2603 05-JUN-86 102 05-JUN-86 224620 12-MAR-87 100 12-MAR-87 4450613 01-FEB-87 108 01-FEB-87 6400614 01-FEB-87 102 05-FEB-87 23940616 03-FEB-87 103 10-FEB-87 764619 22-FEB-87 104 04-FEB-87 1260617 05-FEB-87 105 03-MAR-87 46370615 01-FEB-87 107 06-FEB-87 710618 15-FEB-87 A 102 06-MAR-87 3510.5621 15-MAR-87 A 100 01-JAN-87 730610 07-JAN-87 A 101 08-JAN-87 101.4611 11-JAN-87 B 102 11-JAN-87 45612 15-JAN-87 C 104 20-JAN-87 5860601 01-MAY-86 A 106 30-MAY-86 2.4602 05-JUN-86 B 102 20-JUN-86 56604 15-JUN-86 A 106 30-JUN-86 698605 14-JUL-86 A 106 30-JUL-86 8324606 14-JUL-86 A 100 30-JUL-86 3.4609 01-AUG-86 B 100 15-AUG-86 97.5607 18-JUL-86 C 104 18-JUL-86 5.6608 25-JUL-86 C 104 25-JUL-86 35.2603 05-JUN-86 102 05-JUN-86 224620 12-MAR-87 100 12-MAR-87 4450613 01-FEB-87 108 01-FEB-87 6400614 01-FEB-87 102 05-FEB-87 23940616 03-FEB-87 103 10-FEB-87 764619 22-FEB-87 104 04-FEB-87 1260617 05-FEB-87 105 03-MAR-87 46370615 01-FEB-87 107 06-FEB-87 710618 15-FEB-87 A 102 06-MAR-87 3510.5621 15-MAR-87 A 100 01-JAN-87 730173SALGRADEGRADE LOSAL HISAL1 700 12002 1201 14003 1401 20004 2001 30005 3001 9999ITEMORDID ITEMID PRODID ACTUALPRICE QTY ITEMTOT610 3^100890 58 1 58611 1 100861 45 1 45612 1^100860 30 100 3000601 1 200376 2.4 1 2.4602 1 100870 2.8 20 56604 1^100890 58 3 174604 2^100861 42 2 84604 3^100860 44 10 440603 2^100860 56 4 224610 1^100860 35 1 35610 2^100870 2.8 3 8.4613 4 200376 2.2 200 440614 1^100860 35 444 15540614 2^100870 2.8 1000 2800612 2^100861 40.5 20 810612 3^101863 10 150 1500620 1 100860 35 10 350620 2 200376 2.4 1000 2400620 3^102130 3.4 500 1700613 1 100871 5.6 100 560613 2^101860 24 200 4800613 3 200380 4 150 600619 3^102130 3.4 100 340617 1 100860 35 50 1750617 2 100861 45 100 4500614 3 100871 5.6 1000 5600616 1 100861 45 10 450616 2 100870 2.8 50 140616 3^100890 58 2 116616 4 102130 3.4 10 34616 5 200376 2.4 10 24619 1 200380 4 100 400619 2 200376 2.4 100 240615 1 100861 45 4 180607 1 100871 5.6 1 5.6615 2 100870 2.8 100 280617 3^100870 2.8 500 1400617 4 100871 5.6 500 2800617 5 100890 58 500 29000617 6 101860 24 100 2400617 7^101863 12.5 200 2500617 8 102130 3.4 100 340617 9 200376 2.4 200 480617 10 200380 4 300 1200609 2 100870 2.5 5 12.5609 3 100890 50 1 50618 1 100860 35 23 805618 2 100861 45 11 50618 3 100870 45 10 450621 1 100861 45 10 450621 2 100870 2.8 100 280615 3 100871 5 50 250608 1 101860 24 1 24608 2 100871 5.6 2 11.2609 1 100861 35 1 35606 1 102130 3.4 1 3.4605 1 100861 45 100 4500605 2 100870 2.8 500 1400605 3 100890 58 5 290605 4 101860 24 50 1200605 5 101863 9 100 900605 6 102130 3.4 10 34612 4 100871 5.5 100 550619 4 100871 5.6 50 280174=============================================================================PRODUCT=============================================================================PRODID DESCRIP100860 ACE TENNIS RACKET I100861 ACE TENNIS RACKET II100870 ACE TENNIS BALLS-3 PACK100871 ACE TENNIS BALLS-6 PACK100890 ACE TENNIS NET101860 SP TENNIS RACKET101863 SP JUNIOR RACKET102130 RH: "GUIDE TO TENNIS"200376 SB ENERGY BAR-6 PACK200380 SB VITA SNACK-6 PACKPRICEPRODID STDPRICE MINPRICE STARTDATE ENDDATE100871 4.8 3.2 01-JAN-85 01-DEC-85100890 58 46.4 01-JAN-85100890 54 40.5 01-JUN-84 31-MAY-84100860 35 28 01-JUN-86100860 32 25.6 01-JAN-86 31-MAY-86100860 30 24 01-JAN-85 31-DEC-85100861 45 36 01-JUN-86100861 42 33.6 01-JAN-86 31-MAY-86100861 39 31.2 01-JAN-85 31-DEC-85100870 2.8 2.4 01-JAN-86100870 2.4 1.9 01-JAN-85 01-DEC-85100871 5.6 4.8 01-JAN-86101860 24 18 15-FEB-85101863 12.5 9.4 15-FEB-85102130 3.4 2.8 18-AUG-85200376 2.4 1.75 15-NOV-86200380 4 3.2 15-NOV-86175CUSTOMERCUSTID NAME ADDRESS CITY ST ZIP AREA PHONE REPID CREDITLIMIT100 JOCKSPORTS 345 VIEWRIDGE BELMONT CA 96711 415 598-6609 7844 5000101 TKB SPORT SHOP 490 BOLI RD. REDWOOD CITY CA 94061 415 368-1223 7521 10000102 VOLLYRITE 9722 HAMILTON BURLINGAME CA 95133 415 644-3341 7654 7000103 JUST TENNIS HILLVIEW MALL BURLINGAME CA 97544 415 677-9312 7521 3000104 EVERY MOUNTAIN 574 SURRY RD. CUPERTINO CA 93301 408 996-2323 7499 10000105 K + T SPORTS 3476 EL PASEO SANTA CLARA CA 91003 408 376-9966 7844 5000106 SHAPE UP 908 SEQUOIA PALO ALTO CA 94301 415 364-9777 7521 6000107 WOMENS SPORTS^ VALCO VILLAGE^SUNNYVALE CA 93301 408 967-4398 7499 10000108 NORTH WOODS HEALTH AND FITNESS SUPPLY CENTER 98 LONE PINE WAY ^HIBBING MN 55649 612 566-9123 7844 8000MVDIRDIRNO DIRNAMEDO1 STEVEN SPIELBERGD02 PENNY MARSHALLD03 SPIKE LEEMVSTARSTNO STNAMESO1 MADONNASO2 TOM HANKSS03 GEENA DAVISSO4 JEFF GOLDBLOOMS05 DENZEL WASHINGTONMVMOVIEMVNO MVNAMEMO1 JURASSIC PARKMO2 LEAGUE OF THEIR OWNM03 MALCOLM XMVSTARSINMVNO STNOMO2 SO1MO2 SO2MO2 S03MO1 SO4M03 S05MVDIRECTSMOVIENO DIRNOMO1^DO1MO2^002M03^DO3177D Database InterfaceThe interface of the Prolog part of the system to the C server is contained in one smallProlog module (where.pl). The interface is implemented in the form of four predicates.The first predicate is whereLocation/5 (Figure D.1) The purpose of this predicate is todetermine the database graph node at a particular table, row, and column position in thedatabase. The first term of the predicate (location/3) specifies the table, column and rowthat identifies the database graph node. The system accesses the database through ORACLEin order to determine the second term, (the node/3 predicate). This predicate is used whenthe system is producing the spanning trees to access nodes in the database graph that are inthe same row.whereLocation( +location(Table,Column,Row), ?node( Location, Value, cost(Cost) )-)Figure D.1 - whereLocation/2The second predicate, where_prefix/3, is used during tokenization of a sentence (seesection 6.1.1). The first term,where_prefix( String, Prefix-Alternatives, Suffix )String, is the list of ascii codesthat comprise the input string".^Figure D.2 - where_prefix/3The second and third terms are bound by the predicate. Prefix is a prefix of the string,20 - In Prolog "strings" are implemented as a list of ascii codes178179String. Alternatives is a list of the possible interpretations' of the string Prefix, andSuffix is the portion of String after Prefix is removed, ie - append( Prefix, Suffix, String ).The inverted index is used to implement this predicate.The final two predicates are used to send SQLoracleServer_send( Command ).commands to ORACLE and receive the results of^oracleServer_read( Results ).the SQL. These predicates are shown in Figure D.3. Figure D.3 - SQL Access PredicatesThe first predicate, oracleServer_send/1, is used to send an SQL command to ORACLE.Only three commands are currently supported, login(userid/password), logoff, andsql(SQL). The login/1 and logoff are used to log on and off of a database. sql/1 is used tosend an SQL command directly to the DBMS. SQL is a Prolog atom that is an SQLcommand. The results of the SQL command can be obtained using theoracleServer_read/1 predicate. The first term of this predicate is a list (possibly empty) oftuples that are returned by the SQL command.21 - see the Interpretation Alternatives column in Figure 6.10 for examplesE Test Runs180smith works for ford.EMPO.ENAME EMPLENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seemreasonable?yes.: smith works in research.EMPO.ENAME DEPTO.DNAMECLARK^ACCOUNTINGKING ACCOUNTINGMILLER^ACCOUNTINGSMITH RESEARCHTo configure the system for a newdatabase, the user (in bold) enterssentences that describe data in thedatabase. By using these sentences andaccessing the database the system candetermine the meaning of nouns and verbs.(Users tend to know a lot about some ofthe data in the database).Examples arepresented to provide feedbackDo these examples seem reasonable?I : yes.: smith is managed by ford.EMPO.ENAME EMPl.ENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seem reasonable?I : yes.: smith's salary is 800.EMPO.ENAME EMPO.SALALLEN^1600JONES 2975SMITH^800WARD 1250Do these examples seem reasonable?: yes.: the manager of smith is ford.EMPO.ENAME EMP1.ENAMEALLEN^BLAKEFORD JONESSCOTT^JONESWARD BLAKEDo these examples seem reasonable?: yes.: the salary of ford is 3000.EMPO.ENAME EMPO.SALALLEN^1600JONES 2975SMITH^800WARD 1250Do these examples seem reasonable?I : yes.181182I : smith earns 800.EMPO.ENAME EMPO.SALALLEN^1600JONES 2975SMITH^800WARD 1250Do these examples: yes.: what is smith's salary.EMPO.SAL800That's it. System configuration iscomplete (for now). Questions cannow be asked about the database.Note that questions can be asked assoon as the user has defined thewords that will appear in thequestion. After asking somequestions, more words can bedefined if desired.First an easy question to get warmed up.seem reasonable?: which person's salary is 800.EMPO.ENAMESMITHI : the salary of which person is 800.EMPO.ENAMESMITH: what is the salary of the person who manages the person who manages smith.EMPO.SAL2975: what is the salary of the person who manages the person managing smith.EMPO.SAL2975 183I : which person's manager's salary is 2975.Possessives and comparison.EMPl.ENAMESCOTTFORDI : who does the person managing scott manage.EMPl.ENAMESCOTTFORDI : which person's salary is over ford's salary.EMPl.ENAMEKINGI : who earns over what smith earns.EMPLENAME EMPO.SALALLEN 800WARD 800JONES 800MART IN 800BLAKE 800CLARK 800SCOTT 800KING 800TURNER 800ADAMS 800JAMES 800FORD 800MILLER 800184: who earns over smith's salary.EMPl.ENAMEALLENWARDJONESMARTINBLAKECLARKSCOTTKINGTURNERADAMSJAMESFORDMILLER: who earns over the money ford earns.EMPLENAMEKING: who is the person managing scott.EMP1.ENAMEJONES : who earns over an employee's average salary.Ft" such as average,totak highest, and lowest areptovided..EMPO.ENAMEJONESBLAKECLARKSCOTTKINGFORD185: who earns over an employee working in research's average salary.EmpO.ENAMEJONESBLAKECLARKSCOTTKINGFORD: who earns over the average salary of an employee working in research.EMpO.ENAMEJONESBLAKECLARKSCOTTKINGFORDI : what is the average salary of an employee working in research.AVG(EMPO.SAL)2175I : what is the lowest salary of the people who earn over the average salary of anemployee.miN(EMPO.SAL) OtayI adz& that the. response generation is veryander hut letipeillit generation is another thesis2450: list the name and salary of people earning over the average salary of an employee.r3s3: No Parses not implemented yet186:^list the name and salary of the people earning over the average salary of anemployee.EMPO.ENAME EMPO.SALJONES 2975BLAKE 2850CLARK 2450SCOTT 3000KING 5000FORD 3000I : how many people earn over the average salary of an employee.COUNT(EMPO.ENAME)6: can you list the salary and manager of employees working in research.r3s3: No Parses not implemented yetI : can you list the salary and manager of the employees working in researchEMPO.SAL EMPl.ENAME3000^JONES3000 JONES800^FORD2975 KING1100^SCOTTI : can you list the name salary and manager of the employees working in research.EMPO.ENAME EMPO.SAL EMPLENAMESCOTT^3000^JONESFORD 3000 JONESSMITH^800^FORDJONES 2975 KINGADAMS^1100^SCOTT: print the average salary of the employees working in research.AVG(EMPO.SAL)2175187: list the name and salary of the employees earning over 800.EMPO.ENAME EMPO.SALALLEN 1600WARD 1250JONES 2975MARTIN 1250BLAKE 2850CLARK 2450SCOTT 3000KING 5000TURNER 1500ADAMS 1100JAMES 950FORD 3000MILLER 1300: can you list the name manager and salary of the employees working in research.EMPO.ENAME EMPO.SAL EMPLENAMESCOTT^3000^JONESFORD 3000 JONESSMITH^800^FORDJONES 2975 KINGADAMS^1100^SCOTTI : who works in research.EMPO.ENAMESMITHADAMSFORDSCOTTJONES188Let's teach the system aword with acomplicated meaning.This one has ambiguityand requires 4 tablejoins. The user ispresented with a choiceof two meanings.: tkb sport shop paid 58 for ace tennis net.2 Interpretations. They Are:Option #1"58" refers to ACTUALPRICE in the ITEMtableOption #2"58" refers to ITEMTOT in the ITEMtableYou may select an option as a correctinterpretation, ask for more options, ordecide to stop this definitionI : i like number 1.[pickAnOption(1)]: what is the average price a customer has paid for acetennis net.AVG(ITEMO.ACTUALPRICE)56.6666666666666666666666667: who paid under 58 for ace tennis net.Let's try somequestions.CUSTOMERO.NAMEJOCKSPORTS: who has paid less than 58 for ace tennis net.CUSTOMERO.NAMEJOCKSPORTS: what did jocksports pay for ace tennis net.ITEMO.ACTUALPRICE50I : what is the lowest highest and average salary of employee working in research.r6s4: No interpretation not implemented189: what is the lowest highest and average salary of the employees working inresearch.MIN(EMPO.SAL),MAX(EMPO.SAL),AVG(EMPO.SAL)800^ 3000 2175I added another database about movies. Let's try using it for a while.: steven spielberg directed jurassic park.MVDIRO . DIRNAME^MVMOVIEO.MVNAMEPENNY MARSHALL^LEAGUE OF THEIR OWNSPIKE LEE^MALCOLM XSTEVEN SPIELBERG JURASSIC PARKDo these examples seem reasonable?: yes.I : who directed malcolm x.MVDIRO.DIRNAMESPIKE LEE: league of their own starred tom hanks.MVMOVIEO.MVNAMEJURASSIC PARKLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNMVSTARO.STNAMEJEFF GOLDBLOOMGEENA DAVISMADONNATOM HANKSDo these examples seem reasonable?: yes.: who did jurassic park star.MVSTARO.STNAMEJEFF GOLDBLOOM: steven spielberg directed jeff goldbloom.190MVDIRO.DIRNAMEPENNY MARSHALLPENNY MARSHALLPENNY MARSHALLSTEVEN SPIELBERGMVSTARO.STNAMEGEENA DAVISMADONNATOM HANKSJEFF GOLDBLOOMDo these examples seem reasonable?: yes.I : who was tom hanks directed by.MVDIRO.DIRNAMEPENNY MARSHALL: denzel washingtone is t he star of malcolm x.MVMOVIEO.MVNAME^MVSTARO.STNAMEJURASSIC PARKLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNJEFF GOLDBLOOMGEENA DAVISMADONNATOM HANKSDo these examples seem reasonable?: yes.: who is the star of league of their own.MVSTARO.STNAMEMADONNATOM HANKSGEENA DAVISI : steven spielberg directed jurassic park.MVDIRO.DIRNAME^MVMOVIEO.MVNAMEPENNY MARSHALL^LEAGUE OF THEIR OWNSPIKE LEE^MALCOLM X^.STEVEN SPIELBERG JURASSIC PARKDo these examples seem reasonable?191Now we'll try definingtwo different senses for theverb direct. Let's start withdirector directing movie.Notice that we defined thisearlier. The system canhandle such mistakes.: yes.I : steven spielberg directed jeff goldbloom.Now we'll define the other sense ofthe verb direct - director directingstar.MVDIRO.DIRNAMEPENNY MARSHALLPENNY MARSHALLPENNY MARSHALLSTEVEN SPIELBERGMVSTARO.STNAMEGEENA DAVISMADONNATOM HANKSJEFF GOLDBLOOMDo these examples seem reasonable? I : yes.: who directed jeff goldbloom.Now a couple of question to check things out.MVDIRO.DIRNAMESTEVEN SPIELBERG: who directed jurassic park.MVDIRO.DIRNAMESTEVEN SPIELBERG: who directed malcolm x.MVDIRO.DIRNAMESPIKE LEE: who directed tom hanks.MVDIRO.DIRNAMEPENNY MARSHALL: smith works for ford.EMPO.ENAME EMPl.ENAMEALLENFORDSCOTTWARDBLAKEJONESJONESBLAKE192Let's try two different senses of the verb works.One will relate to the employee database and onewill relate to the movie database. We'll start withemployee works for manager.Do these examples seem reasonable?I : yes.: tom hanks works for penny marshall.MVSTARO.STNAME MVDIRO.DIRNAMEGEENA DAVIS^PENNY MARSHALLJEFF GOLDBLOOM STEVEN SPIELBERGMADONNA^PENNY MARSHALLTOM HANKS PENNY MARSHALLNow we'll define the 'moviestar works for director' sense.Do these examples seem reasonable? yes.: who works for ford.A couple of test questions.EMPO.ENAMESMITH: who works for king.EMPO.ENAMEJONESCLARKBLAKE: who works for steven spielberg.MVSTARO.STNAMEJEFF GOLDBLOOM: smith works in research.EMPO.ENAME DEPTO.DNAME193CLARKKINGMILLERSMITHACCOUNTINGACCOUNTINGACCOUNTINGRESEARCHDo these examples seem reasonable?: yes.I : geena davis works in league of their own.MVSTARO.STNAME MVMOVIEO.MVNAMEGEENA DAVISJEFF GOLDBLOOMMADONNATOM HANKSLEAGUE OF THEIR OWNJURASSIC PARKLEAGUE OF THEIR OWNLEAGUE OF THEIR OWNDo these examples seem reasonable?I : yes.: who works in accounting.EMPO.ENAMECLARKKINGMILLER: who works in Jurassic park.MVSTARO.STNAMEJEFF GOLDBLOOMThe purpose of this wpm is to demonstrate that the claims made in my thesis arecomputationally effective. The thesis makes claims only about the poblem of portabilityof a natural language interfaces and so only minimal effort was directed towards creatinga general purpose natural language interface.
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Graduate
Improving the portability of natural language interfaces through learning
Text