Balisage Paper: Optimized Cartesian product: A hybrid approach to derivation-chain checking in XSD 1.1

Introduction

In this paper we propose an hybrid solution to the problem of verifying whether a type is a legal restriction of its base in XSD 1.1.

Version 1.1 of XML Schema (XSD) in now in Working Draft [XSD 1.1: Structures, XSD 1.1: Datatypes]. One of the most important features introduced by XSD 1.1 is Conditional Type Assignment, i.e., the possibility for element declarations to assign a type based on XPath predicates. CTA is meant to address one of the most evident limitations of XSD 1.0: the co-constraint definition support.

The CTA introduction in XSD arises an issue concerning the derivation by restriction between types containing conditional declarations. Indeed, the type actually assigned by a conditional declaration can be known at run-time only and it may vary from element to element. Thus the problem of statically verifying whether a type is a legal restriction of its base when conditional declarations are involved is difficult. It is possible to identify three alternative approaches to the problem:

Co-occurrence constraints (also known as co-constraints ) are rules relating the presence and values of elements and attributes that may occur in distinct fragments of an XML document. E.g., we have a co-constraint when an attribute value governs the content of an element, or when two attributes are in some logic/arithmetic relation, and so on. Co-constraints are present in several XML-based languages, among which also languages recommended by W3C.

One of the widely recognized limitations of XSD 1.0 [XSD 1.0: Structures, XSD 1.0: Datatypes] is the inability to define co-constraints. This is a serious shortcoming for a schema language, and especially for XSD, given its widespread use. Indeed, when a schema is not able to capture every validity constraints of a class of XML documents, in order to reach a complete validation process specific modules are required to verify those constraints not covered by the schema. In such cases, not only the validation process becomes more complex, but also the interoperability between applications decreases.

Version 1.1 of XSD introduces two mechanisms for the co-constraint definition: assertions and Conditional Type Assignment (CTA). The former is inspired by Schematron [Schematron ISO specification]. It permits to augment type definitions with XPath predicates (called assertions), each specifying a further validity condition besides those enforced by the content model. Assertions are particularly useful to require some elements and attributes to be in logic or arithmetic relations.

CTA, inspired by SchemaPath [P. Marinelli, C. Sacerdoti Coen, and F. Vitali, 2004], allows an element declaration to conditionally assign a type based on XPath predicates. Here we refer to declaration of such a typology as conditional declarations. CTA is particularly suitable for those situations where an attribute value governs the content of an element. For instance, in order to subject the content of a <entry> element (representing a bibliographic entry) to the value of the kind attribute, the following conditional declaration might be used

<xs:element name="entry" type="Entry">
	<xs:alternative test="@kind = 'proceedings'" type="ProceedingsEntry" />
	<xs:alternative test="@kind = 'journal'"     type="JournalEntry" />
	<xs:alternative test="@kind = 'book'"        type="BookEntry" />
</xs:element>

The above declaration reads as "if @kind is proceedings then <entry> is of type ProceedingsEntry, otherwise if @kind is journal then <entry> is of type JournalEntry, otherwise if @kind is book then <entry> is of type BookEntry, otherwise (none of the above conditions hold) <entry> is of type Entry (which is a type for generic bibliographic entries). Each <xs:alternative> element is named type alternative in XSD 1.1.

Conditional declarations arise an issue in the derivation by restriction. XSD (both 1.0 and 1.1) allows to define new types deriving existing ones. A derivation method is by restriction. The general principle behind the derivation by restriction is that the derived type accepts a subset of what the base type accepts. Thus, given an element E, it is required that the type assigned to E in the context of the derived type, be a restriction of the type assigned to E in the context of the base type. The presence of conditional declarations heavily complicates the static verification of such principle, as it require to analyze logic relations among XPath predicates. However, there are at least three alternative approaches to the problem of verifying whether a type is a legal restriction of its base:

