Documentation of Wrapper Components

Matcher - Parser - Library - Optimizer

07/10/1996Marcus Breunig
07/14/1996Joachim Hammer

Table of Contents

  1. About This Document
  2. The Matcher
    1. What Matches What
    2. Matcher Files
    3. Execution of Actions
    4. Example
    5. Interface and Error Handling
    6. Implementation Notes
    7. Testfile
  3. The Library
  4. The Parser
    1. "Site" Requirements
    2. Actions, Rulenames, and Desirability
    3. New Interface and Error Handling
    4. Class TRACER
    5. How to Free the Memory of the Parse Trees
    6. Changes to pdp.h
  5. The Optimizer
  6. What File Goes Where in the TSIMMIS Directory

1. About This Document

This document was written by Markus Breunig ( and describes the work I have done in June/July 1996 on the TSIMMIS project.

2. The Matcher

My original and main project was to write code to match templates and queries for the wrappers in TSIMMIS.

2.1. What Matches What

Queries contain: variables, constants
Templates contain: variables, constants, placeholders

Variable XVariable Y remember binding X=Y
Constant Cerror
Placeholder Perror
Constant CVariable Y generate filter Y=C
Constant Cok
Constant Derror (D !=C)
Placeholder Premember binding P=C

Variable YVariable Xremember binding X=Y
Constant Cgenerate filter Y=C
Constant CVariable Xerror
Constant Cok
Constant D(D !=C) error
Placeholder PVariable Xerror
Constant Cremeber binding P=C

2.2. Matcher Files

The directory contains code to match a query with a template. The following files are important:

Contains the data structures used to represent both the query and the template (abstract syntax tree). It was originally written by Yannis as part of the mediator parser. I tried to document it as much as I could. I added the action*type structs to support actions and support for placeholders. I also extracted all global variable definitions from pdp.h and put them into pdp.h has been moved into the include/ directory. Manage the table of what matches what. more specifically what variables in the query match what variables in the template, and what placeholder in the template is assigned what constant value in the query. Do the matching itself. Modelled very closely along the data structued in pdp.h, for every struct one function to match it (mostly at least). Also contains code to execute the actions after the matching is complete. Matching is the process of 1) finding which placeholders are bound to which constant 2) checking that the query can be answered by the template 3) generate filters for indirectly supported queries. A backtracking algorithm is used. Instantiates the templates used in the matcher. Picks the best rule out of all matching rules. See 5. Testcode for the parser and the matcher.

2.3. Execution of the Actions

The actions are executed left to right. Newly defined placeholders can be used in the next rule. $$ is evaluated, however as we currently match the query to only one template (and not multiple templates as in the more general case) $i is never defined.

2.4. Example

To illustrate lets have a look at a concrete example:

We use a template consisting of 2 rules:

C :- C: <report {<title $X>}>
// "select * from book where Title = " ^ $X //.

B :- B: <book {<author $X><title Y><date Y>}>
// $S = "select * from "
$T = $S ^ "book where ",
$$ = $T ^ "Author = " ^ $X //.

and submit the following query:

A :- A: <book {<author "Joe"><title "1991"><date "1991">}>.

The parser and matcher together will produce the following results:

** Parsing template
C_0 :-
C_0:<OID1_0 report {<OID0_0 title $X_0>}>@(null)
// "select * from book where Title = " ^ $X_0 //.

B_1 :-
B_1:<OID5_1 book {<OID2_1 author $X_1> <OID3_1 title Y_1>
<OID4_1 date Y_1>}>@(null)
// $S_1 = "select * from " ,
$T_1 = $S_1 ^ "book where " ,
$$ = $T_1 ^ "Author = " ^ $X_1 //.

** Parsing Query
A_0 :-
A_0:<OID9_0 book {<OID6_0 author Joe> <OID7_0 title 1991>
<OID8_0 date 1991>}>@(null).

** Matching

** Results
Rule chosen : 1
Action : "select * from book where Author = Joe"
$X_1 = Joe
$S_1 = select * from
$T_1 = select * from book where

extractor :
A_0:<OID9_0 book {<OID6_0 author Joe> <OID7_0 title 1991>
<OID8_0 date 1991>}>

constructor :

Optimizer chose rule: 1

Rules are numbered starting from 0. The second rule (rule 1) illustrates the usage of additional placeholders.

2.5. Interface and Error Handling

The matcher has a very simple interface. Standard code to use it would look like this:

