4. Resulting Requirements

This chapter describes requirements a query language must fulfill to be able to implement the OCL compilers type information component.

4.1 Order of Instance Nodes

This section shows by example, that a query language must be able to evaluate the order of nodes in the document instance.

4.1.0.0.1 Example.

Given the following example, written down in Java.

class someClass
{
  Return1 operation(int x, String y);
  Return2 operation(String y, int x);
}

When the type component is queried for the first of both operations , it looks like this.

someclass.navigateParameterized("operation", 
  { Basic.INTEGER, Basic.STRING } );

Obviously, this expression should evaluate to Return1.

Lets see, how this query can be implemented using XML-QL. At first the (simplified) XMI representation of the example above.

<Class name="someClass">
  <Operation name="operation">
    <Parameter kind="in" name="x" type="int" />
    <Parameter kind="in" name="y" type="String" />
    <Parameter kind="return" type="Return1" />
  </Operation>
  <Operation name="operation">
    <Parameter kind="in" name="y" type="String" />
    <Parameter kind="in" name="x" type="int" />
    <Parameter kind="return" type="Return2" />
  </Operation>
</Class>

Note that both operations differ in the order of the Parameter elements only.

Now lets have a first try of the XML-QL query.

WHERE 
<Class name="someClass"> 
  <Operation name="operation"> 
    <Parameter kind="in" type="int" /> 
    <Parameter kind="in" type="String" /> 
    <Parameter kind="return" type=$r /> 
  </Operation> 
</Class> 
IN "example.xmi", 
CONSTRUCT <result>$r</result> 

This query is not yet correct. By default, XML-QL matches without checking order of nodes. Thus the query matches to both operations and returns

<result>Return1</result> 
<result>Return2</result>

To achieve the correct behavior, the query is slightly extended. Enclosed in square brackets are element-order variables. These variables are bound to the index in the local order of document nodes. An additional precondition rejects matches with the undesired order. Additions are put in italic.

WHERE 
<Class name="someClass"> 
  <Operation name="operation"> 
    <Parameter kind="in" type="int" /> [$i] 
    <Parameter kind="in" type="String" /> [$j] 
    <Parameter kind="return" type=$r /> 
  </Operation> 
</Class> 
IN "example.xmi", 
$i < $j 
CONSTRUCT <result>$r</result>

This query matches only the first operation. Correctly it produces

<result>Return1</result>

Note that the XML-QL prototype currently available from AT&T Labs does not support queries for instance order.

4.1.0.0.2 Evaluation of impact.

It has to be admitted, that the problem described here is somewhat exotic. For a collision to occur, it needs two operations in a class, differing in the order if their parameters only.

The problem of transitive closures described below is much more important.

4.2 Transitive Closure

This section shows by example, that a query language must be able to process queries including the transitive closure of a given relation.

The type component must implement a query for generalizations. Given two classes the query must determine whether one class is a (possibly indirect) subtype of the other.

Our example features four classes in a linear generalization.

XMI represents this model as a relationship table. Somewhat simplified, it looks like this.

<generalization supertype="Person" 
                subtype="Employee" />
<generalization supertype="Employee" 
                subtype="Programmer" />
<generalization supertype="Programmer" 
                subtype="Guru" /> 

For an easy start, we retrieve the generalization from Employee to Person.

WHERE
<generalization supertype="Person" 
                subtype="Employee">
IN "example.xmi"
CONSTRUCT yes

When querying for the indirect generalization from Programmer to Person, we use a self join.

WHERE
<generalization supertype="Person" subtype=$a>

IN "example.xmi",
<generalization supertype=$a subtype="Programmer">
IN "example.xmi"
CONSTRUCT yes

This works for generalizations of any order. From Guru to Person it takes three steps.

WHERE
<generalization supertype="Person" subtype=$a>,
IN "example.xmi"
<generalization supertype=$a subtype=$b>,
IN "example.xmi"
<generalization supertype=$b subtype="Guru">
IN "example.xmi"
CONSTRUCT yes

However, there is a serious drawback. These queries need to know the ``generalization distance'' in advance.

To address this issue, the query language must feature recursion. XML-QL does not provide recursion. Chapter 5 shows, that XSLT solves this problem.

4.2.0.0.1 Evaluation of impact.

This requirement is essential for a query language to be suitable for implementing the type component. Note that the query for generalizations is only the simplest case. The type checker must also care about inherited features and polymorphism of operation parameters. This cannot be implemented without traversing arbitrary generalization trees.

4.3 Summary

This chapter introduced two requirements for a query language. The need for evaluating node order will be rare, but certainly the inability to handle these situations well leaves the author with strong discomfort. However, the need for querying over transitive closures is essential. For a query language to be suitable for our task, there is no way around it.