The XSD current draft adopts the full dynamic approach. Indeed, at schema compile time the derivation by restriction is checked simply ignoring type alternatives. Given an element E, at run-time it is checked that the type conditionally assigned to E in the context of a derived type is a restriction of the type which would be assigned to E in the context of the base type. Such a condition is then recursively checked also for E and the base type, until the type hierarchy root is reached. I.e., the condition is checked on the entire derivation chain of the initial derived type. We call such a solution Run-Time Check (RTC). The XSD Working Group publicly solicit input from implementors and users of this specification as to whether the current run-time rule should be retained [XSD 1.1: Structures].

Cartesian Product (CP) is another solution but adopts a hybrid approach. At schema compile time it analyzes all possible cases that may occur at run-time. As the number of such cases is very high, it has serious shortcomings concerning the computational cost of the static phase.

In this paper we propose a hybrid solution to the problem of the verification of the derivation by restriction in presence of conditional declarations. We call our solution Optimized Cartesian Product (OCP). OCP, CP, and RTC have the same extensional behavior. OCP can be seen as an optimization to RTC. Indeed, at run-time the number of XPath predicates evaluated by OCP is less than or equal to the number of XPath predicates evaluated by RTC. Moreover, the OCP static phase requires an acceptable computational cost. So OCP is also an optimization to CP (and hence its name). Our paper contribute is two-fold:

Our paper is organized as follows. The next section describes XSD 1.1 in relation to the problem of the co-constraint definition. In particular it describes CTA and assertions. Then we introduce some XSD 1.1 specific terminology in Section “XSD Terminology”. In Section “Derivation by Restriction in XSD 1.1” we describe the problem of the derivation by restriction in presence of conditional declarations. There we describe some possible approaches and solutions. In particular, we provide a detailed Run-Time Check description, including a computational cost analysis. We also discuss about Cartesian Product. Then in Section “Optimized Cartesian Product” we describe our proposal, providing a computational cost analysis for both the static phase and the dynamic phase. Then in Section “Comparing CP, OCP, and RTC” we compare RTC, CP and OCP, mainly focusing on the number of XPath predicates evaluated at validation time by the three techniques. Then we describe a prototype implementation for OCP, which demonstrates the feasibility of our proposal. Before concluding, in Section “Related Works” we discuss about some related works.

XSD 1.1 and Co-Constraints

XSD (XML Schema Definition Language) is the schema language proposed by W3C. Its current version is 1.0, and it is described by two W3C recommendations [XSD 1.0: Structures, XSD 1.0: Datatypes]. Although there are many other schema languages (such as RELAX NG [RELAX NG ISO specification], and Schematron [Schematron ISO specification]), XSD probably is the most known and supported. XSD 1.0 provides support for the definition of a number of constraint kinds. For instance, by means of content models, it is possible to define the legal content of elements. XSD provides a rich set of built-in types for the definition of legal data values. It also provides derivation mechanisms, permitting to construct new types from existing ones. Moreover, XSD allows to define uniqueness and reference constraints on elements and attributes (cumulatively called identity-constraints).

However, XSD 1.0 is widely recognized as unable to express a particular kind of constraints: co-occurrence constraints (commonly referred to as co-constraints). According to the definition given by the ESW Wiki, co-constraints are rules which govern what kinds of markup (elements, attributes) can occur together (co-occur) in an XML document. [Co-occurrence constraints ESW Wiki]. In other words, a co-constraint relates the existence or values of an element (or attribute) to the existence or values of other elements (or attributes).

Some categorizations for co-constraints do exist. Within the ESW Wiki about 30 use-cases are listed, ranging from the mutual exclusion of attributes, to the requirement that two elements values must be in some arithmetic relation. In 2001, Norman Walsh and John Cowan identified seven kinds of co-constraints [N. Walsh and J. Cowan, 2001].

XSD 1.0 is unable to express co-constraints. Such an inability is heavily felt for in many user communities. For instance, validation of incoming data is critical for e-business infrastructures, that require also the adoption of co-constraints. Adopting XSD 1.0 as validation language requires them to implement application-specific modules, in order to provide a complete validation process.

