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


Сравнение мультимножеств


Перейдем к задаче сравнения мультимножеств

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

В используемых обозначениях Z — множество целых чисел. Положительное значение параметра n в операции изменения кардинальности card(x,n) указывает на добавление элемента в коллекцию соответствующее число раз, отрицательное значение — на удаление элемента из коллекции. Нулевое значение n не содержательно для представления дельты, поскольку означает, что количество экземпляров элемента в коллекции не изменилось. В корректно сформированном представлении дельты

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

Применение базовой операции дельты card(x,n) состоит в кратном добавлении соответствующего элемента x при положительном значении параметра n и в его кратном удалении при отрицательном значении параметра. Это гарантирует выполнение необходимого тождества

.

Две операции

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


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