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