From: Eric Prud'hommeaux <eric@w3.org>

Date: Thu, 3 Mar 2016 17:38:23 -0500

To: Iovka Boneva <iovka.boneva@univ-lille1.fr>

Cc: public-shex-dev@w3.org

Message-ID: <20160303223820.GJ24478@w3.org>

Date: Thu, 3 Mar 2016 17:38:23 -0500

To: Iovka Boneva <iovka.boneva@univ-lille1.fr>

Cc: public-shex-dev@w3.org

Message-ID: <20160303223820.GJ24478@w3.org>

This email lays out the current cardinality tests in preparation for adapting them to ShExJ's abstract syntax. The triple expressions in shexj are one of: triple constraint: predicate, inverse, value expression, cardinality allOf: sequence of triple expressions, cardinality someOf: sequence of triple expressions, cardinality inclusion: ref to a shape's triple expression. Currently the permissible cardinality on any of these is {0,∞}. We may restrict the permissible cardinalities on allOfs and containers of allOfs in the future in order to simplify the The ICDT paper gave the membership formula like: Σ: edge labels ∆: set of symbols, possibly in Σ ω: ∆→N: map symbols in ∆ to number of occurrences e.g. w₀ = ⦃a, a, a, c, c⦄ means {a:3, c:2, *:0} I(ε) = [0;∞] I(a[n,m]) = [⌈ω(a)/m⌉;⌊ω(a)/n⌋] 0/∞ = 0 i/∞ = 1 for i ≥ 1 or: I(E₁ ∣ E₂) = I(E₁) ⊕ I(E₂) ⊕: pairwise addition: [n₁;m₁]⊕[n₂;m₂]=[n₁+n₂; m₁+m₂] m+∞ = ∞+m = ∞ and: I(E₁ ∥ E₂) = I(E₁) ∩ I(E₂) [n₁;m₁]∩[n₂;m₂]=[max(n₁,n₂);min(m₁,m₂)] ⎧ [0;∞] if ω∆(E) = ε I(E*) = ⎨ [1;∞] if ω∆(E) ≠ ε and I(E) ≠ 0 ⎩ ∅ otherwise ⎧ [0;0] if ω∆(E) = ε I(E⁺) = ⎨[1;max(I(E))⌉] if ω∆(E) ≠ ε and I(E) ≠ 0 ⎩ ∅ otherwise all ε∥E* are expressed as E⁺ Example: I(a[n,m]) tests <S> { :p . } / { <s> :p true } ∆={:p}, ω={:p→1} I(:p[1,1]) = [⌈1/1⌉;⌊1/1⌋] = [1;1] pass <S> { :p . } / { <s> :q true } ∆={:p}, ω={:p→0} I(:p[1,1]) = [⌈0/1⌉;⌊0/1⌋] = [0;0] fail ?⎧<S> { :p .? } / { <s> :q true } /⎨ ∆={:p}, ω={:p→0} 0⎩ I(:p[0,1]) = [⌈0/1⌉;⌊0/0⌋] = [0;1] pass (adding rule for 0/0=∞) <S> { :p .{2} } / { <s> :p true } ∆={:p}, ω={:p→1} I(:p[2,2]) = [⌈1/2⌉;⌊1/2⌋] = [1;0] fail ⅔⎧<S> { :p .{2,3} } / { <s> :p 1 } /⎨ ∆={:p}, ω={:p→1} 1⎩ I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 } /⎨ ∆={:p}, ω={:p→2} 2⎩ I(:p[2,3]) = [⌈2/3⌉;⌊2/2⌋] = [1;1] pass ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 } /⎨ ∆={:p}, ω={:p→3} 3⎩ I(:p[2,3]) = [⌈3/3⌉;⌊3/2⌋] = [1;2] pass ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 } /⎨ ∆={:p}, ω={:p→4} 4⎩ I(:p[2,3]) = [⌈4/3⌉;⌊4/2⌋] = [2;2] fail ?/0 is really modeled as I(I(:p[1,1]) ∣ I(ε)) below I(ε) tests <S> { } / { <s> :p true } ∆={:p}, ω={} I(ε) = [0;∞] pass ?⎧<S> { :p .? } / { <s> :q true } /⎨ ∆={:p}, ω={:p→0} 0⎩ I(I(:p[1,1]) ∣ I(ε)) = I([0;0] ∣ [0;∞]) = [0;∞] ⅔⎧<S> { :p .{2,3} } / { <s> :p 1 } /⎨ ∆={:p}, ω={:p→1} 1⎩ I(:p[2,3]) = [⌈1/3⌉;⌊1/2⌋] = [1;0] fail ⅔⎧<S> { :p .{2,3} } / { <s> :p 1 } /⎨ ∆={:p}, ω={:p→1} 1⎩ I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) = I(I([⌈1/2⌉;⌊1/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) = I(I([1;0] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;0] ∥ [0;∞])) = I([1;0]) fail ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2 } /⎨ ∆={:p}, ω={:p→2} 2⎩ I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) = I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) = I(I([1;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([1;1] ∥ [0;∞])) = I([1;1]) pass ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3 } /⎨ ∆={:p}, ω={:p→3} 3⎩ I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) = I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) = I(I([2;1] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;1] ∥ [0;∞])) = I([2;1]) fail -- overruns if <s> :p 3 assigned to [2,2] group I(I([⌈2/2⌉;⌊2/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) = I(I([1;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([1;1] ∥ [1;∞])) = I([1;1]) pass -- accepts if <s> :p 3 assigned to I(I(:p[1,1]) ∣ I(ε)) ⅔⎧<S> { :p .{2,3} } / { <s> :p 1,2,3,4 } /⎨ ∆={:p}, ω={:p→3} 4⎩ I(I(I(:p[2,2]) ∥ I(I(:p[1,1]) ∣ I(ε)))) = I(I([⌈4/2⌉;⌊4/2⌋] ∥ I([⌈0/1⌉;⌊0/1⌋] ∣ [0;∞]))) = I(I([2;2] ∥ I([0;0] ∣ [0;∞]))) = I(I([2;2] ∥ [0;∞])) = I([2;2]) fail -- overruns if <s> :p 4 assigned to [2,2] group I(I([⌈3/2⌉;⌊3/2⌋] ∥ I([⌈1/1⌉;⌊1/1⌋] ∣ [0;∞]))) = I(I([2;1] ∥ I([1;1] ∣ [0;∞]))) = I(I([2;1] ∥ [1;∞])) = I([2;1]) pass -- overruns if <s> :p 4 assigned to I(I(:p[1,1]) ∣ I(ε)) ⅔/1, ⅔/2, ⅔/3, ⅔/4 really modeled as I(:p[2,3]) above I'd continue here but I need help understanding ω∆(E) ≠ ε and I(E) ≠ 0. -- -ericP office: +1.617.599.3509 mobile: +33.6.80.80.35.59 (eric@w3.org) Feel free to forward this message to any list for any purpose other than email address distribution. There are subtle nuances encoded in font variation and clever layout which can only be seen by printing this message on high-clay paper.Received on Thursday, 3 March 2016 22:38:39 UTC

*
This archive was generated by hypermail 2.3.1
: Tuesday, 4 June 2019 11:00:16 UTC
*