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


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


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

и . В данном случае изменения не содержат конфликтов и могут быть консолидированы, приводя к результирующему представлению списка . Оценка вычислительной сложности классического алгоритма минимального редакторского расстояния с использованием метода динамического программирования составляет . Этой же оценкой определяется общая сложность формирования дельты для списков. При неоптимальном формировании дельты, например, путем нахождения наибольшей общей последовательности и определения дополняющих операций, оценка вычислительной сложности может быть улучшена до , однако количество элементарных операций в полученном представлении дельты может оказаться высоким. Более детальная систематизация алгоритмов и сравнительный анализ их вычислительной сложности приводятся в [20, 21].

Сравнение упорядоченных множеств

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

Пусть

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

 =    

Операция перестановки

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

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

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

Все значения индексов позиций указываются в представлении дельты относительно исходных версий коллекции.
При выполнении дельты индексные параметры всех последующих операций должны корректироваться с учетом ранее примененных. Данная корректировка заключается в увеличении или уменьшении индексов элементов исходного множества на количество выполненных вставок или удалений. При выполнении перестановок корректировка состоит в циклическом распространении индекса для каждого последующего элемента группы перестановки. Любое изменение порядка элементов в упорядоченном множестве может быть представлено композицией циклических перестановок. Причем при отсутствии пересечений по индексам перестановки удовлетворяют требованию коммутативности и могут применяться в произвольном порядке независимым друг от друга образом [19]. Тем самым удовлетворяется требование конструктивной декомпозиции и реконсиляции транзакций, связанное с возможностью независимого применения их отдельных операций. При этом наличие одного и того же индекса в разных группах перестановок дельты

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


Для того чтобы удовлетворить условие и обеспечить неразрывность семантически связанных групп элементов, видятся два простых решения: обобщение операции перестановки таким образом, чтобы обеспечить циклическую перестановку не отдельных элементов, а целых групп; соблюдение условия предшествования операций перестановки операциям вставки. На наш взгляд, второй способ более предпочтителен, поскольку контроль частичного порядка операций при выполнении не вызывает дополнительных сложностей в реализации в отличие от обобщенных перестановок. Проиллюстрируем вычисление и применение дельты для упорядоченных множеств на следующем примере. Пусть  — основная и модифицированная версии коллекции символов, представленные следующими последовательностями элементов: , . Тогда дельта, вычисленная в соответствии с вышеописанной семантикой операций, представляется как В ходе применения дельты к основной версии  операции  переставляют элементы a, e и c, d исходного множества, приводя к промежуточным представлениям коллекции  и  соответственно. Операции  добавляют элементы g, h, k, l перед d и элемент m перед a, формируя последовательности  и . Наконец, операции ,  удаляют элементы b и f, приводя к окончательному представлению модифицированной версии коллекции . Опишем возможный способ формирования дельты двух упорядоченных множеств в соответствии с перечисленными выше условиями: Поиск идентичных подмножеств  и  исходных множеств, , сохраняющих оригинальный порядок следования элементов: , Возможная алгоритмическая реализация данного этапа состоит в предварительной сортировке элементов исходных множеств (при наличии отношения полного порядка) и последовательном просмотре и идентификации элементов как удаленных, вставленных или перенесенных без изменений. Альтернативный способ заключается в непосредственном использовании процедуры поиска для установления факта наличия или отсутствия элементов в исходных множествах и в параллельном формировании структур соответствия индексов элементов.


Подобные структуры обеспечивают быстрое преобразование индексов, необходимое для эффективной реализации следующих этапов. Поиск циклической перестановки элементов множества , приводящей к последовательности элементов множества . Наиболее простым способом реализации данного этапа видится предварительная замена алфавита исходного множества  на последовательность натуральных чисел  и применение методики, применяемой в доказательстве теоремы о единственности специальной формы соединительного произведения перестановки линейно упорядоченного мультимножества [19]. Определение множества операторов вставки , упорядоченного по индексам вставки элементов, используя структуры соответствия индексов элементов множеств  и . Определение множества операторов удаления , упорядоченного по индексам удаляемых элементов, используя структуры соответствия индексов элементов множеств  и . Формирование единого списка операций дельты в соответствии с принятым порядком исполнения: сначала следуют операции перестановок, затем — операции вставок и в конце — операции удаления. Сформированная таким образом дельта состоит из множества независимых операций, каждая из которых может быть принята или отклонена в рамках результирующей транзакции независимо от статуса остальных операций. Вычислительная сложность построения дельты определяется в первую очередь сложностью алгоритмов сортировки, применяемых в ходе реализации. Все остальные элементы, включая алгоритм разложения перестановки на множество циклических, имеют асимптотически линейную сложность при условии использования соответствующих структур быстрого преобразования индексов. Например, описанный метод формирования дельты с использованием сортировки на основе слияния списков имеет асимптотическую оценку вычислительной сложности . Перечислим конфликтные ситуации, возникающие при реконсиляции конкурентных операций над упорядоченными множествами, а также возможные способы их разрешения. Основные конфликты сводятся к следующим содержательным случаям (опустим для краткости математическую нотацию, примеры и комментарии подобно тому, как это делалось в предыдущей главе): Вставка тождественных элементов в разные позиции.


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

Коллекции с ограниченной мощностью

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

Пусть задано следующее ограничение мощности коллекции:

, где . Частный случай  соответствует коллекции фиксированной мощности. Если  и  — соответствующие подмножества операций вставки и удаления исходного представления дельты , то должно выполняться следующее дополнительное условие: .

