13.6 Applications in Natural Language

13.6.6 Building a Natural Language Interface to a Database

You can augment the preceding grammar to implement a simple natural language interface to a database. The idea is that, instead of transforming sub-phrases into parse trees, you transform them directly into queries on a knowledge base. To do this, make the following simplifying assumptions, which are not always true, but form a useful first approximation:

  • nouns and adjectives correspond to properties

  • verbs and prepositions correspond to a binary relation between two individuals, the subject and the object.

In this case, a noun phrase becomes an individual with a set of properties defining it. To answer a question, the system can find an individual that has these properties. A noun phrase followed by a verb phrase describes two individuals constrained by the verb.

Example 13.39.

In the sentence, “a tall student passed a math course”, the phrase “a tall student” is the subject of the verb “passed” and the phrase “a math course” is the object of the verb. For the individual S that is the subject, tall(S) and student(S) are true. For the individual O that is the object, course(O) and dept(O,math). The verb specifies that passed(S,O). Thus the question “Who is a tall student that passed a math course?” can be converted into the query:

𝘢𝘴𝘬 tall(S)student(S)passed(S,O)course(O)dept(O,math).

The phrase “a tall student enrolled in cs312 that passed a math course” could be translated into

𝘢𝘴𝘬 tall(X)student(X)enrolled_in(X,cs312)passed(X,O)
    course(O)dept(O,math).

% A noun phrase is a determiner followed by adjectives followed by a noun followed by an optional modifying phrase:

noun_phrase(L1,L4,Ind)
    adjectives(L1,L2,Ind)
    noun(L2,L3,Ind)
    mp(L3,L4,Ind).

% Adjectives consist of a sequence of adjectives.

adjectives(L0,L2,Ind)
    adj(L0,L1,Ind)
    adjectives(L1,L2,Ind).
adjectives(L,L,Ind).

% An optional modifying phrase / relative clause is either a relation (verb or preposition) followed by a noun-phrase or nothing

mp(L0,L2,Subject)
    reln(L0,L1,Subject,Object)
    noun_phrase(L1,L2,Object).
mp(L,L,Ind).

% adj(L0,L1,Ind) is true if L0-L1 is an adjective that is true of Ind

adj([computer,scienceL],L,Ind)dept(Ind,comp_sci).
adj([tallL],L,Ind)tall(Ind).
adj([aL],L,Ind).    % a is treated as an adjective

% noun(L0,L1,Ind) is true if L0-L1 is a noun that is true of Ind

noun([courseL],L,Ind)course(Ind).
noun([studentL],L,Ind)student(Ind).

% The following are for proper nouns:

noun([IndL],L,Ind)course(Ind).
noun([IndL],L,Ind)student(Ind).

% reln(L0,L1,Sub,Obj) is true if L0-L1 is a relation on individuals Sub and Obj

reln([enrolled,inL],L,Subject,Object)enrolled_in(Subject,Object).
reln([passedL],L,Subject,Object)passed(Subject,Object).
Figure 13.11: A grammar that directly answers a question

Figure 13.11 shows a simple grammar that parses an English question and answers it at the same time. This ignores most of the grammar of English, such as the differences between prepositions and verbs or between determiners and adjectives, and makes a guess at the meaning, even if the question is not grammatical. Adjectives, nouns and noun phrases refer to an individual. The extra argument to the predicates is an individual which satisfies the adjectives and nouns. Here an mp is a modifying phrase, which could be a prepositional phrase or a relative clause. A reln, either a verb or a preposition, is a relation between two individuals, the subject and the object, so these are extra arguments to the reln predicate.

Example 13.40.

Suppose question(Q,A) means A is an answer to question Q, where a question is a list of words. The following provides some ways questions can be asked from the clauses of Figure 13.11, even given the very limited vocabulary used there.

The following clause allows it to answer questions, such as “Is a tall student enrolled in a computer science course?” and returns the student:

question([isL0],Ind)
    noun_phrase(L0,L1,Ind)
    mp(L1,[],Ind).

The following rule is used to answer questions, such as “Who is enrolled in a computer science course?”, or “Who is enrolled in cs312” (assuming that course(cs312) is true):

question([who,isL0],Ind)
    mp(L0,[],Ind).