W3C is releasing a new version of XSD: XSD 1.1. At the time of writing, it is in Last Call Working Draft [XSD 1.1: Structures, XSD 1.1: Datatypes]. One of the major improvements over 1.0, is the support for co-constraints definition. For this purpose, XSD 1.1^[1] introduces two mechanisms: assertions and Conditional Type Assignment. Both mechanisms will be described in the next two sections.

<xs:element name="pages" type="PagesType" />
<xs:complexType name="PagesType">
  <xs:attribute name="from" type="xs:positiveInteger" />
  <xs:attribute name="to" type="xs:positiveInteger" />
  <xs:assert test="@from le @to" />
</xs:complexType>

<xs:complexType name="Entry">
  <xs:sequence>
    content model for a generic entry
  </xs:sequence>
  <xs:attribute name="kind" type="EntryKindType" />
</xs:complexType>

<xs:complexType name="ProceedingsEntry">
  <xs:complexContent>
    <xs:extension base="Entry">
      <xs:sequence>
        <xs:element name="conference" type="Conference" />
        <xs:element name="pages" type="Pages" />
      </xs:sequence>
    </xs:extension>
  </xs:complexContent>
</xs:complexType>

<xs:element name="entry" type="Entry">
  <xs:alternative test="@kind = 'proceedings'" type="ProceedingsEntry" />
</xs:element>

XSD Terminology

For the reader unfamiliar with XSD, this section introduces some CTA-related definitions taken from the XSD current draft [XSD 1.1: Structures].

Derivation by Restriction in XSD 1.1

XSD allows to define new types from existing ones through two derivation mechanisms, extension and restriction. The latter is meant to define a type whose content model accepts a subset of what the base type content model accepts.

<xs:complexType name="B">
  <xs:sequence>
    <xs:element name="e" type="xs:anyType">
      <xs:alternative test="@a >  @b" type="T1" />
      <xs:alternative test="@a <= @b" type="T2" />
    </xs:element>
  </xs:sequence>
</xs:complexType>

<xs:complexType name="R">
  <xs:complexContent>
    <xs:restriction base="B">
      <xs:sequence>
        <xs:element name="e" type="xs:anyType">
          <xs:alternative test="@a >  @b" type="T2" />
          <xs:alternative test="@a <= @b" type="T1" />
        </xs:element>
      </xs:sequence>
    </xs:restriction>
  </xs:complexContent>
</xs:complexType>

<xs:complexType name="T1">
  <xs:sequence>
    <xs:element name="t1" />
  </xs:sequence>
  <xs:attributeGroup ref="ab" />
</xs:complexType>

<xs:complexType name="T2">
  <xs:sequence>
    <xs:element name="t2" />
  </xs:sequence>
  <xs:attributeGroup ref="ab" />
</xs:complexType>

The presence of conditional declarations within content models immediately arises a question concerning the derivation by restriction. In order to explain the issue, let us consider the schema snippet shown in Figure “CTA Restriction Example”. We can observe that neither T1 derives from T2, nor the converse. Also it is easy to observe that whenever the conditional declaration within B assigns T1, the conditional declaration within R assigns T2, and vice versa.

Now let us consider the following XML fragment:

<p xsi:type="R">
 <e a="5" b="2"> <!-- @a > @b -->
   <t2 />
 </e>
</p>

As <p> is assigned type R, its child <e> is assigned type T2. According to the schema, <e> is valid against T2. For what previously observed, the type that would be assigned to <e> if <p> was of type B is T1. Clearly, <e> is not valid against T1. Thus we have that B rejects something R accepts. We can reasonably argue that this is a violation of the principle behind the derivation by restriction. And actually, the XSD current draft imposes constraints meant to detect as illegal situations like the one above.

Before discussing in details how the XSD current draft faces the derivation by restriction in presence of conditional declarations, we examine some general approaches to the problem.

<xs:complexType name="B">
  <xs:sequence>
    <xs:element name="message" type="messageType">
      <xs:alternative test="@kind='string'" type="messageTypeString"/>
      <xs:alternative test="@kind='base64'" type="messageTypeBase64"/>
      <xs:alternative test="@kind='binary'" type="messageTypeBase64"/>
      <xs:alternative test="@kind='xml'"    type="messageTypeXML"/>
      <xs:alternative test="@kind='XML'"    type="messageTypeXML"/>
    </xs:element>
  </xs:sequence>