Очевидно, что в случае фиксированной мощности

 количество операций вставки и удаления в транзакции должно совпадать. Для мультимножеств условие представления дельты  приобретает вид .

В случае конкурентных транзакций

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

Рассмотрим следующий пример. Пусть

 — базовая и модифицированные версии мультимножества символов с ограниченной мощностью : , , .
Тогда дельты, вычисленные путем сравнения модифицированных версий с базовой, представляются как , . Операции  и  эквивалентны, поэтому в результирующую дельту следует включить любую из них. Операция  не конфликтует ни с одной другой операцией, поэтому переносится в результат без изменений. Наконец, операции  и  конфликтуют друг с другом. Согласно рассмотренным выше методам согласования изменений для мультимножеств, конфликт можно разрешить выбором кратности вхождения элемента e из интервала [2, 4]. Однако выбор значения кратности, равного 4, приводит к нарушению ограничения мощности результирующего мультимножества, в которое в таком случае войдет 7 элементов. Следовательно, допустимыми значениями кратности вхождения элемента e в итоговую коллекцию являются 2 и 3. В случае принятия второго значения результирующая дельта приобретает вид: , а итоговое семантически корректное представление мультимножества — .

Последовательности фиксированной длины

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

 будем использовать следующее представление дельты:

,

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

 заменяет значение элемента исходного массива  с индексом i значением соответствующего элемента модифицируемого массива .

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

 предполагает, что индексы модифицируемых элементов не повторяются в разных операциях:

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

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

Рассмотрим следующий пример согласования изменений в массиве. Пусть

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

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

Наличие свойств сортировки для последовательностей элементов позволяет существенно ускорить процедуры сравнения коллекций

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

Коллекции прямых и инверсных ассоциаций

Коллекции могут использоваться для реализации множественных ассоциативных связей между объектными типами. В языках объектно-ориентированного моделирования имеется возможность для каждой прямой ассоциации объявить соответствующую инверсную, которая представляется, как правило, неупорядоченным множеством или мультимножеством объектных ссылок и налагает дополнительные семантические ограничения (уникальности или мощности множественной ассоциации) на исходную модель.

Пусть

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

Если инверсная ассоциация представляется множеством, то дополнительно устанавливается ограничение уникальности инверсного отношения. При сочетании в качестве прямой и инверсных ассоциаций различных коллекций более строгое ограничение уникальности в итоге распространится на обе ассоциативные связи. Таким образом, возможны следующие варианты сочетания прямых и инверсных коллекций: «set–set», «multiset–multiset», «list–multiset», «ordered set–set».

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

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

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

В силу отношений логической эквивалентности операций над прямыми и обратными ассоциациями, условия приобретают вид:

В случае конкурентных транзакций

 данные условия должны выполняться также для консолидированной дельты .

Литература

Y. Saito, M. Shapiro. Optimistic Replication // In ACM Computing Surveys, Vol. 37, No. 1, March 2005, pp. 42–81. Better SCM Initiative: Version Control System Comparison Diffutils — GNU Project — Free Software Foundation (FSF) Z. Xing, E. Stroulia. UMLDiff: an algorithm for object-oriented design differences. // Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, Long Beach, CA, USA, 2005, pp. 54–65. Open Testware Reviews — Data Comparator Survey Comprehensive List of File and Folder Comparison and Synchronization Tools Сравнение файлов — Soft Софт каталог Google directory — Computers > Software > File Management > File Comparison Semenov V.A., Karaulov A.A. Semantic-Based Decomposition of Long-Lived Transactions in Advanced Collaborative Environments. // Proceedings of 6 European Conference on product and process modeling, ECPPM 2006, Spain, Valencia, September 11–15, 2006, pp.223–232. Семенов В.А., Ерошкин С.Г., Караулов А.А., Энкович И.В. Семантическая реконсиляция прикладных данных на основе моделей. // Труды Института системного программирования: т. 13, ч. 2. / Под ред. В.П. Иванникова — М.: ИСП РАН, 2007, с. 141–164. Semenov V.A. Collaborative Software Engineering Using Metamodel-Driven Approach. // Proceedings 16th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, WET ICE 2007, IEEE Computer Society Conference Publishing Services, 2007, pp. 178–179. Semenov V.A. Semantics-Based Reconciliation of Divergent Replicas in Advanced Concurrent Engineering Environments. // Complex Systems Concurrent Engineering: Collaboration, Technology Innovation and Sustainability, Springer-Verlag, 2007, pp. 557–564. ISO 10303: 1994, Industrial automation systems and integration — Product data representation and exchange. OMG. Model Driven Architecture: How systems will be built. T. Lindholm. XML three-way merge as a reconciliation engine for mobile data. // Proceedings of the 3d ACM international workshop on data engineering for wireless and mobile access, San Diego, CA, USA, 2003, pp. 93–97. J. Katajainen and J. L. Träff. A Meticulous Analysis of Mergesort Programs. // Lecture Notes In Computer Science, vol. 1203, 1997, pp. 217–228. Object Constraint Language Specification, Version 2.0 ISO 10303-11: 2004, Industrial automation systems and integration — Product data representation and exchange — Part 11: Description methods: The EXPRESS language reference manual. Edition 2. Д. Кнут. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. — М.: Издательский дом «Вильямс», 2000. Д. Гасфилд. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — СПб.: Невский Диалект; БХВ-Петербург, 2003. G. Navarro. A Guided Tour to Approximate String Matching. // ACM Computing Surveys, vol. 33, no. 1, March 2001, pp. 31–88.

Таким образом, рассмотрены основные типы

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

---

---