void f() {
Match *m;
struct rulelisttype *templ;
struct rulelisttype *query;
Tracer TrQuery, TrTempl;
Parser parser;
char **vtTempl, **vtQuery;

// parse the template file
templ = parser.File("TEMPLATE");
// check if the parsing was successful
if(templ==NULL) { // parse error
cerr << " Parser error parsing the template. " << endl;
} else {
// get the symbol table from the parser
vtTempl = parser.GetVT();
// initialize the tracer with the symbol table
// print the parsed template

// parse the query file
query = parser.File("QUERY");
// check if the parsing was successful
if(query==NULL) { // parse error
cerr << " Parser error parsing the query. " << endl;
} else {
// same as for template
vtQuery = parser.GetVT();

// create the matcher and let him do the matching
m = new Match(query->rule, templ);
// get the results from the matcher
const MatchResult *mr = m->GetResult();

// see what the matcher says
if(mr==NULL) { // matching not successful
if(m->GetState()==S_NOMATCH) {
// matching did just fail
} else if(m->GetState()==S_ERROR) {
// error while matching
// in this case more info about the error can be found in the
// ErrMsg string the matcher provides

cerr << "ERROR: " << m->GetErrMsg() << endl);
} else {
// matching was successful
// use the mr->... to continue working
// optimize the result.

Optimizer o;
mr = o.optimize(mr);
// now use mr to go to the source
delete m;
delete vtQuery;
delete vtTempl;

2.6. Implementation Notes

The following is NOT a concise abstract about the implementation of the matcher, but rather just s bunch of points I think might be important for someone trying to understand the code.

Matcher-local variables:

The binding table. It keep which template var is bound to which constant or query var and which placeholder is bound to which constant. The current contents can be checkpointed and restored, which is used for backtracking purposes.
List of all the rules the were matched successfully so far and the infos gathered during the matching process. Newly matched rules are inserted at the head of this list.
Number of the rule we are currently trying to match.
number of the var in the template rule we are currently trying to match.
pointer to the rule we are currently trying to match.
query, templ
the query and the list of rules as provided by the user.
The part of the query used to extract the result.
list of all predicates in the template that could not be matched to the current rule.
True when we are currently working an a subtree of the template var definition in the rule.
Set of all the vars in used in the query head.
All query vars accessible after the query has been executed by the source. Computed while we are traversing the rule-graph.
State we are in to facilitate error handling.
error message string as set by the function that found the error.

Algorithm used:

The matcher works by recursivly traversing the data structures as defined in pdp.h, and backtracking in case of dead ends.


In order for the algorithms to work properly when predicates are present it is important, that all the predicates are at the end of the cond-list that represents the rule. This function reorders the cond-list-conds so that this condition holds. The reasons that this is necessary is that in order to check if a predicate can be evaluated we need to know all "GoodVars" (See above for def of GoodVars). However, we match one rule-cond after the other by trying to match it with all remaining query-conds. Now if e.g. the first rule-cond is a predicate it will never be matches successfully because we have not computed the GoodVars yet. If it is at the end of the condlist however, it will work.


The functions that do the actual matching.

Again, this is used to handle predicates. When traversing the pdp.h data structures we need to keep track of wether we are under a top-level predicate or under a top-level objectcondition. Depending on which one we are under different actions need to be taken during the matching process (e.g. under a objectcondition when we encounter two variables, we remember the mapping and if no other mapping exitst so far everything is fine. Under a predicate however, we do need an already existing mapping and need to do some other checks). As terms can be in both predicates and object-conds we need different versions for these, too.


Used to check if all variables occuring in this part of the data structure are GoodVars. Applied to all preds in the query that cannot be matched to any preds in the template and therefore have to be evaulated later by the engine.


Evaluation functions for the actions. New term-functions for the actions can be added here.


These functions add all variables occuring in their parameters to the GoodVars. Used to add all these vars in parts of the query tree that are under the part of the tree that corresponds to the tree under the template-head-var.

2.7. Testfile

In order to test my code I've written a test-program that read a template and a query, parses them, matches them, calls the optimizer and prints the results. This program is called, read the file TEMPLATE and the file QUERY. It can be used to test more templates and queries.

3. The Library

I noticed that the TSIMMIS project did not use a library with all the standard functions so far. As I needed classes like sets etc., I decided it would be worth to put these into a general library for reuse. The library code is contained in the subdirector L. The main header file is l.h. The library makes extensive use of C++ templates. The compiler used was + 2.7.0, so it should be portable in spite of the use of templates.

4. The Parser

During the coding phase of the wrapper some deficiencies of the parser became apparent. I was assigned the task to clear up the parser and do the necessary changed. The parser was originally written by Yannis, modified by Amit Agarwal to incorporate the actions.

Unfortunately due to a misunderstanding between Amit and Vassilis the code Amit wrote did not solve the actions in a satisfactory manner. After looking at the code I decided the best way to go was to start anew from Yannis' code.

4.1. "Site" Requirements

As the parser was originally written for the mediators it required every condition to have a site associated with it, e.g. A :- A:<book {<author $B>}>@s1 As the wrapper only runs at one site this is not necessary for the wrapper. I changed to parser so the site is only optional and not required any more. So A :- A:<book {<authro $B>} will parse without error.

4.2. Actions, Rulenames and Desirability

Actions were completely recoded. Newly introduced were names for the rules and a way to specify desirability, which is used by the optimizer. The syntax for template is now:

template ::= {rule}*

rule ::= [PreHead] Head :- Condition-List Actionlist.

PreHead ::= RuleName:Desirability

RuleName ::= Constant
Desirability ::= Constant

Head ::= as before

Actionslist ::= // NoAssAction //
             |  // AssAction { , AssAction }* //

NoAssAction ::= ActionBody

AssAction   ::=  $$ = ActionBody
             |   Placeholder = ActionBody

ActionBody  ::= ActionTerm

ActionTerm  ::= Func ( ActionTerm )
             |  ActionTerm { ^ ActionTerm }*
             |  Constant
             |  Placeholder
             |  $$

Constant    ::= "{AlphanumericalChar}*"

Placeholder ::= $UpercaseChar{AlphenumericalChar}*

Condition-List ::= similar to before, but everywhere where Variables
                   were allowed we also now allow Placeholders

Func is a function symbol. Each function symbol expects a certain
number of parameters. Currently the following function-symbols and 
associated functions are available:

uppercase(X) : converts X into uppercase letters

lowercase(X) : converts X into lowercase letters

equal(X,Y)   : if the caseinsensitive comparison of X and Y yields
               that they are the same, this function returns "TRUE",
               otherwise it returns "" (the empty string)

if(X,Y,Z)    : if X is not the empty string ("") then this
               function returns X otherwise it returns Z

cr()         : returns a "\n", i.e. a newline

quote(X)     : puts the string in quotes, i.e. returns "X"

4.3. New Interface and Error Handling

A new interface to the parser has been designed. The class Parser provides two functions for parsing: one to parse a file and one to parse a string. The code for this interface is in and parse.h. The parser error handling has been changed from abort'ing to returning NULL as a parse string if a parse error occurs.

4.4. Class Tracer

The files and trace.h contained C functions to print a parse tree into understandable form. These functions have been encapsulated into a "Tracer" class (files and tracer.h). Furthermore new functions have been written to enable printing of Placeholders and Actions.

4.5. How to Free the Memory of the Parse Trees

The easiest way to free the memory occupied by the parse trees is by calling the Free functions of the class Parser. They are overloaded functions that recursively free the whole parsetree starting at the point given. Typical code would look like this:


Parser parse;

struct rulelisttype *res;

res = parse.File("TEMPLATES");




4.6. Changes to pdp.h

The pdp.h file has been changed in the following ways:

  1. all global variables have been moved to
  2. the ruletype has 3 new fields:
  3. changes to termtype:
  4. new struct actionlisttype
  5. new struct actiontype
  6. new struct actionoplisttype
  7. new struct actionoplistlisttype
  8. new struct actionoptype

Furthermore the file pdp.h now contains comments describing all structures

and which fields are valid for which kind values (at least to the best of

my knowledge). More comments would not hurt, though.

5. The Optimizer

The parser returns a list of rules that match. The optimizer has the job of determining which one will be the most efficient to execute. It currently uses the following heuristic: Let R be the set of all matching rules. It can be partitioned into two disjoint sets P and NP, where P contains all rules that have not enough predicates for the query, i.e. rules for which additional predicates have to be evaluated after getting the result from the source. NP contains all other matching rules. So R = P union NP, and P and NP are disjoint.

If NP it not empty then the optimizer picks as the best rule the one with the highest desirability on NP, otherwise the one with the highest desirability in P.

The interface to the optimizer is very simple:

const MatchResult *mr, *omr;

Optimizer o;

.. get mr from matcher...

omr = o.optimize(mr)


omr points to the best element in the list mr.

6. What File Goes Where in the TSIMMIS Directory

The following files need to be copied into the TSIMMIS directories:

=> ~tsimmis/tsimmis-1.0/src/common/pdp.h

=> ~tsimmis/tsimmis-1.0/src/wrappers-96/parser/*

=> ~tsimmis/tsimmis-1.0/src/wrappers-96/matcher/*

=> ~tsimmis/tsimmis-1.0/src/wrappers-96/matcher/L/*