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

       

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


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

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

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

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

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

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

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

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

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

Содержание раздела







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий