Нечеткое сравнение коллекций семантический и алгоритмический аспекты


Задача нечеткого сравнения в приложениях семантической реконсиляции - часть 2


Это, так называемая, классическая “3-way Merge” схема реконсиляции в отличие от схем “2-way Merge” и “4-way Merge”, имеющих более узкое применение [15, 16].

Рис. 1. Пример консолидации изменений в итоговом текстовом документе

Например, если при одновременной модификации текстового файла в ходе выполнения одной транзакции была вставлена новая строка, а в ходе выполнения другой транзакции одна из строк была удалена, результатом консолидации изменений должен стать итоговый документ с внесенными общими изменениями (см. рис. 1), дополняющий его существующие версии новым согласованным вариантом.

Корректная идентификация изменений и реализация функции исполнения предполагают, что соответствующие тождества

,
 необходимо удовлетворены.

Тривиальными случаями реализации функции реконсиляции являются

,
 и
, приводящие к уже известным версиям коллекции
,
 и
 соответственно. Содержательная реализация функции реконсиляции
 нетривиальна, поскольку
,
 могут представлять собой иерархически структурированные изменения
,
,
,
 и т.д. По существу, дельты
,
 являются реконструируемым представлением конкурентных транзакций, примененных к исходным данным
 и имеющих результатом
 и
 соответственно. В силу указанных причин реализация данной функции должна обеспечивать консолидацию как можно большего числа изменений при условии сохранения частичного порядка операций, индуцируемого семантикой приложений, и их бесконфликтности. В случаях, когда все конфликты разрешаются путем принятия изменений из первой версии, функция реконсиляции строится следующим образом:

,

где логическая функция

 истинна в случае конфликта между изменениями
,
. Является открытым вопрос о том, какие ситуации следует считать конфликтными, и каким образом они могут быть разрешены: отменой всех операций, выделением и принятием бесконфликтного подмножества операций, или путем их коррекции.

В дальнейшем под конфликтом будем понимать бинарное или множественное отношение между наборами или последовательностями операций в конкурентных транзакциях

,
, одновременное принятие которых приводит к некорректной интерпретации операций и неоднозначности результата, или к нарушению семантических ограничений, накладываемых на результирующее представление данных
, где
.

Стандартный способ разрешения конфликта состоит в принятии одной из опций

.


Начало  Назад  Вперед