15.5 Translating User Queries to Engine Queries

Building Parsers with Java
By Steven  John  Metsker

Table of Contents
Chapter  15.   Parsing a Query Language


15.5 Translating User Queries to Engine Queries

You can extract facts from a logic program by issuing queries whose structures match the types of facts in the program. For example, to retrieve chip facts you can create a structure with functor "chip" and with five variables . When you write a query language for a commercial database engine, the ability to query any table is probably already built into the engine. Because you are using a logic engine here, you must create a query method for each class of fact in the program. Your parser will rely on these query structures when it translates a user query into an engine query. Figure 15.12 shows the query methods for ChipSource .

Figure 15.12. The ChipSource query methods. ChipSource contains protected methods that produce query structures for each class in the object model. These methods support the public queryStructure() method, which returns a query structure given the object's class name .


For each class in the object model, ChipSource has a static method that produces a query for objects of that class. Here is the code for ChipSource.queryChip() :

 /*   * Returns a query that matches chip facts.  */ public static Structure queryChip() {     return new Structure("chip", new Term[]{         new Variable("ChipID"),         new Variable("ChipName"),         new Variable("Price"),         new Variable("Ounces"),         new Variable("Oil")}); } 

This method creates a structure that prints itself as

 chip(ChipID, ChipName, Price, Ounces, Oil) 

This structure can unify with a chip fact, which unifies each variable in the query structure with its corresponding value in the fact. When you build a query language parser, you create assemblers that use query structures to extract the values of facts. The query methods for customer and order are similar. With these elements in place, you can formulate a translation strategy for user queries.

You want to let a user enter a Jaql query such as

 select CustomerLast, BagsPerMonth from Customer, Order  where BagsPerMonth > 2 

To achieve this, you must parse the text and create a Query object that

  • Has a query structure for each named class

  • Has a comparison structure for each where clause

  • Selects only the named variables to return to the user

If you ignore for now the user's request for only some of the variables, the engine query that you want is

 customer(CustomerID, LastName, FirstName),  order(CustomerID, ChipID, BagsPerMonth), >(BagsPerMonth, 2) 

This translation simply replaces each class that the user query names with the query template for that class, and it converts the where clause into a comparison format that the engine can understand. This translation relies on the natural join of like-named variables in the query structures.

15.5.1 Natural Joins

In the example, the engine query forces a natural join on the variable CustomerID , which appears in both query structures. When the query proves itself, the customer structure in the query unifies with one of the customer facts in the Program object. After each successful unification of the customer structure, the query tries to unify its order structure with order facts. All the structures in a query share the same variable scope, so at this point in a proof the order structure's CustomerID variable is unified with a value. Thus, the order structure will be able to unify only with order facts for that customer.

Occasionally, joining variables by name is limiting. For example, consider a Logikus program with the genealogical data

 parent(henry, peter);  parent(peter, bridget); 

To find grandparents, children, and grandchildren, you could issue the query

 parent(Grandparent, Child), parent(Child, Grandchild) 

This query will find

 Grandparent = henry, Child = peter, Grandchild = bridget 

You cannot translate this Logikus program and query into Jaql because Jaql does not provide for naming variables within a fact. There is no way to retrieve parent facts so that the first term is in one case a Grandparent and in a another case a Child . You can overcome this limitation by extending the syntax of Jaql to allow naming variables, but this book does not take up that challenge.

15.5.2 Where Clauses

When the query is able to unify with customer and order facts, the last structure in the query applies the where clause. A where clause is a comparison, and the query language parser must translate the user input to comparisons that the engine can process.

For example, the query clause

 where BagsPerMonth > 2 

translates to the engine structure

 >(BagsPerMonth, 2) 

15.5.3 Projection

Limiting the variables the user wants to see introduces the topic of projection. Projection is a matter of specifying which variables are interesting to the user. For example, consider again the select statement

 select CustomerLast, BagsPerMonth from Customer, Order  where BagsPerMonth > 2 

As this query executes, it establishes values for all the variables in Customer and Order . However, the query asks to see results for only CustomerLast and BagsPerMonth . An intuitive way to achieve this result in the engine is to introduce a rule whose head has only the variables you want:

 q(CustomerLast, BagsPerMonth) :-      customer(CustomerID, LastName, FirstName),     order(CustomerID, ChipID, BagsPerMonth),     >(BagsPerMonth, 2) 

You can add this rule to the engine and create a query:

 q(CustomerLast, BagsPerMonth) 

This query unifies with the head of the rule, the rule proves itself, and the variables in q unify with the proof values. This approach is effective, but in practice you can use a shortcut. To limit the query results to only CustomerLast and BagsPerMonth , you need not add a rule to the engine. It is simpler to prepend the q structure to the query and prove the tail of the query. You create the query as

 q(CustomerLast, BagsPerMonth),  customer(CustomerID, LastName, FirstName), order(CustomerID, ChipID, BagsPerMonth), >(BagsPerMonth, 2) 

You cannot prove this query because there is no q fact in the program. However, the tail of the query can prove itself as before if the tail consists of all the structures after the first, head structure q . The trick to reducing the variables seen by the user is to introduce a head structure that contains only the interesting variables, prove the tail of the query, and show the user the variables in the head structure. These variables will unify with successful results as before.


Building Parsers with Java
Building Parsers With Javaв„ў
ISBN: 0201719622
EAN: 2147483647
Year: 2000
Pages: 169

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net