С.С. Магазов, Д.О. Чугунов
10
Унификация.
В ХLog для организации эффективного доступа к
частям ХLog-документа помимо оператора пути добавлен ориги-
нальный и эффективный механизм унификации.
Унификация XLog-документов.
Определим бинарный оператор
унификации
на XLog-документах и обозначим его как U(H1,H2), где H1,
H2 – XLog-документы. Операция унификации устанавливает структур-
ную схожесть двух XLog-документов. В случае успешной унификации
переменные, входящие в H1 и H2, могут
конкретизироваться,
т. е. им
присваиваются в качестве значений фрагменты XLog-документа.
Если
переменой не присвоено значение, она будет
неконкретизированной
. В
процессе унификации переменные документов
связываются
. Для свя-
занных переменных справедливо следующее утверждение: при измене-
нии значения какой-либо одной из связанных переменных все осталь-
ные связанные с ней переменные принимают новое значение.
Дадим индуктивное определение оператору унификации:
1) Если H1, H2 – два одинаковых как строки документа, то они
унифицируемы.
2) Пусть даны два заголовка тегов H1=<t1 a
1
=V
1
… a
n
=V
n
> и
H2=<t2 b
1
=L
1
… b
m
=L
m
>, где t1 и t2 – имена тегов, a
i
и b
i
– атрибуты
тегов. H1 и H2 унифицируемы тогда и только тогда, когда t1=t2 и
унификация атрибутов успешна. Рассматриваются атрибуты, которые
входят одновременно в оба тега. Остальные атрибуты не оказывают
никакого влияния на унификацию.
3) Атрибуты a=V, b=L такие, что a=b, унифицируются, если вы-
полняются условия пунктов 3a–3e.
3a) L и V – константные значения, L=V.
3б) L и V – несвязанные и неконкретизированные переменные. В
этом случае L и V становятся связанными между собой.
3в) L – связанная конкретизированная переменная, V – несвязан-
ная переменная. В этом случае L и V становятся связанными, а пере-
менная V конкретизируется значением из L.
3г) L – связанная конкретизированная переменная, V – констант-
ное значение, значение V совпадает с L.
3д) L – связанная конкретизированная переменная, V – связанная
конкретизированная переменная, значение V совпадает с L. Перемен-
ные L и V становятся связанными.
К пунктам 3a–3д добавляются пункты, в которых L и V меняются
местами.
4) Унификация XLog-элемента и переменной осуществляется со-
гласно правилам 4a–4б.
4a) если H1 – XLog-элемент, а $$X – неконкретизированная пе-
ременная, Н1 унифицируется с $$X и $$X принимает значение H1;
4б) Если H1 – XLog-элемент, а $$X – конкретизированная пере-
менная, унификация успешна только в том случае, если значение пе-
ременной $$X унифицируется с H1.