The following rule is used to answer questions, such as “Who is a tall student?”:

question([who,isL],Ind)
    noun_phrase(L,[],Ind).

The following rule allows it to answer questions, such as “Who is tall?”:

question([who,isL],Ind)
    adjectives(L,[],Ind).

The following rule can be used to answer questions, such as “Which tall student passed a computer science course?” or even “Which tall student enrolled in a math course passed a computer science course?”:

question([whichL0],Ind)
    noun_phrase(L0,L1,Ind)
    mp(L1,[],Ind).

The following rule allows it to answer questions that have “is” between the noun phrase and the modifying phrase, such as “Which tall student is enrolled in a computer science course?” or “Which student enrolled in a math course is enrolled in a computer science course?”:

question([whichL0],Ind)
    noun_phrase(L0,[isL1],Ind)
    mp(L1,[],Ind).

The preceding grammar directly found an answer to the natural language question. One problem with this way of answering questions is that it is difficult to separate the cases where the program could not parse the language from the case where there were no answers; in both cases the answer is “no”. This makes it difficult to debug such a program. An alternative is instead of directly querying the knowledge base while parsing, to build a logical form of the natural language – a logical proposition that conveys the meaning of the utterance – before asking it of the knowledge base. The semantic form can be used for other tasks such as telling the system knowledge, paraphrasing natural language, or even translating it into a different language.

You can construct a query by allowing noun phrases to return an individual and a list of constraints imposed by the noun phrase on the individual. Appropriate grammar rules are specified in Figure 13.12, and they are used with the dictionary of Figure 13.13.

% A noun phrase is a determiner followed by adjectives followed by a noun followed by an optional prepositional phrase.

noun_phrase(L0,L4,Ind,C0,C4)
    det(L0,L1,Ind,C0,C1)
    adjectives(L1,L2,Ind,C1,C2)
    noun(L2,L3,Ind,C2,C3)
    pp(L3,L4,Ind,C3,C4).

% Adjectives consist of a sequence of adjectives.

adjectives(L,L,Ind,C,C).
adjectives(L0,L2,Ind,C0,C2)
    adj(L0,L1,Ind,C0,C1)
    adjectives(L1,L2,Ind,C1,C2).

% An optional prepositional phrase is either nothing or a preposition followed by a noun phrase.

pp(L,L,Ind,C,C).
pp(L0,L2,Sub,C0,C2)
    preposition(L0,L1,Sub,Obj,C0,C1)
    noun_phrase(L1,L2,Obj,C1,C2).
Figure 13.12: A grammar that constructs a query

In this grammar,

noun_phrase(L0,L1,O,C0,C1)

means that list L1 is an ending of list L0, and the words in L0 before L1 form a noun phrase. This noun phrase refers to the individual O. C0 is an ending of C1, and the formulas in C1, but not in C0, are the constraints on the individual O imposed by the noun phrase.

Procedurally, L0 is the list of words to be parsed, and L1 is the list of remaining words after the noun phrase. C0 is the list of conditions coming into the noun-phrase, and C1 is C0 with the extra conditions imposed by the noun-phrase added.

det(L,L,O,C,C).
det([aT],T,O,C,C).
det([theT],T,O,C,C).
noun([courseT],T,O,C,[course(O)C]).
noun([studentT],T,O,C,[student(O)C]).
noun([johnT],T,john,C,C).
noun([cs312T],T,312,C,C).
adj([computer,scienceT],T,O,C,[dept(O,comp_science)C]).
adj([tallT],T,O,C,[tall(O)C]).
preposition([enrolled,inT],T,O1,O2,C,[enrolled(O1,O2)C]).
Figure 13.13: A dictionary for constructing a query
Example 13.41.

The query

𝘢𝘴𝘬 noun_phrase([a,computer,science,course],[],Ind,[],C).

will return

C=[course(Ind),dept(Ind,comp_science)].

The query

𝘢𝘴𝘬 noun_phrase([a,tall,student,enrolled,in,a,computer,
    science,course],[],P,[],C).

returns

C=[course(X),dept(X,comp_science),enrolled(P,X),student(P),
    tall(P)].

If the elements of list C are queried against a database that uses these relations and constants, precisely the tall students enrolled in a computer science course could be found.