TU München - Fakultät für Informatik Lehrstuhl III: Datenbanksysteme

Parser

The main effort carried out during parsing is to issue search requests to the lookup service in order to discover all relevant resources (i.e., data, function, and cycle providers). The parser aborts the processing of a query if for some part of the query, no resources can be found. Not surprisingly, relevant data providers are found using the themes specified in the FROM clause of a query. For every theme, the lookup service registers no, one, or several matching collections from different data providers; a collection matches if it has the same theme and its objects have all the attributes used in the SELECT and WHERE clauses of the query.Likewise, the parser looks for function providers for each external function used in a query; again, external functions such as thumbnail can have several implementations from different function providers; all implementations that match the right name and signature are considered. Query operators such as join, union, or display are typically implicit in a query; for join and union the parser will consider built-in variants and all variants provided by function providers. For display, the parser will always consider ObjectGlobe's built-in variant which produces XML to represent query results; the parser will only consider a different display operator if this is explicitly requested.

In theory, every cycle provider can be useful to execute a query. Considering all cycle providers for every individual query would simply be infeasible. To find relevant and interesting cycle providers, data and function providers can register a set of preferred cycle providers to handle their data or execute their functions; this set of preferred cycle providers will typically include the machines of the data or function provider. In addition, each ObjectGlobe end user (or application programmer) can specify a set of preferred cycle providers; this set may include the client machine of the user. For a given query, the parser determines the overall set of interesting cycle providers from the preferred cycle providers of the user and of all relevant data and function providers. From this set, the parser will further prune cycle providers which are clearly not useful; e.g., cycle providers which are not allowed to process any function. It should be noted that registering preferred cycle providers is optional; therefore, it is possible that the parser stops processing a query if neither the user nor any relevant data or function provider have specified preferred cycle providers, although the query could be executed using non-preferred sites.

In addition to discovering all relevant resources, the parser consults the lookup service in order to retrieve all available statistics and authorization information. As a result, the parser produces a (quite complex) XML document which is then used by the optimizer in order to generate a plan. Figure 6 shows an example how the authorization and applicability information is represented as a compatibility matrix for collections, functions, and cycle providers. For each relevant collection such a compatibility matrix is generated by the parser. A point at (c,f) in a matrix of a collection is set if cycle provider c is authorized to see the collection, function f is authorized to process objects of the collection, c is authorized to execute f, and c is capable of executing f (i.e., has enough memory and disk space). For instance, wrap_S may be executed at all cycle providers in order to read collection S, but it may obviously not be used anywhere to read collection R or T. In the matrix, built-in query operators such as display, scan, and join are treated in the same way as external functions (e.g., thumbnail and wrap_S); it would be possible, for instance, that a cycle provider only allows its own join methods to be executed on its machines.

Figure 6: Compatibility Matrices for the Example of Section 2.2