Сравнение множеств
Начнем рассмотрение с наиболее простого типа коллекций
— множества элементов типа T, предполагающего неявное задание и выполнение единственного семантического ограничения уникальности элементов
. Дельта для двух версий множества
может быть естественным образом представлена в виде неупорядоченного набора операций добавления и удаления соответствующих элементов коллекции:
Корректное представление дельты
предполагает, что выполняется условие
, означающее, что один и тот же элемент не может одновременно участвовать в операции добавления и удаления. Более того, будем исключать повторение операций добавления и удаления с одним и тем же элементом, которое при исполнении операций противоречило бы определению множества:
и
.
Применение операций, определяемых дельтой, довольно прозрачно. К заданному исходному множеству добавляются элементы, определяемые операциями ins, и удаляются элементы, определяемые операциями del. Тем самым, гарантируется тождественность условия
, в котором функция
возвращает модифицированное представление коллекции, полученное в результате применения дельты к заданному представлению коллекции X.
Две конкурентные транзакции
могут оказаться конфликтными в случае
, когда в одной транзакции некоторый элемент добавляется в коллекцию, а в другой транзакции тот же самый элемент удаляется. Однако, если обе дельты вычислялись относительно общей версии коллекции в рамках распространенной схемы слияния “3-way Merge”:
,
, то подобные конфликты исключены в силу того, что удаляемый элемент обязан принадлежать базовой версии коллекции X и не может быть добавлен в нее повторно вследствие ограничения уникальности элементов множества. В случае иных схем слияния с участием нескольких базовых версий, например, схемы “4-way Merge”, подобные конфликты должны идентифицироваться и корректно разрешаться. Тривиальными способами разрешения являются следующие опции
, предполагающие игнорирование обеих конфликтных операций или принятие одной из них.
Сложность вычисления дельты
определяется, прежде всего, способом представления исходных множеств (список, массив, сбалансированное дерево), а также алгоритмами поиска добавляемых и удаляемых элементов.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий
