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


         

если при одновременной модификации текстового


Это, так называемая, классическая “3-way Merge” схема реконсиляции в отличие от схем “2-way Merge” и “4-way Merge”, имеющих более узкое применение [15, 16].
Рис. 1. Пример консолидации изменений в итоговом текстовом документе Например, если при одновременной модификации текстового файла в ходе выполнения одной транзакции была вставлена новая строка, а в ходе выполнения другой транзакции одна из строк была удалена, результатом консолидации изменений должен стать итоговый документ с внесенными общими изменениями (см. рис. 1), дополняющий его существующие версии новым согласованным вариантом. Корректная идентификация изменений и реализация функции исполнения предполагают, что соответствующие тождества
,
 необходимо удовлетворены. Тривиальными случаями реализации функции реконсиляции являются
,
 и
, приводящие к уже известным версиям коллекции
,
 и
 соответственно. Содержательная реализация функции реконсиляции
 нетривиальна, поскольку
,
 могут представлять собой иерархически структурированные изменения
,
,
,
 и т.д. По существу, дельты
,
 являются реконструируемым представлением конкурентных транзакций, примененных к исходным данным
 и имеющих результатом
 и
 соответственно. В силу указанных причин реализация данной функции должна обеспечивать консолидацию как можно большего числа изменений при условии сохранения частичного порядка операций, индуцируемого семантикой приложений, и их бесконфликтности. В случаях, когда все конфликты разрешаются путем принятия изменений из первой версии, функция реконсиляции строится следующим образом:
, где логическая функция
 истинна в случае конфликта между изменениями
,
. Является открытым вопрос о том, какие ситуации следует считать конфликтными, и каким образом они могут быть разрешены: отменой всех операций, выделением и принятием бесконфликтного подмножества операций, или путем их коррекции. В дальнейшем под конфликтом будем понимать бинарное или множественное отношение между наборами или последовательностями операций в конкурентных транзакциях
,
, одновременное принятие которых приводит к некорректной интерпретации операций и неоднозначности результата, или к нарушению семантических ограничений, накладываемых на результирующее представление данных
, где
. Стандартный способ разрешения конфликта состоит в принятии одной из опций
.

Содержание  Назад  Вперед