# 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 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 23:15:29 UTC