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

Re: Algorithm for computing the cardinality of a simpleType?

From: Xan Gregg <xan.gregg@jmp.com>
Date: Thu, 21 Jul 2005 10:11:51 -0400
Message-Id: <0bb7d12db45e571c9da7628835c2965d@jmp.com>
Cc: <xmlschema-dev@w3.org>
To: "Roger L. Costello" <costello@mitre.org>

Roger,

Computing cardinality of a pattern would be enough to scare me off. 
What is the cardinality of 
0*1*0*2*0*3*0*4*0*5*0*6*0*7*0*8*0*9*8*7*6*5*? If it weren't for leading 
zeros you could just try every possible lexical value and see if it's 
valid.

totalDigits is based on absolute values so it also applies to negative 
numbers. As a result totalDigits of 2 has cardinality 199, not 100.

I think you need to worry more about combinations of facets, such as 
min=75 and totalDigits=2. In the example you give,

> <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).

Wouldn't 2 be the correct answer because of the enumeration facet?

Ignoring pattern (hard) and enumeration (easy), my approach would be to 
keep a running range while processing factes:

1. lo = -128, hi = 127
2. minInclusive present => lo = max(lo, minInclusive)
3. maxInclusive present => hi = min(hi, maxInclusive)
4. minExclusive present => lo = max(lo, minExclusive + 1)
5. maxExclusive present => hi = min(hi, maxExclusive - 1)
6. totalDigits present => lo = max(lo, -10^^totalDigits + 1); hi = 
min(hi, 10^^totalDigits - 1)
7. range cardinality = hi - lo + 1

Then apply pattern and enumeration info to compute actual cardinality.

xan
Received on Thursday, 21 July 2005 14:11:58 GMT

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