</xs:complexType>

<xs:complexType name="R">
  <xs:complexContent>
    <xs:restriction base="B">
      <xs:sequence>
        <xs:element name="message" type="messageType">
          <xs:alternative test="@kind='string'" type="messageTypeString"/>
          <xs:alternative                       type="xs:error"/>
        </xs:element>
      </xs:sequence>
    </xs:restriction>
  </xs:complexContent>
</xs:complexType>

<p xsi:type="R">
 <e a="5" b="2">
   <t2 />
 </e>
</p>

void process-element(Element e) {

  ...

  Type T = get-current-type(); // e's parent type

  TypeTable TTT = get-context-determined-type-table(e, T);
  int i = evaluate-type-table(e, TTT);
  Type ST = TTT.get-alternative(i).getType();

  boolean error = false;

  // walk on the derivation chain
  while (T is not xs:anyType and !error) do {

    Type B = T.base;
    TypeTable TTB = get-context-determined-type-table(e, B);
    int j = evaluate-type-table(e, TTB);
    Type SB = TTB.getAlternative(j).getType();

    if (validly-substitutable-as-restriction(ST, SB)) {
      T = B;
      ST = SB;
    } else {
      // CTSR violation
      error = true;
      report-schema-error("vr-cta-substitutable");
    }
  }

  ...

}

Optimized Cartesian Product

In this section we present our solution to the problem of the derivation by restriction in presence of conditional declarations. We call it Optimized Cartesian Product (OCP). From the expressivity point of view, our proposal is meant to be fully equivalent to Runt-Time Check and Cartesian Product. While being inspired by CP (and hence its name), it can also be seen as an RTC optimization.

// visits a type of the schema type hierarchy
void visit-type(Type T) {

  // annotate each context-determined Type Table within the current type
  for each QName name in tt-mapT.domain {
    annotate-type-table(tt-mapT(name));
  }

  // recursive call
  for each Type D derived from T do {
    visit-type(D);
  }
}

// annotates a context-determined Type Table
void annotate-type-table(TypeTable ttr) {
  for each int i s.t. 1 <= i <= ttr.size {
    // build the error condition for the current alternative
    Expression expr = build-error-condition(ttr, i);
    // simplify the error condition
    expr = simplify(expr);
    // annotate the current alternative with the simplified condition
    ttr.get-alternative(i).error-condition = expr;
  }
}

// builds an error condition for a Type Table alternative
Expression build-error-condition(TypeTable ttr, int i) {

  // get the base Type Table
  TypeTable ttb = ttr.base;
  if (ttb is absent) {
    return Expression.FALSE; // In such a case no CTSR violation may occur
  } else {
    return build-error-condition_aux(ttr, ttb, i, Expression.FALSE, 1, STATE_OR);
  }
}

Expression build-error-condition_aux(TypeTable ttr, TypeTable ttb, int i, Expression left, int j, short state) {
  if (j > ttb.size) {
    return left;
  } else {

    Expression a;
    if (j == ttb.size) {
      a = Expression.TRUE;
    } else {
      a = ttb.get-alternative(j).getTest();
    }

    Expression right;

    Type r = ttr.get-alternative(i).getType();
    Type b = ttb.get-alternative(j).getType();

    if (r validly restricts b) {
      NotExpression negatedLiteral = new NotExpression(a);
      right = build-error-condition_aux(ttr, ttb, i, negatedLiteral, j + 1, STATE_AND);
    } else {
      right = build-error-condition_aux(ttr, ttb, i, a, j + 1, STATE_OR);
    }

    if (state == STATE_OR) {
      return new OrExpression(left, right);
    } else { state == STATE_AND
      return new AndExpression(left, right);
    }
  }
}

