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


Сравнение множеств


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

 — множества элементов типа T, предполагающего неявное задание и выполнение единственного семантического ограничения уникальности элементов
. Дельта для двух версий множества
 может быть естественным образом представлена в виде неупорядоченного набора операций добавления и удаления соответствующих элементов коллекции:

Корректное представление дельты

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

Применение операций, определяемых дельтой, довольно прозрачно. К заданному исходному множеству добавляются элементы, определяемые операциями ins, и удаляются элементы, определяемые операциями del. Тем самым, гарантируется тождественность условия

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

Две конкурентные транзакции

 могут оказаться конфликтными в случае
, когда в одной транзакции некоторый элемент добавляется в коллекцию, а в другой транзакции тот же самый элемент удаляется. Однако, если обе дельты вычислялись относительно общей версии коллекции в рамках распространенной схемы слияния “3-way Merge”:
,
, то подобные конфликты исключены в силу того, что удаляемый элемент обязан принадлежать базовой версии коллекции X и не может быть добавлен в нее повторно вследствие ограничения уникальности элементов множества. В случае иных схем слияния с участием нескольких базовых версий, например, схемы “4-way Merge”, подобные конфликты должны идентифицироваться и корректно разрешаться. Тривиальными способами разрешения являются следующие опции
, предполагающие игнорирование обеих конфликтных операций или принятие одной из них.

Сложность вычисления дельты

 определяется, прежде всего, способом представления исходных множеств (список, массив, сбалансированное дерево), а также алгоритмами поиска добавляемых и удаляемых элементов.


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