Issue
Should unbounded occurrences be permitted in an XML Schema?
Two Approaches to Allowing an Unbounded Number of Occurrences
There are two approaches in XML Schemas for allowing an unbounded number of
occurrences. Below I discuss these two approaches. Following that I discuss two
viewpoints on whether unbounded number of occurrences should or should not be
permitted. I then discuss the advantages and disadvantages of each viewpoint.
Finally, I propose a compromise of the two viewpoints.
Allowing Unbounded Occurrences using maxOccurs
The first approach to
allowing an unbounded number of occurrences is to explicitly state that you want
an unbounded number of occurrences by using maxOccurs="unbounded". For example,
the following declaration says that Bookstore can contain an unbounded number of
Book elements:
<element name="Bookstore">
<complexType>
<sequence>
<element name="Book" type="..." maxOccurs="unbounded"/>
</sequence>
</complexType>
</element>
Allowing Unbounded Occurrences using a Recursive Expression
The second approach to allowing an unbounded number of occurrences is less
obvious. Unboundedness occurs implicitly when you create a recursive structure.
In the following example there is no limit to the depth of the Section elements.
That is, a Section can contain a Section which contains a Section which contains
a Section ...
<element name="Section" type="SectionType"/>
<complexType name="SectionType">
<sequence>
<element name="Title" type="..."/>
<element name="Section" type="SectionType"/>
</sequence>
</complexType>
Comparison of the Two Approaches
Both of the above approaches allow an unbounded number of occurrences. Let's
compare the two approaches:
- Explicit vs Implicit: With the first approach you explicitly state
that you are allowing an unbounded number of occurrences. With the second
approach unboundedness is implicit. Although it is obvious in the example
presented, in a large Schema where the recursion extends through many
complexTypes it may not be obvious that an unbounded number of occurrences are
being allowed.
- Ability to "throttle back" on the Number of Occurrences: With the
first approach is it easy to reduce the number of occurrences. If you don't
want an unbounded number of occurrences, and want, say, only 10 occurrences
then you simply specify maxOccurs="10". With the second approach there is no
means to control the depth of the recursion. There is no means to say, "There
cannot be more than 10 deep Section elements".
Permit Unbounded Occurrences or Constrain the Occurrences?
Now that we have seen the two approaches for allowing an unbounded number of
occurrences we return to the main issue: when designing an XML Schema should you
permit an unbounded number of occurrences? There are two viewpoints on this
issue. One viewpoint is that you should design your Schemas to permit an
unbounded occurrences. The other viewpoint is that you should not permit an
unbounded number of occurrences.
To keep the discussion concrete, let's take the above Bookstore Schema as the
example. Suppose that it is decided that Bookstore should not allow more than
30,000 Books. Should the Schema be designed to allow an unbounded number of
Books:
<element name="Bookstore">
<complexType>
<sequence>
<element name="Book" type="..." maxOccurs="unbounded"/>
</sequence>
</complexType>
</element>
Or, should the Schema be designed to explicitly state 30,000 as the
maximum:
<element name="Bookstore">
<complexType>
<sequence>
<element name="Book" type="..." maxOccurs="30000"/>
</sequence>
</complexType>
</element>
Viewpoint 1: Permit an Unbounded Number of Occurrences
This viewpoint says that it's better to use maxOccurs="unbounded".
There is a technical problem with setting maxOccurs="30000". Michael Kay
nicely summarizes the problem: "the classical algorithms for turning grammars
into finite state machines produce very inefficient machines when there are
occurrence limits that are large but finite. Many schema processors break or
consume seriously large amounts of memory if you specify a maxOccurs value
(other than unbounded) that's greater than a couple of hundred." In other words,
a Schema validator will choke if you specify maxOccurs="30000".
If the Bookstore wants, at a later date, to expand to accommodate, say,
35,000 Books then no change will be needed to the Schema.
The example being considered is just one element. A Schema is, of course,
usually comprised of many elements. Suppose that each element is constrained as
precisely as possible. Then a document may be rejected because one element
exceeded its constraints while all other others were within their
constraints.
Viewpoint 2: Constrain the Number of Occurrences
This viewpoint says that it's better to use maxOccurs="30000".
It is important to distinguish between theoretical constraints and
practical constraints. Theoretically, a Bookstore may have an unbounded
number of Books, but for performance/capacity/security reasons this Bookstore
can only handle 30,000 Books.
Another example of the difference between theoretical and practical limits:
theoretically an HTML document may have an infinite number of <p>
elements, but in practice a browser supports only a specific maximum.
Every system has practical constraints. There are many possible reasons for
the constraint such as performance, capacity, or security constraints. The
particulars are irrelevant. What is relevant, however, is that it is guaranteed
that no system is infinite and consequently all systems have practical
constraints.
Expressing the practical limits in an XML Schema are especially important for
Service Level Agreements (SLAs).
So, there are theoretical constraints and there are practical constraints.
And as we've seen, typically the two are not identical. The purpose of an XML
Schema is to express constraints. Which constraints should a Schema express -
theoretical constraints or practical constraints? Viewpoint 2 says that a Schema
should express the practical constraints. Thus, for the Bookstore example, set
maxOccurs="30000".
See Greg Hunt's messages for an excellent discussion of this viewpoint.
Viewpoint 1: Permit an Unbounded Number of Occurrences
-
Advantages
- Schema Validator Efficiency: Schema validators are more efficient
when you use maxOccurs="unbounded" than when you set maxOccurs to a large
number
- Accommodates Growth: as a system is expanded to support larger
amounts of data, there is no need to change the Schema.
-
Disadvantages
- Pushes the Constraint-Checking Problem to Another Part of the
System: if the practical limits are not expressed in the Schema, then
they have to be expressed somewhere else - somewhere less visible, less
maintainable, and with less tool support.
- Vulnerable to Denial of Service Attack: XML guards depend upon an
XML Schema to indicate whether an XML instance document should be allowed to
pass. It will be unable to detect a denial of service attack since the
Schema sets a theoretical limit and not a practical limit.
Viewpoint 2: Constrain the Number of Occurrences
-
Advantages
- Constraints are Visible, Maintainable, and with Tool Support:
since the practical limits are expressed in the Schema, they are visible,
maintainable, and with tool support.
- Prevent Denial of Service Attack: XML guards depend upon an XML
Schema to indicate whether an XML instance document should be allowed to
pass. It will be able to detect a denial of service attack since the Schema
sets a practical limit and not a theoretical limit.
Disadvantages
- Schema Validator is Inefficient: Schema validators are not
efficient when you set maxOccurs to a large number
- Requires Periodic Update: as a system is expanded to support
larger amounts of data, the Schema will need to be updated.
- Exposing System Limits: by setting maxOccurs="30000" you are
giving information to people about the limitations of your system.
Proposal: Constraining Data without the Validator Inefficiencies
As was described above the current implementation of Schema validators are
very inefficient when you specify a large number for the value of maxOccurs. So,
even if you want to express practical limits you cannot, due to this Schema
validator implementation problem.
Here is a proposal to avoid the inefficiency: express the theoretical limits
using XML Schemas and express the practical limits using Schematron assertions.
Let's consider the Bookstore example. Below I show that XML Schemas is to
indicate that Bookstore is comprised of an unbounded number of Books, and I use
Schematron to indicate that the practical limit to the number of Books must not
exceed 30,000:
<element name="Bookstore">
<complexType>
<sequence>
<element name="Book" type="..." maxOccurs="unbounded">
<schematron:assert test="count(Book) <= 30000"/>
</element>
</sequence>
</complexType>
</element>
Comments?
