XSD - XS：所有改寫爲確定性DTD

Question

以下XSD部分給出：

<xs:element name="root"> 
    <xs:complexType> 
     <xs:all> 
      <xs:element minOccurs="1" name="box-type-1"/> 
      <xs:element minOccurs="0" name="box-type-2"/> 
      <xs:element minOccurs="0" name="box-type-3"/> 
      <xs:element minOccurs="0" name="box-type-4"/> 
     </xs:all> 
    </xs:complexType> 
</xs:element> 

[XS：類型無關]

請參閱：https://stackoverflow.com/a/7833274/6805256

鏈接的答案顯示了DTD相當於一個類似的模式但我不能適應它我的需要和精確的情況。

編輯：我刪除了我的問題的廢話部分。這個問題是完美的答案。

Answer 1

這並不完全清楚你遇到什麼問題;有一些具體的工作，我會假設你不能適應你引用你的問題的答案的原因是你不明白它是如何工作的。

您提供的內容模型允許元素box-type-1到box-type-4以任何順序出現;因爲有四個元素，所以有四個！ = 4 * 3 * 2 * 1 = 24個可能的序列。類似DTD的語法中的簡單正則表達式看起來像這樣;爲簡潔起見，我打算將元素b1,b2,b3, b4。

((b1, b2, b3, b4) 
| (b1, b2, b4, b3) 
| (b1, b3, b2, b4) 
| (b1, b3, b4, b2) 
| (b1, b4, b2, b3) 
| (b1, b4, b2, b3) 

| (b2, b1, b3, b4) 
| (b2, b1, b4, b3) 
| (b2, b3, b1, b4) 
| (b2, b3, b4, b1) 
| (b2, b4, b1, b3) 
| (b2, b4, b3, b1) 

| (b3, b1, b2, b4) 
| (b3, b1, b4, b2) 
| (b3, b2, b1, b4) 
| (b3, b2, b4, b1) 
| (b3, b4, b1, b2) 
| (b3, b4, b2, b1) 

| (b4, b1, b2, b3) 
| (b4, b1, b3, b2) 
| (b4, b2, b1, b3) 
| (b4, b2, b3, b1) 
| (b4, b3, b1, b2) 
| (b4, b3, b2, b1) 
) 

到目前爲止，一切都很好，但有兩個併發症：第一，內容模型都必須在這兩個XML DTD和XSD架構確定性。這意味着，必須始終可以將內容中的元素與內容模型中的特定標記（或xsd：元素元素）進行匹配，而不必展望未來。但內容中的初始b1可能與內容模型中b1的前六次出現中的任何一個匹配。這是不允許的，所以我們需要重寫內容模型以消除非確定性。

所以我們將表達式重寫，利用該觀察代數同一性，對於序列，（（XýABC）|（XŽDEF））等於（X（（ýABC）|（žDEF）））。如果我們摺疊常用前綴一起由身份建議，那麼我們生產的具有確定性的表達式可識別完全相同的語言：

((b1, ((b2, ((b3, b4) | (b4, b3))) 
     | (b3, ((b2, b4) | (b4, b2))) 
     | (b4, ((b2, b3) | (b3, b2))))) 
| (b2, ((b1, ((b3, b4) | (b4, b3))) 
     | (b3, ((b1, b4) | (b4, b1))) 
     | (b4, ((b1, b3) | (b3, b1))))) 
| (b3, ((b1, ((b2, b4) | (b4, b2))) 
     | (b2, ((b1, b4) | (b4, b1))) 
     | (b4, ((b1, b2) | (b2, b1))))) 
| (b4, ((b1, ((b2, b3) | (b3, b2))) 
     | (b2, ((b1, b3) | (b3, b1))) 
     | (b3, ((b1, b2) | (b2, b1)))))) 

現在我們打的第二併發症：這是不太我們想要的語言，因爲它使所有四個要素都是強制性的。

