ShEx/CurrentDiscussion/StateBased
Obsolete - please see ShapeMap Spec
'or' operation choosing between inclusive and exclusive or -> SOLVED
This discussion related to the definition of the And and Or Truth Tables. See tables in [1] and ValidationCode#Truth_tables for the current definition in the validation script.
The definition of the And seems to be Ok, however the definition of the Or table raises discussion.
For this discussion we were thinking of 2 types of or 'inclusive(OR)' or 'exclusive(XOR)', but we have chosen the exclusive(XOR) type which matches the one in NG Relax.
For this discussion we defined the following use cases, with associated SHEX definition(With the solution we think it should contain).
1. A user_name and given_name must be given
USER {
user_name xsd:string
given_name xsd:string
}
2. A user_name, given_name or family_name must be given but not a combination of them and not more then one
USER {
(user_name xsd:string | given_name xsd:string | family_name xsd:tring)
}
3. A user_name or given_name must be given, both my be given, but not more then one for each of them
USER {
((user_name xsd:string,
given_name xsd:string?) |
given_name xsd:string)
}
4. A user_name or given_name must be given, any number or combinations are allowed
USER {
((user_name xsd:string+,
given_name xsd:string*) |
given_name xsd:string+)
}
5. Multiple user_name's or given_name's must be given, but the combination of user_name and given_name are not allowed
USER {
(user_name xsd:string+ | given_name xsd:string+)
}
6. Either give a fullname or set that must have a one or more givenNames with only one family name
USER {
(foaf:fullname xsd:string, !foaf:givenName xsd:string+, !foaf:familyName xsd:string+) |
(foaf:givenName xsd:string+, foaf:familyName xsd:string, !foaf:fullname xsd:string+)
}
If we would have chosen for an inclusive or then each item in a or rule group passing will increase the cardinality of the group by 1. However, a and rule group can not have a cardinality of more then 1 as it is impossible to group items in an unordered structure. Making special exceptions for an or rule group will make things complex and break down the mathematical logics. So this means as soon 2 or more items are matching in a or rule group it fails and so its logic actually becomes the same as an exclusive or.
Using this solution we can solve most uses cases however, use case 3 can not be solved with the following data
ex:user1 ex:user_name "p13t" ; ex:given_name "jan" .
USER {
((user_name xsd:string -> PASS,
given_name xsd:string? -> PASS) -> PASS|
given_name xsd:string -> PASS) -> ERROR -> FAIL
}
However using the ! operator we solve it with the following definition
USER {
((user_name xsd:string,
given_name xsd:string?) |
(given_name xsd:string,
!given_name xsd:string+))
}
If some one can think up a (other) case that can not be solved with the exclusive or please add it as use case 7.
So the final logic tables becomes like as taken from Eric's definition
OrRuleGroup.truthTable = ...
| Or | NONE | OPEN | FAIL | PASS | ERROR |
|---|---|---|---|---|---|
| NONE | NONE | OPEN | NONE | PASS | ERROR |
| OPEN | OPEN | OPEN | OPEN | PASS | ERROR |
| FAIL | NONE | OPEN | FAIL | PASS | ERROR |
| PASS | PASS | PASS | PASS | ERROR | ERROR |
| ERROR | ERROR | ERROR | ERROR | ERROR | ERROR |
AndRuleGroup.truthTable = ...
| Seq | NONE | OPEN | FAIL | PASS | ERROR |
|---|---|---|---|---|---|
| NONE | NONE | NONE | FAIL | FAIL* | ERROR |
| OPEN | NONE | OPEN | FAIL | PASS | ERROR |
| FAIL | FAIL | FAIL | FAIL | FAIL | ERROR |
| PASS | FAIL* | PASS | FAIL | PASS | ERROR |
| ERROR | ERROR | ERROR | ERROR | ERROR | ERROR |
As a group can be either optional or present once we have the following group summarization logic
groupSummary =
| Seq | ? | 1 |
|---|---|---|
| NONE | OPEN | NONE |
| OPEN | OPEN | OPEN |
| FAIL | FAIL | FAIL |
| PASS | PASS | PASS |
| ERROR | ERROR | ERROR |
Summary used for the root result
shapeSummary =
| Seq | |
|---|---|
| NONE | FAIL |
| OPEN | PASS |
| FAIL | FAIL |
| PASS | PASS |
| ERROR | FAIL |
Discussion on ERROR state behavior
The or operator is an exclusive or (xor).
If we would use the 'real' xor operation then any input:
(a|b|c) == ((a|b)|c) == (a|(b|c)) == ((a|c)|b)
and would
(a|b|c) <- abc -> result a PASS: 1 xor 1 xor 1 = 1 (a|b|c) <- ac -> result a FAIL: 1 xor 0 xor 1 = 0
However we would like to have exclusive or that is only valid in only one of its member is true. So that definition becomes
sum|i=0,i=N|(item_i == true ? 1 : 0) == 1 (sorry how can I include math on this wiki)
and result becomes
(a|b|c) <- abc -> result a FAIL as 1 + 1 + 1 != 1 more then 1 member i
Then with this definition
(a|b|c) != ((a|b)|c) != (a|(b|c)) != ((a|c)|b)
Which is fine to my opinion as its adds more expressive power to the language.
Note that for N == 2
(sum|i=0,i=N|(item_i == true ? 1 : 0) == 1) == (item_1 xor item_2)
Instead of summing all the matching items we can stop as soon we reach 2 and set the state to ERROR.
Then if we consider that each item(being a arc or subgroup) in a rule group to either results NONE, OPEN, PASS, FAIL. Then we can convertthe ERROR state to FAIL after matching a subgroup. So
groupSummary =
| Seq | ? | 1 |
|---|---|---|
| NONE | OPEN | NONE |
| OPEN | OPEN | OPEN |
| FAIL | FAIL | FAIL |
| PASS | PASS | PASS |
| ERROR | FAIL | FAIL |
- solution 1
Then we get the following result expect
(a|b)|c <- abc = PASS (a|b)|c <- ABc = PASS a|c <- Ac = PASS ((a|b)&c)|d) <- ABd = PASS ((a|b)&c)|d) <- abd = PASS ((a|b)|(c|d)) <- abc = PASS #quircky or not quircky -> at least (a|b|c) != ((a|b)|c) != (a|(b|c)) != ((a|c)|b) (a|b|c|d) <- abc = FAIL
- solution 2
However if we preserve the error state as defined in eric tables it will become (uses tables as given above)
(a|b)|c <- abc = FAIL #feels a bit quircky, but is acceptable (a|b)|c <- ABc = PASS a|c <- Ac = PASS ((a|b)&c)|d) <- ABd = PASS ((a|b)&c)|d) <- abd = FAIL #feels a bit quircky, but is acceptable ((a|b)|(c|d)) <- abc = FAIL (a|b|c|d) <- abc = FAIL
To my opinion both option are acceptable, however when we start including the effects of the negation(!) operation then I think its better to stick to the first solution. See negation solution below.
Negative rules
Declare that a node does not have a given arc or rule. For example, declare that a concept does not have 'foaf:knows' property.
<concept> { ! foaf:knows . }
Negating arc is strait forward, however we can also think about negating complete sub groups. However we do negate complete groups we have to consider negation of the 5 states
groupNegate =
| Seq | |
|---|---|
| NONE | PASS |
| OPEN | FAIL |
| FAIL | PASS |
| PASS | FAIL |
| ERROR | PASS |
If we take the first solution in the Discussion on ERROR state behavior we get
!(a|b)|c == !(!a|!b)|c == ((a|b)|!c) != (a|b|!c) !(a|b)|c <- ["ac","ab","bc","Abc",""] -> all pass ,["c","ABc","a","b"] -> all fail !(!a|!b)|c <- ["ac","ab","bc","Abc",""] -> all pass ,["c","ABc","a","b"] -> all fail ((a|b)|!c) <- ["ac","ab","bc","Abc",""] -> all pass ,["c","ABc","a","b"] -> all fail
Different results as expected
(a|b|!c) <- ["ac","bc","Abc",""] -> all pass ,["ab"*,"c","ABc","a","b"] -> all fail *different result
Open discussion point: Should OPEN negate to FAIL?
Further example behavior (examples from olivier):
1) forbid a and be to appear cojointly
<XXX>{
.... ,
! (:a xsd:string+, :b xsd:string+) ,
...
}
2) forbid any a's and b's
<XXX>{
.... ,
! :a xsd:string+,
! :b xsd:string+,
....
}
3) forbid two a's and one b
<XXX>{
.... ,
! (:a xsd:string{2}, :b xsd:string),
....
}
4) accept any combination except when two a's and one b
<XXX>{
.... ,
(:a xsd:string*, :b xsd:string*) ! (:a xsd:string{2}, :b xsd:string),
....
}