Классика баз данных - статьи




Семантика мультимножеств с параллельным обновлением


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

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

Интересный случай возникает при анализе добавления и удаления единственного вхождения объекта в CuBag. Внутри одной транзакции операции добавления и удаления одного и того же объекта не являются коммутативными в соответствии с семантикой операции удаления. Например, если удаление происходит после добавления, то операция выполняется успешно. Если же удаление выполняется до добавления объекта, то операция удаления терпит неудачу, поскольку объект не присутствует в CuBag. Однако когда эти операции выполняются в параллельных транзакциях, они являются коммутативными. Эти операции являются коммутативными, поскольку операция удаления всегда терпит неудачу, независимо от порядка, в котором транзакции пытаются фиксироваться.


Содержание  Назад  Вперед