一個簡單的方法，使b2 - b4可選的將是一個問號添加到每個人的表情，所以它有一個形式是這樣的：

((b1, ((b2?, ((b3?, b4?) | (b4?, b3?))) 
     | (b3?, ((b2?, b4?) | (b4?, b2?))) 
     | (b4?, ((b2?, b3?) | (b3?, b2?))))) 
| (b2?, ...) 
| (b3?, ...) 
| (b4?, ...)) 

但這個重新介紹非確定性：輸入序列b1,b2僅在所示表達式的部分中匹配五種方式。正確的解決方法是觀察到，而（（X，ÿ）|？（Ý，X）？）是非確定性的，表達式（（X，ÿ？ ）|（y,x？））？是確定性的並接受相同的語言。運用這一原則使我們能夠適當地改寫我們的表達：

((b1, ((b2, ((b3, b4?) | (b4, b3?))?) 
     | (b3, ((b2, b4?) | (b4, b2?))?) 
     | (b4, ((b2, b3?) | (b3, b2?))?))?) 
| (b2, ((b1, ((b3, b4?) | (b4, b3?))?) 
     | (b3, ((b1, b4?) | (b4, b1))) 
     | (b4, ((b1, b3?) | (b3, b1))))) 
| (b3, ((b1, ((b2, b4?) | (b4, b2?))?) 
     | (b2, ((b1, b4?) | (b4, b1))) 
     | (b4, ((b1, b2?) | (b2, b1))))) 
| (b4, ((b1, ((b2, b3?) | (b3, b2?))?) 
     | (b2, ((b1, b3?) | (b3, b1))) 
     | (b3, ((b1, b2?) | (b2, b1)))))) 

請注意，我們不標註任何標誌傳送到第一b1可選的左邊，因爲那將是不必要的，不可取的。不必要的，因爲我們總是可以不失一般性地假設在輸入中沒有出現的可選元素在上面給出的一個排列的末尾被省略。不可取的，因爲它也會重新引入非決定論。

從這個表達式到XSD的翻譯很簡單，我把它作爲讀者的練習。

[注爲XML愛好者閱讀本：其他人可能現在停止閱讀。]

我寫生成不問號左側摺疊表達可能是感興趣的XQuery函數：

declare function local:all-to-choice-of-seq(
    $ids as xs:string* 
) as xs:string { 
    let $n := count($ids) 
    return if ($n eq 1) then $ids 
    else '(' || 
     string-join(for $id in $ids 
     let $rest := $ids[. ne $id] 
     return '(' || $id || ', ' 
       || local:all-to-choice-of-seq($rest) || ')', 
     ' | ') 
     || ')' 
}; 

調用：

let $gis := ('b1', 'b2', 'b3', 'b4') 
return local:all-to-choice-of-seq($gis) 

簡單extensi在做出所需要的一些元素和其他可選的將是：

declare function local:all-to-choice-of-seq2(
    $req as xs:string*, 
    $opt as xs:string* 
) as xs:string { 
    local:all-to-choice-of-seq-aux(($req,$opt), $req) 
}; 

declare function local:all-to-choice-of-seq-aux(
    $ids as xs:string*, 
    $req as xs:string* 
) as xs:string { 
    let $n := count($ids) 
    return 
    if ($n eq 1) then 
    if (exists($req)) then $ids else $ids || '?' 
    else '(' || 
     string-join(for $id in $ids 
     let $rest := $ids[. ne $id], 
      $req2 := $req[. ne $id] 
     return '(' || $id || ', ' 
       || local:all-to-choice-of-seq-aux($rest, $req2) || ')' 
       || (if (exists($req)) then '' else '?'), 
     ' | ') 
     || ')' 
}; 

調用：local:all-to-choice-of-seq2('b1', ('b2', 'b3', 'b4'))

但這插入比是絕對必要更多的問號;我還沒有找到一個好方法（或者，更誠實地說，我們可以用的方式）發射'？'只有在必要時。