void process-element(Element e) {

  ...

  // e's parent type
  Type T = current-type();

  // get the context determined Type Table for e
  TypeTable tt = tt-mapT(e);

  // evaluate the type table 
  int i = evaluate-type-table(e, tt);

  if (!check-CTSR(e, tt, i)) {
    report-schema-error("vr-cta-substitutable");
  }

  ...

}

boolean check-CTSR(Element e, TypeTable ttr, int i) {

  Alternative alt = ttr.get-alternative(i);
  Expression err-epxr = alt.error-condition;

  if (evaluate-error-condition(e, err-expr)) {
    return false;
  } else {
    TypeTable ttb = ttr.base;
    if (ttb is absent) {
      return true; // implicitly handles the xs:anyType case
    } else {
      int j = evaluate-type-table(e, ttb);

      // recursive call
      return check-CTSR(e, ttb, j);
    }
  }
}

<messages xsi:type="R">
  <message kind="string">
    ...
  </message>
  <message kind="binary">
    ...
  </message>
</messages>

Comparing CP, OCP, and RTC

In this section we provide a comparison among the main techniques discussed so far: Optimized Cartesian Product, Run-Time Check, and Cartesian Product. The comparison focuses on the number of XPath predicates evaluated at run-time. Before starting, let us first fix some notations. Let:

Both OCP and RTC evaluate TT_k in order to decide which type alternative E has to be assigned. Clearly, both techniques evaluate the same XPath predicates of TT_k. The number of evaluated XPath predicates ranges from 1 to d_k.

On the other hand, CP evaluates TT'_k. If, for any i between 1 and k, E satisfies the first alternative of TT_i, CP is assigned the first alternative of TT_k, and thus the condition of that alternative only is evaluated. However, that condition is the conjunction of k XPath predicates. So in the best case, CP evaluates k XPath predicates. But if for every i between 1 and k E satisfies the last alternative of TT_i, than CP has to process every alternative of TT'_k. It means that it has to evaluate d₁ ⋅ ... ⋅ d_k conditions, where each condition is the conjunction of k XPath predicates.

After the TT'_k evaluation, CP already knows whether E and T satisfy CTSR without the need to walk on the derivation chain: if TT'_k selected type error then CTSR is violated, otherwise CTSR is satisfied. The problem is that the evaluation of TT'_k might be very expensive.

On the other hand, after the TT_k evaluation, both OCP and RTC execute further operations. OCP evaluates the error condition linked to the alternative returned by TT_k, while RTC evaluates TT_k-1. Thus, for the purposes of our comparison, it is important to understand whether evaluating the error condition is more or less expensive than evaluating TT_k-1. In order deal with a clearer notation, we temporarily rename some variables:

We denote the TT_R alternatives by <r₁, R₁>, ..., <r_n, R_n>; and the TT_B alternatives by <b₁, B₁>, ..., <b_m, B_m>. Moreover, let i be the (index of the) alternative selected by TT_R. We denote the error condition associated to that alternative by err_i.

As already observed in Section “OCP Static Phase”, err_i is a boolean expression over the XPath predicates (here called atoms) of TT_B. Assuming the simplification process did not rewrite it, err_i contains each of the m atoms of TT_B.

OCP Error Condition Example: OCP Error Condition Example

Structure for the error condition not(@kind='string') and (@kind='base64' or (@kind='binary' or (@kind='xml' or (@kind='XML' or FALSE)))). XPath predicates have been abbreviated for conciseness reasons.

At this point it is important to study the structure of a generic error expression err_i. As also shown in Figure “OCP Error Condition Example”, an error condition has a fixed structure: for each or (and) operator, its left operand is always a (negated) atom, while its right operand is either another binary operator, or FALSE (TRUE). Moreover, we can observe that the atoms appear in the same order they appear in TT_B.

It is easy to implement an error condition evaluator as a lazy boolean evaluator: for any input binary operator it always evaluates the left operand first, and it evaluates the right operand only if necessary. The atoms of err_i actually evaluated by such a boolean evaluator are exactly the same as those evaluated by RTC to decide the TT_B selected type.

