XSD - хз: все переписаны, как детерминированный ОТД

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> 

[хз: Тип не имеет значения]

Пожалуйста, см: https://stackoverflow.com/a/7833274/6805256

Связанный ответ показывает DTD эквивалент аналогичной схемы , но Я не могу приспособить ее к моим потребностям и точному корпусу.

EDIT: Я удалил бессмысленную часть моего вопроса. Ответ на этот вопрос вполне отвечает.

Answer 1

Непонятно, с какими проблемами вы сталкиваетесь; чтобы иметь что-то конкретное, чтобы работать, я буду считать, что причина, по которой вы не можете адаптировать ответ, который вы цитируете к своей проблеме, заключается в том, что вы не понимаете, как это работает.

Модель контента, которую вы даете, позволяет элементам box-type-1 через box-type-4 происходить в любом порядке; так как есть четыре элемента, есть 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 и XSD схем детерминированным. Это означает, что всегда должно быть возможно сопоставить элементы в контенте с конкретными токенами (или xsd: элементы элементов) в модели контента, не задумываясь. Но начальный b1 в содержимом может соответствовать любому из первых шести вхождений b1 в модели контента. Это недопустимо, поэтому нам нужно переписать модель контента, чтобы устранить недетерминизм.

Таким образом, мы перепишем выражение, используя алгебраическую идентичность, которая отмечает, что для последовательностей ((хуа) | (хгЗащиты)) равно (х ((уа) | (гЗащита))). Если сложить общие префиксы вместе, как было предложено, что единицей, то мы производим детерминированный выражение, которое распознает точно на том же языке:

((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 соответствует пяти способам только в той части выраженного выражения. Правильное исправление заметить, что время ((х, у) |? (у, х)?) Не является детерминированным, то выражение ((х, у?) | (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'))

Но это вставляет больше вопросительных знаков, чем строго необходимо; Я не нашел хороший способ (или, если честно, любой способ), чтобы испустить '?' только при необходимости.