W3C home > Mailing lists > Public > xmlschema-dev@w3.org > July 2005

Algorithm for computing the cardinality of a simpleType?

From: Roger L. Costello <costello@mitre.org>
Date: Thu, 21 Jul 2005 09:23:09 -0400
Message-Id: <200507211323.j6LDNEY05794@smtp-bedford.mitre.org>
To: <xmlschema-dev@w3.org>, "'Roger L. Costello'" <costello@mitre.org>

Hi Folks,
 
Given a simpleType I want to determine the maximum number of different
values (i.e., the cardinality) permitted by the simpleType.
 
Let's consider an example:
 
<simpleType name="foo">
    <restriction base="byte">
        <minInclusive value="0"/>
        <maxInclusive value="3"/>
    </restriction>
</simpleType>
 
This simpleType permits 4 values: 0, 1, 2, 3.  
Thus, the cardinality of this simpleType is: 4
 
Let's consider another example:
 
<simpleType name="foo">
    <restriction base="byte">
        <enumeration value="12"/>
        <enumeration value="5"/>
        <enumeration value="88"/>
        <enumeration value="47"/>
    </restriction>
</simpleType>

This simpleType permits 4 values: 12, 5, 88, 47.  
Thus, the cardinality of this simpleType is: 4

The above simpleTypes both have the same cardinality.

Let's consider one more example:
 
<simpleType name="foo">
    <restriction base="byte">
        <totalDigits value="2"/>
    </restriction>
</simpleType>

This simpleType permits any 2-digit byte value, i.e., [0-9][0-9]
Thus, the cardinality of this simpleType is: 10^^2 (10 raised to the 2
power) = 100

The byte datatype has these facets:
 
totalDigits
fractionDigits   
pattern   
whiteSpace   
enumeration   
maxInclusive   
maxExclusive   
minInclusive   
minExclusive 

Here is a statement of the problem: Given any simpleType that is a
restriction of the byte datatype, what is its cardinality?

Here is the algorithm that I have developed.  Does it look correct?  Have I
missed anything?

Algorithm for Computing the Cardinality of a byte simpleType

1. Determine the cardinality of each pattern facet. 
       Compute the maximum cardinality of all the pattern facets.
   Done.

2. If there is a minInclusive facet and a maxInclusive facet then
      compute the difference
   Done.

3. If there is a minExclusive facet and a maxExclusive facet then
      compute the difference
   Done.

4. If there is a minInclusive facet and a maxExclusive facet then
      compute the difference
   Done.

5. If there is a minExclusive facet and a maxInclusive facet then
      compute the difference
   Done.

6. If there is a maxInclusive facet then
      compute the difference of the maxInclusive value from -127
   Done.

7. If there is a maxExclusive facet then
      compute the difference of the maxExclusive value from -127
   Done.

8. If there is a minInclusive facet then
      compute the difference of 128 from the maxInclusive value
   Done.

9. If there is a minExclusive facet then
      compute the difference of 128 from the maxExclusive value
   Done.

10. If there is a totalDigits facet then
      compute 10^^totalDigits (10 raised to the power totalDigits)
   Done.

11. If there are enumeration facets then
      count the number of enumeration facets
   Done.

Notice that my algorithm ignores many facet combinations, e.g.,

<simpleType name="foo">
    <restriction base="byte">
        <minInclusive value="0"/>
        <maxInclusive value="3"/>
        <enumeration value="1"/>
        <enumeration value="2"/>
    </restriction>
</simpleType>

My algorithm checks for the combination of minInclusive and maxInclusive
before it checks for enumerations.  For this example my algorithm returns a
cardinality of: 4 (which is correct).

Thus, the order in which I check the facets if very important.  Have I got
the order correct?  Does this algorithm look correct?  Have I missed
anything?

/Roger
Received on Thursday, 21 July 2005 13:23:20 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:14:50 GMT