For instance, suppose that for a given j our E element does not satisfy none of b₁, ..., b_j-1, and it does satisfy b_j. RTC evaluates b₁, ...,b_j. Also our technique evaluates those predicates, and it does not evaluate further ones. Indeed within err_i, b_j appears either in negated form as left operand of an and operator, or directly as left operand of an or operator (it depends on whether or not R_i is validly substitutable as restriction for B_j). In either case, the err_i evaluation stops before processing the right operand.

Thus we can conclude that even if it is not possible to simplify err_i, OCP and RTC are equivalent in terms of evaluated atoms. But there are cases in which err_i is simplified by the rewriting rules described in Section “OCP Static Phase”. Indeed, if there exists a j such that either

or

then the simplification process removes from err_i the atmos b_j+1, ..., b_m.

In such cases, if E does not satisfy any of the predicates b₁, ..., b_j+k, for some k, then OCP does not need to evaluate the k atoms b_j+1, ..., b_j+k in order to decide whether CTSR is satisfied or not. On the other hand, RTC does evaluate those atoms, because it has to find the type actually selected by TT_B.

Thus, we can conclude that on a single step of a derivation chain, OCP evaluates a number of predicates less than or equal to the number of predicates evaluated by RTC.

However, as can be noted from the formulas shown in Equations “RTC algorithm upper-bound” and “OCP run-time phase upper-bound”, OCP might evaluate twice the same atoms. Coming back to the notation introduced early in this section, if E does not satisfy the error condition of the alternative selected by TT_k, then OCP has to evaluate TT_k-1. But as the error condition previously processed was built on the atoms of TT_k-1, it is clear that some predicates of TT_k-1 might be processed twice.

However, it is possible to ease such an additional cost if during the processing of an error condition, the result of each atom evaluation is stored in some data structure. In this way, an XPath predicate is actually evaluated only if it has not been evaluated yet.

So we conclude that for a given derivation chain, OCP evaluates a number of XPath predicates less than or equal to the number of XPath predicates RTC evaluates.

Implementation

We realized a prototype implementation of Optimized Cartesian Product, thus demonstrating its feasibility. We implemented it in Java within Xerces [Xerces]. Our prototype patches Xerces under three aspects:

As Xerces is an XML parser for XSD 1.0, it does not handle 1.1-specific constructs. Our prototype modifies the Xerces modules delegated to the construction of schema components (package org.apache.xerces.impl.xs.traversers). It also modifies the Xerces implementation of the XML Schema API [XML Schema API], in order to represent type alternative components, and to give element declarations awareness of their Type Tables (packages org.apache.xerces.xs and org.apache.xerces.impl.xs).

The OCP static phase is implemented within a separated package it.unibo.cs.cta. The code for the error condition construction is within the class it.unibo.cs.cta.preprocessor.impl.ErrorConditionBuilder. Such a class processes an input XSD schema, associating each type with a map. That map is our implementation of tt-map^T. Indeed, it associates element names to context-determined Type Tables. ErrorConditionBuilder also annotates each context-determined Type Table with its error conditions. Error conditions are built directly using the algorithm described in Section “OCP Static Phase”. The classes handling error conditions are within the package it.unibo.cs.cta.errorexpr. In particular, the simplification of error conditions is implemented by ErrorExpressionSimplifier, while their evaluation is implemented by ErrorExpressionEvaluator.

The static phase is delegated to a pre-processor invoked when a schema document is loaded. In order to invoke it, the simple and compact code below is used:

// instantiation 
PreprocessorFactory pf = PreprocessorFactory.getInstance();
fPreprocessor = pf.createPreprocessorSequence(
    new String[]{"ErrorConditionBuilder"}
    );
// invocation on an XS Model
fPreprocessor.processModel(model);

The static phase result (i.e., association between types and maps) is read calling the pre-processor method getStateByName("type-table-map").

The OCP run-time phase is implemented within the class org.apache.xerces.impl.xs.OptimizedCTAXMLSchemaValidator, a patched version of the original XSD validator provided by Xerces. In particular, the code for the CTSR verification is within the method handleStartElement. XPath predicates are evaluated using the interfaces in javax.xml.xpath. Currently, our prototype does not check whether an XPath predicate has already been evaluated. Thus, as observed in Section “Comparing CP, OCP, and RTC”, an XPath predicate might be evaluated twice for the same element.

