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


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


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

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

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

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

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

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

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

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

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


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