Shape Expressions + Extends discussions

--- tags: - ShEx - extends --- Shape Expressions + Extends 2020-12-18 =============================== # Meeting 2023/07/11 - Extends between Valuesets... - Proposal FINAL + EXTENDABLE: - Triples/neighbourhood of a node - Shapes default to `EXTENDABLE` - Unless marked as `FINAL` - Node constraints - We assume every node constraint non-extandable - Unless marked as `EXTENDABLE` - Proposal FINAL - Triples/neighbourhood of a node - Shapes default to extendable - Unless marked as `FINAL` - Node constraints - We assume every node constraint extandable - Unless marked as `FINAL` - Consequences - Pros: - We only need one keyword (FINAL) - A bit more symmetric design where shapes are extendable. - Cons: - good modeling would have most NCs marked FINAL ## Extends on non-Shapes (2023-11-29) Extending shapes and node-constraints Extends = OR for node-constraints and each-of shapes ``` -- Original schema <S'> { :p1 @<Svs> } # crop shape - includes p1 = harvestMethod @<HarvetMethodValueSet> <Svs> [ :V1 :V2 ] # hasvest method value set -- Extended schema <T'> EXTENDS @<S'> # cotton shape { :p2 . ; :p3 . } # couple more props AND { :p1 @<Tvs> } AND NOT @<Svs> # dance to say that harvestMethod MUST be in the <T> extension of <S> <Tvs> EXTENDS @<Svs> [ :V3 ] # cotton value set <U'> EXTENDS @<S'> # soybean shape { :p4 . ; :p5 . } AND { :p1 NOT [ :v3 ] } ``` translated to ShEx 2.0: ``` <T'> { :p1 /* @<S> OR */ @<T> ; # this comes from S' :p2 . ; :p3 . } AND { :p1 [ :V1 :V2 ] OR [ :V3 ] # this comes from @< } ``` Data (Turtle): ``` <myT'> :p1 :V3 ; :p2 2 ; :p3 true . ``` ShapeMap: \<myT'>@\<T'> Screw case Data (Turtle): ``` <myU'> :p1 :V3 ; :p4 "x" ; :p5 rdf:nil . ``` ShapeMap: \<myU'>@\<U'> Template [template](https://github.com/ericprud/AMIA-2023/blob/main/playground/manifests/schemas/Patient-name-templates.shex), [flattened](https://github.com/ericprud/AMIA-2023/blob/main/playground/manifests/schemas/Patient-name.shex) ### previous meeting Idea about having Shape-Diffs, example: ``` <CottonShape> OVERRIDES @<Shape>: - @<Shape>~<harvetMethod> + :harvestMethod @<HarvestMethod> OR @<CottonHarvestMethod> ! @<Shape>~<harvetMethod> @<HarvestMethod> OR @<CottonHarvestMethod> ``` A shape is a node constraint + triple expression Discussion between using a keyword `Extendable` vs `Final` - Proposal 1: every node constraint is final unless someone declares marks it as `extendable` - Proposal 2: every node constraint is extendable unless someone marks them as `final` Use case of harvest method ``` <Sample> { :harvestMethod [ :M1 :M2 ] * } <CottonSample> extends @<Sample> { :harvestMethod [ :CM1 :CM2 ] * } --- <cottonData1> :harvestMethod :M1, :CM1 . ``` ericP's previous model ``` <Sample> { :status IRI AND @<StatusCode> ; :harvestMethod IRI AND EXTENDABLE @<HarvestMethods> * # or extendable below } <StatusCode> ["OK" "Fine" "Fab"] EXTENDABLE <HarvestMethods> [ :M1 :M2 ] # or in valueExpr <CottonSample> EXTENDS @<Sample> { ... } # AND :harvestMethod <CottonHarvestMethods> extends @<HarvestMethods> [ :CM1 :CM2 ] --- # <cd1>@<Sample> <cd1> :harvestMethod :M1, :CM1 . # Pass with CottonSample <cd2> :harvestMethod :CM1 . # Pass using extendable ``` A Shape A constrains the possible values of a node a neighborhood partition ``` <A> { :p0 xsd:integer } AND { :p0 maxincludes 10; :p1 . ; :p2 . } extends @<A> IRI AND { ... } <C> EXTENDS @<A> { :p0 xsd:string } AND { :p0 [9 11] } ``` ```turtle <myC> :p0 9, "asdf" . ``` # Restricts 11/12/2020 ```turtle <Obs> { fhir:id . ; fhir:component { fhir:code . } * } # A BP restricts that to two specific components. <BP> RESTRICTS @<Obs> { fhir:component { fhir:code "systolic" } ; fhir:component { fhir:code "diastolic" } ; } # A PostureObs as one component <PostureObs> RESTRICTS @<Obs>{ fhir:component { fhir:code "posture" } ; } # A PostureBP has three components: <PostureBP> EXTENDS @<BP> EXTENDS @<PostureObs> { } ``` # Thoughts on Extends and restricts (Iovka on 10/12 and on 12/12) ## On definition of children and descendants ``` l0 -> se0 AND { te0 } l1 -> se1 AND extends @l0 { te1 } ``` In the above example, we do not want to say that l1 is child of l0 because d(l1) is not the extendee shape. However, `extends @l0 { te1 }` is a Shape that extends the ShapeExpression d(l0). So we should be able to say that `extends @l0 { te1 }` is a child of `se0 AND { te0 }` **Proposition:** The children and descendant relations are defined on Shapes, not on shape labels. A shape hierarchy is a DAG which roots can be ShapeExpressions, but which innern nodes and leaves are Shapes. ## On "has a single Shape" We considered that ShapeExpression can be extended only if it has a single Shape (so that the "mentioned" properties are well identified as the properties that appear in the TripleExpresson of that Shape). However, a Shape can extend another Shape, in which case it automatically has two TripleExpressions. ``` l0 -> se0 AND { te0 } # has only one TripleExpression te0 l1 -> extends @l1 { te1 } # has two TripleExpressions, te0 and te1 l2 -> extends @l1 { te2 } # allowed ? l3 -> restricts @l1 { te3 } # allowed ? ``` Above, - can we extend on l1 ? - can we restrict on l1 ? - which propositions are allowed in te3 ? those of te0, of te1, or of both ? # Meeting 9/Dec/2020 ## Adding a restricts keyword ``` abstract/concrete shape labels extends @l s restricts @l s EXTENDS @l {} AND {pz from @l} ``` - d(l) has only one shape (ie only one triple expression) - restricts: the predicates of s must belong d(@l) - Semantics `restricts @l s` = `@l AND s` + - Children of a label @l l' such that d(l') = extends @l s or d(l') = restricts @l s ``` <Person> { <name> ... .... } <user> restricts @<person> { ... m ``` ``` <Person> { # has 2 shapes -> cannot extend and cannot restrict <name> ... .... } AND { <email> ... } <Person> IRI AND { # has 1 shape -> can extend and can restrict <name> ... } <user> extends @<person> { => forbidden ? ... } <user> restricts @<person> { => forbidden ... } ``` ``` <Person> { <name> . } <User> extends @<Person> CLOSED { email IRI } <User1> extends @<Person> { email IRI } ``` Possibility to avoid extends... ``` s ::= CLOSED? {(@l; | epsilon); te} s ::= CLOSED? {(@l;)* te} Then, we should define this: @l ; te s ::= CLOSED ? (EXTENDS @l)* {te} s ::= CLOSED ? e* {te } e :: extends @l Then, we should define this: extends l te ``` 4 possibilities: - extend a closed shape with an open one - `person closed { <n> . }`, `user extends @person { <e> .}` - extend a closed shape with a closed shape - `person closed {}`, `user extends @person closed {}` - extend an open shape with a closed one - `person {}`, `user extends @person closed {}` - extend an open shape with an open shape - `person {}`, `user extends @person {}` - We - extend a closed shape with an open one - `person closed extra <n> { <n> [ 1 2 ] }` - `user extends @person { <e> .}` - extend a closed shape with a closed shape - `person closed extra <n> { <n> [1 2 ]}` - `user extends @person closed { <n> }` - extend an open shape with a closed one - `person {}`, `user extends @person closed {}` - extend an open shape with an open shape - `person {}`, `user extends @person {}` - We Data: ``` T1 <alice> name "Alice" . T2 <alice> knows <bob> . T3 <alice> email 23 . T4 <alice> :foo 4 . ``` | @Person | local | | -- | -- | | T1 | T2, T3, T4 | | T1, T4 | T2, T3 | try T1,T4 against `CLOSED @<Person>`, # Translation of ShEx+extends to ShEx ```turtle <S1> {<p1>.} <S2> EXTENDS @<S1> {<p2>.} <S3> EXTENDS @<S1> {<p3>.} ABSTRACT <S4> EXTENDS @<S2> EXTENDS @<S3> {<p4>.} <S5> EXTENDS @<S4> { <p5> @<S1> } Inheritance graph: <S1> / \ <S2> <S3> \ / <S4> | <S5> ``` turns into a schema: ```turtle <S1> @<S1'> OR @<S2'> OR @<S3'> OR @<S5'> <S2> @<S2'> OR @<S5'> <S3> @<S3'> OR @<S5'> <S4> @<S5'> # S4 is abstract so we collect it's descendants only <S5> @<S5'> <S1'> { <p1> . } <S2'> { <p1> . ; <p2> . } <S3'> { <p1> . ; <p3> . } <S5'> { <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> } <S5primtityprime> { ( # EXTENDS S4 ( # EXTENDS S2 ( # EXTENDS S1 <p1> . ) ; <p2> . ) ; ( # EXTENDS S3 ( # EXTENDS S1 <p1> . ) ; <p3> . ) ; <p4> . ) ; <p5> @<S1> } ``` Without adding extra-labels (full-embedding) ``` <S1> { # S1 <p1> . # via S1 } OR { # S2 <p1> . ; # via S1 <p2> . ; # via S2 } OR { # S3 <p1> . ; # via S1 <p3> . ; # via S3 } OR { # S5 <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> ; # via S5 } <S2> { # S2 <p1> . ; # via S1 <p2> . ; # via S2 } OR { # S5 <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> ; # via S5 } <S3> { # S3 <p1> . ; # via S1 <p3> . ; # via S3 } OR { # S5 <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> ; # via S5 } <S4> { # S5. S4 is abstract so we collect it's descendants only <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> ; # via S5 } <S5> { # S5 <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> ; # via S5 } ``` Possible optimization by embedding the shapes in triple expressions... ``` <S5'> { <p1> . ; # via S4,S2,S1 (<p2> . ; # via S4,S2 # <p1> . ; # via S4,S3,S1 # WTF do we do with S3? # <p3> . ; # via S4,S3 (<p4> . ; # via S4 <p5> @<S1>)?)? } ``` ## Meeting Iovka/Eric/Labra 8/Dec/2020 ### Conjunction descendants... ``` <S1> { [1 2 3 ]} <S2> extends @<S1> { <q> [4 5 6 ] } AND { [ 2 3 ] } ``` ``` ok1 2; <q> 4 . ko1 1: <q> 4 . ``` ### ``` <S1> te1 AND te2 <S2> extends @<S1> { te } (L(te1) ∩ L(te2) ) ; L(te) (te1 AND te) ; (te2 AND te) ``` ericP screwin' around: ``` <S1> { [1 2]} AND { [2] } <S2> EXTENDS @<S1> { [3] } ``` => ``` <S1> => <S1'> OR <S2'> <S2> => <S2'> <S1'> { [1 2]} AND { [2] } <S2'> { [1 2]; [3] } AND { [2] ; [3] } ``` Another case: In the next funny example `<S1>` unsatisfiable but we can extend it to make it satisfiable when translating it and we don't want it to be satisfiable... (the translation must honor the operational semantics of testing a partition of the neighborhood) ``` <S1> { [1 2]} AND { [3 4] } <S2> EXTENDS @<S1> { [2 3]+ } ``` could be translated to: ``` <S1> => <S1'> OR <S2'> <S2> => <S2'> <S1'> { [1 2]} AND { [3 4] } <S2'> { [1 2]; [2 3] } AND { [3 4] ; [2 3] } <S2bis> { ( [1 2] & [3 4] ); [2 3] } ``` ( where '&' is a conjunction of REs) data: ``` <n1> 2, 3. ``` ```turtle <S1> {<p1> [1 2] } # AND { <p1> [ 2 3 ]} <S2> EXTENDS @<S1> {<p2>.} <S3> EXTENDS @<S1> {<p3>.} ABSTRACT <S4> EXTENDS @<S2> EXTENDS @S3 {<p4>.} <S5> EXTENDS @<S4> { <p5> @<S1> } Inheritance graph: <S1> / \ <S2> <S3> \ / <S4> | <S5> ``` turns into a schema: ```turtle <S1> @<S1'> OR @<S2'> OR @<S3'> OR @<S5'> <S2> @<S2'> OR @<S5'> <S3> @<S3'> OR @<S5'> <S4> @<S5'> # S4 is abstract so we collect it's descendants only <S5> @<S5'> <S1'> { <p1> [1 2] } AND { <p1> [2 3] } <S2'> { <p1> [1 2] ; <p2> . } AND { <p1> [2 3]; <p2> . } <S3'> { <p1> . ; <p3> . } <S5'> { <p1> . ; # via S4,S2,S1 <p1> . ; # via S4,S3,S1 <p2> . ; # via S4,S2 <p3> . ; # via S4,S3 <p4> . ; # via S4 <p5> @<S1> } ``` ## ericP trying to figure out AND/OR/NOT ```turtle <S1> {<p1>.} <S2> EXTENDS @<S1> {<p2>.} AND /^a/ <S3> {<p3>.} AND /^.b/ <S4> EXTENDS @<S2> {<p4>.} AND EXTENDS @<S3> {} <S5> EXTENDS @<S4> {<p5>.} ``` => ```turtle <S1> @<S1'> OR (@<S2'> AND /^a/) OR S<S4> <S2> (@<S2'> AND /^a/) OR @<S4> <S3> (@<S3'> AND /^.b/) OR @<S4> <S4> (@<S4'> AND /^a/) AND (@<S4"> AND /^.b/) <S5> @<S5'> AND @<S5"> <S1'> { <p1> . } <S2'> { <p1> . ; <p2> . } <S3'> { <p3> . } <S4'> { <p1> . ; <p2> .; <p4> . } <S4"> { <p3> . } <S5'> { <p1> . ; <p2> .; <p4> .; <p5> . } <S5"> { <p3> . ; <p5> . } ``` ## EXTENDS of RESTRICTS 14/Dec/2020 ### diamond schema: ``` <G0> R/ R\ <G1L> <G1R> E\ E/ <G2> <G0> { <p1> . ; <p2> . * } <G1L> RESTRICTS @<G0> { <p2> ["1L1"] ; <p2> ["1L2"] } <G1R> RESTRICTS @<G0> { <p2> ["1R"] } /^http:/ # <X> @<G1L> AND @<G1R> is unsatisfiable, but they can be concatonated: <G2> EXTENDS @<G1L> EXTENDS @<G1R> { <p3> . } # Without RESTRICTS: <G1L> { <p2> ["1L1"] ; <p2> ["1L2"] } <G1R> { <p2> ["1R"] } <G2> @<G0> AND (EXTENDS @<G1L> EXTENDS @<G1R> {}) ``` G2 gets extends the **set** of what it restricts: (\<G1>) i.e. `<G2> EXTENDS @<G0> {} AND @<G1L> ; @<G1R>` => ```= <G2> { <p1> . ; <p2> . * ; <p3> . } AND { <p2> ["1L1"] ; <p2> ["1L2"] ; <p2> ["1R"] } AND /^http:/ ``` Data: ```= <n0> <p1> "0" . <n0> <p2> "1L1" . <n0> <p2> "1L2" . <n0> <p2> "1R" . <n0> <p3> "3" . ``` ### with intermediates: ```jsx <G0> R/ E\ <G1L> <G1R> E| R| <G2L> <G2R> E\ E/ <G3> ``` 17/Dec/2020 Input example that will be converted: ```jsx # lbl| inheritance | triple expression | permitted p2s <G0> { <p1> ["0"] ; <p2> . * } # .* <G1L> RESTRICTS @<G0> { <p2> ["1L1" "1L2"] ; <p2> ["1L3"] } # 1L1|1L2 1L3 <G2L> EXTENDS @<G1L> { <p2> ["2L"] } # 1L1|1L2 1L3 2L <G1R> EXTENDS @<G0> { <p3> ["31" "32"] } # .* <G2R> RESTRICTS @<G1R> { <p2> ["2R"] } # 2R <G3> EXTENDS @<G2L> EXTENDS @<G2R> { <p3> ["3"] } # 1L1|1L2 1L3 2L 2R ``` => ```jsx= <G0¹> @<G0>.sE # .* <G1L¹> @<G0>.sE # 1L1|1L2 1L3 AND @<G1L>.sE <G2L¹> { @<G0>.sE ; @<G2L>.sE } # 1L1|1L2 1L3 2L AND { @<G1L>.sE ; @<G2L>.sE } <G1R¹> { @<G0>.sE ; @<G1R>.sE } # .* <G2R¹> { @<G0>.sE ; @<G1R>.sE } # 2R AND @<G2R>.sE <G3¹> { @<G0>.sE ; @<G2L>.se ; @<G1R>.se ; @<G3>.se} # 1L1|1L2 1L3 2L 2R AND { @<G1L>.se ; @<G2L>.se ; @<G2R>.se ; @<G3>.se } ``` **\<G3¹> as TCs**: 17/dec/2020 Output of conversionof conversion: ```jsx= <G0> { <p1> ["0"] ; <p2> . * } <G1L> { <p1> ["0"] ; <p2> . * } AND { <p2> ["1L1" "1L2"] ; <p2> ["1L3"] } <G2L> { <p1> ["0"] ; <p2> . * ; <p2> ["2L"] } AND { <p2> ["1L1" "1L2"] ; <p2> ["1L3"] ; <p2> ["2L"] } <G1R> { <p1> ["0"] ; <p2> . * ; <p3> ["31" "32"] } <G2R> { <p1> ["0"] ; <p2> . * ; <p3> ["31" "32"] } AND { <p2> ["2R"] } <G3> { <p1> ["0"] ; <p2> . * ; <p2> ["2L"] ; <p3> ["31" "32"] ; <p3> ["3"] } AND { <p2> ["1L1" "1L2"] ; <p2> ["1L3"] ; <p2> ["2L"] ; <p2> ["2R"] ; <p3> ["3"] } ``` **Data**: ```= <n0> <p1> "0" . <n0> <p2> "1L1" . # | "1L2" <n0> <p2> "1L3" . <n0> <p2> "2L" . <n0> <p2> "2R" . <n0> <p3> "3" . ``` ### intermediates2 ```jsx <G0> R/ E\ E\ <G1L> <G1R> \ E| R| \ <G2L> <G2R> \ E\ E/ E\ \ <G3L> <G3M> <G3R> E| R\ E/ R\ E/ R| <G4L> <G4R> ``` 17/Dec/2020 Input example that will be converted: ```jsx # lbl| inheritance | triple expression | permitted p2s <G0> { <p1> ["0"] ; <p2> . * } # .* <G1L> RESTRICTS @<G0> { <p2> ["1L1" "1L2"] ; <p2> ["1L3"] } # 1L1|1L2 1L3 <G2L> EXTENDS @<G1L> { <p2> ["2L"] } # 1L1|1L2 1L3 2L <G1R> EXTENDS @<G0> { <p3> ["31" "32"] } # .* <G2R> RESTRICTS @<G1R> { <p2> ["2R"] } # 2R <G3L> EXTENDS @<G2L> EXTENDS @<G2R> { <p3> ["3L"] } # 1L1|1L2 1L3 2L 2R <G3M> EXTENDS @<G2R> { <p3> ["3M"] } # 2R <G3R> EXTENDS @<G0> { <p3> ["3R"] } # .* <G4L> EXTENDS @<G3L> EXTENDS @<G3M> EXTENDS @<G3R> { } # 1L1|1L2 1L3 2L 2R <G4R> RESTRICTS @<G3L> RESTRICTS @<G3M> RESTRICTS @<G3R> { } # 1L1|1L2 1L3 2L 2R ``` => ```jsx= <G0¹> @<G0>.sE # .* <G1L¹> @<G0>.sE # 1L1|1L2 1L3 AND @<G1L>.sE <G2L¹> { @<G0>.sE ; @<G2L>.sE } # 1L1|1L2 1L3 2L AND { @<G1L>.sE ; @<G2L>.sE } <G1R¹> { @<G0>.sE ; @<G1R>.sE } # .* <G2R¹> { @<G0>.sE ; @<G1R>.sE } # 2R AND @<G2R>.sE <G3¹> { @<G0>.sE ; @<G2L>.se ; @<G1R>.se ; @<G3>.se} # 1L1|1L2 1L3 2L 2R AND { @<G1L>.se ; @<G2L>.se ; @<G2R>.se ; @<G3>.se } ``` **\<G3¹> as TCs**: 17/dec/2020 Output of conversion: ```jsx= ``` **Data**: ```= <n0> <p1> "0" . <n0> <p2> "1L1" . # | "1L2" <n0> <p2> "1L3" . <n0> <p2> "2L" . <n0> <p2> "2R" . <n0> <p3> "3" . ``` ### FHIR vitals Observations TODO ``` <#Observation> { fhir:code .? ; fhir:component { fhir:code . ; fhir:value . }* } # -- super-classes -- ABSTRACT <#Vital> EXTENDS @<#Observation> {} # alias for Obs ABSTRACT <#PostureVital> @<#Vital> AND EXTENDS @<#Posture> {} ABSTRACT <#ReclinedVital> @<#PostureVital> AND EXTENDS @<#Reclined> {} # -- BP -- <#BP> EXTENDS @<#Vital> {} AND { fhir:component { fhir:code ["systolic"] } ; fhir:component { fhir:code ["diastolic"] } } <#PostureBP> EXTENDS @<#BP> EXTENDS @<#PostureVital> { } <#ReclinedBP> EXTENDS @<#BP> EXTENDS @<#ReclinedVital> { } # -- Pulse -- <#Pulse> EXTENDS @<#Vital> {} AND { fhir:code ["pulse"] } <#PosturePulse> EXTENDS @<#Pulse> EXTENDS @<#PostureVital> { } <#ReclinedPulse> EXTENDS @<#Pulse> EXTENDS @<#ReclinedVital> { } # -- postures -- <#Posture> { fhir:component { fhir:code ["posture"] } } <#Reclined> @<#Posture> AND { fhir:component { fhir:code ["posture"] ; fhir:value ["reclined"] } } ``` # Example of children ``` Issue { :reproduced @:Person } :Solved { :solvedDate xsd:date } :SolvedIssue @Solved AND extends @:Issue { :reproduced @Programmer ; } :SolvedIssue -> :Issue :SolvedIssue' extends @:Issue { ... } :SolvedIssue' -> :Issue :X extends @:Issue { :reproduced @Programmer ; } :SolvedIssue @Solved AND @:X ``` ``` :A { :p [ 1 ]} :B @A AND { :p [ 2 ] } :B extends @:A {} AND { :p [ 2 ] } :B -> :A ``` # Unsatisfiable1 No set of triples can satisfy`<Base>`. If we don't test that the partition allocated to `<Base>` is consistent, we allow `<s> :a 2` to satisfy the left conjunct and `<s> :a 3` to satisfy the right conjunct. If we do enforce a consistent partition between the TripleConstraints in `<Ext>` and those in `<Base>`, the ShapeMap below should not be satisfiable. ``` <Base> { :a [1 2]} AND { :a [3 4]} <Ext> extends <Base> { :a [2 3] } Data: <s> :a 2, 3. ShapeMap: <s>@<Ext> ``` ``` SE1: { :a [1 2] } AND { :a [3 4] } TC1: { :a [2 3] } T1: <s> :a 2 --> SE1 !fails 2nd conjunct! T2: <s> :a 3 --> TC1 T1: <s> :a 3 --> SE1 !fails 1st conjunct! T2: <s> :a 2 --> TC1 ∴ <s>@!<Ext> ``` # Satisfiable1 This one is satisfiable. ``` <Base> { :a [1 2]} AND { :a [2 3]} <Ext> extends <Base> { :a [2 3] } Data: <s> :a 2, 3. SE1: { :a [1 2] } AND { :a [2 3] } TC1: { :a [2 3] } T1: <s> :a 2 --> SE1 (succeeds) T2: <s> :a 3 --> TC1 ``` # ExtIsOrthogonal1 The predicates in the extending shape's triple constraints are disjoint from those in the base. This should typify he common use case and should be efficient to process. ``` <Base> CLOSED { :a [1 2]; :b [2 3] } AND { :b [2] } <Ext> extends <Base> { :c [3] } Data: <s> :a 1; :b 20; :c 3. TC1.1 TC1.2 TC2.1 SE1: { :a [1 2]; :b [2 3] AND { :b [2] } TC1.1: :a [1 2] TC1.2: :b [2 3] TC2.1: :b [2] TC9: { :c [2 3] } T1: <s> :a 1; :b 2 --> SE1 (succeeds) T2: <s> :c 3 --> TC1 ``` Here we got stuck figuring out that TC1.2 and TC2.1 could be mapped to the same triple. When looking for a general way to figure that out, the possible partitions seemed to explode. For instance, we could say that every TriplePattern in some conjunct which shared a predicate with a TriplePattern from another conjunct could have a 0 min cardinality. This appeared to be creating a *sketch* of a TripleExpression designed to acquire triples from the partition. Below we appear to have found a more efficient way to derive the sketch. # Sketch algorithm Here we construct a *sketch* by calculating the min and max cardinalities for each predicate mentioned in `<Base>`. We believe this can be extended to include more complex TripleExpressions, e.g. EachOfs with arbitary cardinalities. Given the following declarations: ``` <Base> <BaseDefn> <Ext> extends <Base> <ExtDefn> ``` - For each predicate `p` in `<BaseDefn>` calculate the maximum of the min-cardinality and the minimum of the max-cardinalities of `p`. `EXTRA` forces unlimted max cardinality. Disjunction forces that predicat's minimum cardinality toT 0. - Create an EachOf expression of all the predicates - Obtain the subgraph `g` that matches this expression - Validate `<Base>` with subgraph `g` - Validate the `<ExtDefn>` For [ExtIsOrthogonal1](#ExtIsOrthogonal1), `<Base>`'s sketch is `(:a .; :b .)`, resulting in an effective TripleExpression: ``` { (:a .; // from <Base> :b . ) ON <Base> ; ( :c [2 3] from <Ext> ) } ``` Note that the sketch `(:a .; :b .)` doesn't validate the partition; instead it allocates the triples which are then tested as a neighborhood for the extended shape. While it may be helpful for visualizing/debugging the logic, it's not necessary to materialize the sketch, simply to keep a list of TripleConstraints appearing in the base shapes coupled with their min and max cardinality. We've not explored ShapeNot or ShapeOr. NodeConstraints (on the focus node) seem trivially taken care of. We don't understand [concatenation](https://hackmd.io/LximWmWfT52PmLc0ZddldQ#) well enough to know if this is an efficient implementation of it. # ExtIsOrthogonal2 This is like [ExtIsOrthogonal1](#ExtIsOrthogonal1) but has the start of some experiments with XSD facets instead of value sets. **In Progress**, example not self-consistent. ``` <Base> CLOSED { :a [1 2]; :b [2 3] } AND { :b [2] } <Ext> extends <Base> { :b MinInclusive 40 } Data: <s> :a 1; :b 20; :c 3. SE1: { :a [1 2]; :b xsd:integer {10,20}} AND { :b MinInclusive 18 {15, 25 } } TC1,1: :a [1 2] TC1,2: :b xsd:integer TC2,1: :b MinInclusive 18 TC9: { :c [2 3] } T1: <s> :a 1; :b 20 --> SE1 (succeeds) T2: <s> :c 3 --> TC1 ``` # Naïve Semantics by translation It works in simple cases but passes Unsatisfiable1 (which we don't want). ``` <A> extends { defn1 } AND { defn2 } ``` By translation: ``` <A> { ; defn1 } AND { ; defn2 } ``` The translation for Unsatisfiable1 would be: ``` <Trans> { :a [1 2] ; :a [2 3] } AND { :a [3 4] ; :a [2 3] } ``` # See Also * [concatenation pad](https://hackmd.io/LximWmWfT52PmLc0ZddldQ#)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.