Our prototype is meant to prove the OCP feasibility, and as such it is not aimed to be XSD 1.1 conformant. In particular it has some limitations, the most important of which are:

We also developed a small test suite for OCP. It can be run through a simple graphic interface. Source code and jars are available from http://tesi.fabio.web.cs.unibo.it/Tesi/OptimizedCartesianProduct.

Related Works

Among the most known validation languages (DTD [XML 1.1], RELAX NG [RELAX NG ISO specification], Schematron [Schematron ISO specification], DSD [DSD 2.0], etc), the problem of verifying the subtype relation in presence of conditional declarations is very specific to XSD 1.1. Indeed, although there exist at least one language, DSD, permitting the definition of conditional content models, that language is not type-based, and consequently nor it has any concept of type derivation. We do not know works about restriction checking in presence of conditional declarations.

However, there exist works on the problem of verifying whether an XSD 1.0 type is a legal restriction of another type [H. S. Thompson, and R. Tobin, 2003], [M. Fuchs, and A. Brown, 2003], [C. M. Sperberg-McQueen, 2005]. Those works propose techniques to statically verify whether a type accepts a subset of what the base type accepts. On the same line, Neven et al present theoretical results about some basic decision problems concerning schemas, among which the problem of testing for inclusion of schemas [W. Martens, F. Neven, and T. Schwentick, 2005].

Conclusions

In XSD 1.1, the presence of conditional declarations increases the difficulty in verifying whether a type is a legal restriction of its base. We discussed about three main approaches to the problem: CTA usage limitation, run-time verification, and hybrid verification. Solutions of the first kind ensure it is possible to statically verify whether a type is a legal restriction of its base, but at the cost of limiting the CTA expressivity. Solutions of both second and third kinds allow the highest degree of expressivity, but they may recognize as legal restriction also a type accepting something its base rejects. They throw an error only for those instance documents actually proving that a type is not a legal restriction of its base. Hybrid solutions are meant to precompute during the static phase some information that might decrease the work to be done at run-time.

In particular, we described the solution adopted by the XSD current draft, which follows a run-time approach described within the specs by the Conditional Type Substitutable in Restriction (CTSR) constraint. We discussed about an algorithm verifying CTSR, and we called it Run-Time Check (RTC). Then we proposed an alternative solution to RTC, named Optimized Cartesian Product (OCP). OCP is a hybrid solution. Its idea is to analyze conditional declarations in order to statically decide which XPath predicates can be ignored at run-time. We showed as, contrary to Cartesian Product (CP) - another hybrid solution OCP can be seen as an optimization of - the OCP static analysis cost is perfectly acceptable.

We than compared the RTC, OCP and CP techniques, focusing on the number of XPath predicates evaluated at run-time. We showed as CP is the worst technique, as it inherits from the static phase a high volume of information that might heavily slow down the run-time phase. We also showed that although OCP might process the same alternatives twice, storing the XPath predicate evaluation results, we can assert that OCP evaluates a number of predicates less than or equal to the number of predicates RTC evaluates.

An interesting future work is the experimental comparison among RTC, OCP and CP on a base of real schema documents. Moreover it is interesting to improve our error condition simplification process. For instance, our simplification rules are not able to rewrite expressions like not(@a = 'v1') and (@a = 'v2') into (@a = 'v2'). There are also error conditions that are clearly unsatisfiable when associated to a particular alternative. For instance, if the alternative predicate is (@a = 'v1') and the error condition is (@a = 'v2'), it is clear that the error condition will never be satisfied. Improving the simplification rule set should increase the number of situations in which OCP is preferable to RTC.

Acknowledgements

We would like to thank Stefano Zacchiroli for the technical discussions we had during the design of the Optimized Cartesian Product technique, the anonymous reviewers for their comments, and the XML Schema Working Group for the several and inspiring discussions on the topics covered by this paper.