Реляционные инварианты

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

insert (вставить) – эта операция выполняется, когда становится интересен новый индивидуальный объект;

delete (удалить) – эта операция выполняется, когда существующий индивидуальный объект перестает быть интересным; и

modify (модифицировать) – эта операция выполняется, когда заданные элементы некоторого существующего объекта становятся субъектом изменений.

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

каждый R-индивидуум должен определять некоторый уникальный Ri-индивидуум;

никакие два R-индивидуума не определяют одно и то же множество Ri-индивидуумов для всех Ri, селекторы которых входят в "список ключей";

каждый Rij-индивидуум должен также быть R-индивидуумом;

каждый R-индивидуум, классифицируемый как Rij, должен также быть Rij-индивидуумом;

никакой Rij-индивидуум не является также Rik-индивидуумом при j ? k.

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

Пусть t – некоторый кортеж Rij. Образ предка (parent image) t – это некоторый кортеж t' из R, для которого:

t и t' имеют одни и те же значения во всех общих доменах и
t'.ski имеет значение "Rij".

С семантической точки зрения, кортеж и его образ предка совместно описывают один и тот же индивидуум реального мира; однако образ предок находится на более высоком уровне обобщения.

Если t' – образ предка t, то мы говорим, что t – образ потомка (child image) t'.

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

для каждого R-кортежа t, если t.si

не есть "пусто", то в случае, когда Ri

– родовой идентификатор, t.si является ключом некоторого Ri-кортежа, а в случае, когда Ri – идентификатор некоторого типа, t.si имеет тип Ri;

никакие два различных R-кортежа не могут иметь один и тот же ключ;

каждый Rij-кортеж имеет образ предка в R;

для каждого R-кортежа t, если t.sk

не есть "пусто" и имеет значение Rij, то R имеет образ потомка в Rij;

никакой R-кортеж не может иметь одновременно образы потомка в Rij и в Rik

при j ? k.

Эти пять условий мы называем реляционными инвариантами (relational invariant).

Они являются трансформацией пяти предыдущих условий в соответствии с методом представления родовых объектов как отношений. Имеется одно небольшое исключение, связанное с инвариантами (i) и (iv). Дело в том, что на практике необходимо допускать в некоторых доменах значения "пусто", которые означают "неизвестно" или "безразлично". Инварианты (i) и (iv) предусматривают существование такой возможности.

Реляционные инварианты могут рассматриваться как ограничения, налагаемые на отношения с тем, чтобы они представляли "абстрактные объекты". Эти инварианты должны удовлетворяться каждым отношением в реляционной модели, безотносительно к виду абстрактного объекта, который представляет данное отношение. Помимо этого, каждое отношение должно обычно удовлетворять множеству инвариантов (часто называемых "ограничениями целостности"), характерных только для этого отношения. Подобного рода инварианты ограничивают отношение таким образом, чтобы оно представляло конкретный вид абстрактных объектов. Поскольку реляционные инварианты применяются к каждому отношению, они являются наиболее фундаментальной формой ограничений целостности.

Обычно пользователи не взаимодействует с базой данных на уровне примитивных операций обновления insert, delete и modify. В большинстве случаев эти примитивы используются для конструирования операций обновления более высокого уровня, называемых транзакциями. Понятие транзакции позволяет иным образом характеризовать различия между реляционными инвариантами и специальными ограничениями целостности. Реляционные инварианты должны удовлетворяться до и после каждой инициированной пользователем операции обновления. Специальные же ограничения целостности должны удовлетворяться только до и после каждой транзакции.

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

модель корректно абстрагирует структуру реального мира во время обновления;

информация для обновления точно отражает атрибуты индивидуумов реального мира;

все пользователи имеют полные полномочия доступа ко всем отношениям.

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

В дальнейшем обсуждении будут полезны вводимые ниже аббревиатуры. Рассмотрим реляционную модель M, которая, наряду с прочим, содержит отношение R. Будем говорить, что относительно R некоторое отношение является:

paR, если оно является предком (parent) в плоскости агрегации (aggregation) отношения R;

caR, если оно является потомком (child) в плоскости агрегации (aggregation) отношения R;

pgR, если оно является предком (parent) в плоскости обобщения (generalization) отношения R;

cgR, если оно является потомком (child) в плоскости обобщения (generalization) отношения R.

На рис.19 показано, как отношение "связывается" со своими отношениями paR, caR, pgR и cgR.

Рис. 19. Отношение R и его отношения paR, caR, pgR и cgR

В приведена сводка методов поддержки реляционных инвариантов при выполнении операций обновления. Каждый тип операции обновления (insert, delete, modify) рассматривается в отдельной части таблицы. При этом в каждой части таблицы указывается воздействие на все пять инвариантов, оказываемое выполнением соответствующей операции обновления над кортежом t с ключом k в отношении R.

Таблица III. Поддержка реляционных инвариантов при выполнении операций обновления

INSERT

Инвариант	Возможные нарушения после вставки	Метод коррекции нарушения
i)	t ссылается на несуществующий кортеж в некотором caR-отношении R'	вставить в R' кортеж с соответствующими значениями ключа и значениями "пусто", где это уместно
ii)	t появляется в R дважды	удалить один из экземпляров t
iii)	t не имеет образа-предка в некотором pgR-отношении R'	если кортеж с ключом k уже существует в R', то модифицировать этот кортеж так, чтобы он стал образом предка t, иначе вставить образ предка в R' (используя "пусто" там, где значения неизвестны)
iv)	t не имеет требуемого образа потомка в некотором cgR-отношении R'	вставить образ потомка в R' (используя "пусто" там, где значения неизвестны)
v)	нет

DELETE

Инвариант	Возможные нарушения после вставки	Метод коррекции нарушения
(i)	кортеж в некотором paR-отношении ссылается на несуществующий R-кортеж	a) модифицировать этот кортеж так, чтобы ссылка была замещена значением "пусто" (это возможно, если только ссылка не является частью ключа кортежей) b) удалить этот кортеж
(ii)	нет
(iii)	у кортежа в некотором cgR-отношении отсутствует образ предка в R	удалить этот кортеж
(iv)	кортеж в некотором pgR-отношении не имеет требуемого образа потомка в R	a) модифицировать этот кортеж, замещая его значение в домене образов значением "пусто" (это возможно только тогда, когда домен образов не является частью ключа данного кортежа b) удалить этот кортеж
(v)	нет

<

MODIFY

Инвариант	Возможные нарушения после вставки	Метод коррекции нарушения
(i)	t ссылается на несуществующий кортеж в некотором caR-отношении R'	вставить в R' кортеж с соответствующими значениями ключа и значениями "пусто" там, где это уместно
(i)	(обновление ключевого домена) кортеж в некотором paR-отношении ссылается на несуществующий R-кортеж	модифицировать кортеж так, чтобы он ссылался на t
(ii)	нет
(iii)	t не имеет образа предка в некотором pgR-отношении R'	модифицировать старый образ предка t так, чтобы он стал (новым) образом предка
(iii)	кортеж в некотором cgR-отношении R' не имеет образа предка в R	если модифицируется домен образов для R', то удалить этот кортеж, иначе модифицировать этот кортеж так, чтобы t стал его образом предка
(iv)	t не имеет требуемого образа потомка в некотором cgR-отношении R'	если изменяется домен образов для R', то вставить образ потомка в R' (используя "пусто" там, где неизвестны значения), иначе модифицировать старый образ потомка t в R' так, чтобы он стал (новым) образом потомка t
(iv)	Кортеж в некотором pgR-отношении не имеет требуемого образа потомка в R	модифицировать кортеж так, чтобы t стал его образом потомка
(v)	нет

Предполагается, что реляционные инварианты удовлетворяются перед выполнением операций обновления. Каждая часть таблицы показывает, каким образом могут быть нарушены инварианты в результате операции обновления, а также какие действия можно предпринять для устранения каждого нарушения. Эти действия всегда сводятся к выполнению операции обновления над одним или несколькими отношениями paR, caR, pgR или cgR. Они, в свою очередь, могут вызвать другие нарушения и, следовательно, выполнение операций обновления над другими отношениями. Таким образом, единственная инициированная пользователем операция обновления может инициировать дополнительные операции обновления, которые распространяются как в плоскости агрегации, так и в плоскости обобщения.

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

Единственным случаем, когда инвариант (ii) может быть нарушен корректной операцией обновления, является вставка кортежа-дубликата. При этом корректирующим действием служит просто удаление одного из дубликатов. Инвариант (v) никогда не может быть нарушен при заданных нами предположениях корректности. Наконец, инварианты (i), (iii) и (iv) могут быть нарушены любым корректным обновлением. В каждом случае корректирующее действие соответствует абстракнотной структуре реляционных моделей. Рассмотрим несколько примеров.

Предположим, что мы нарушаем инвариант (i), вставляя кортеж t. Это означает, что t должен ссылаться на несуществующий кортеж в некотором отношении R'. Для устранения такого нарушения мы должны вставить подходящий кортеж (например, t') в R'. Не располагая какой-либо другой входной информацией, мы знаем единственную подробность относительно t' – его ключ, который входит в t. Следовательно, в неключевые домены t' должны быть вставлены значения "пусто". С семантической точки зрения, эффект этого корректирующего действия состоит в том, чтобы ввести абстрактный объект t', о котором известно, что он находится в связи с t.

Допустим теперь, что мы нарушаем инвариант (iii), удаляя кортеж t. Это означает, что кортеж t', который был образом потомка t, больше не имеет образа предка в R. Чтобы устранить это нарушение, мы должны удалить кортеж t'. Такое корректирующее действие отражает семантическое требование, состоящее в том, что объект, который не появляется в некотором классе на верхнем уровне обобщения, не может появиться в каком-либо классе на более низком уровне обобщения.

Предположим, наконец, что мы нарушаем инвариант (iv), модифицируя кортеж t. Имеются два случая, когда может иметь место такое нарушение. Первый случай возникает, когда после модификации t имеет некоторое значение, например, R', в каком-либо домене образов, скажем, в домене d, и t еще не имеет никакого образа потомка в R'. В этом случае корректирующее действие зависит от того, изменялся ли d при выполнении данной операции модификации. Если d не изменялся, то должен быть модифицирован старый образ-потомок t в R' так, чтобы сделать его новым образом потомка. Вся требуемая для этого информация уже имеется в t. Если же d изменялся, то в R' должен быть вставлен образ потомка. Ключ этого образа потомка содержится в t, однако, в каждый домен, значение которого не содержится в t, должно быть помещено значение "пусто".

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

Анализируя , можно обнаружить, что существует два метода коррекции нарушений инвариантов (i) и (iv), возникающих вследствие операции удаления. Каждый из этих методов семантически соответствует определенным ситуациям. Рассмотрим сначала инвариант (i). Допустим, что имеется абстрактный объект x, агрегатным компонентом которого является некоторый объект y. Возникает вопрос, должен ли удаляться x, если удаляется y. Представляется, что ответ зависит от контекста.

Предположим, например, что у некоторого автомобиля имеются "радиоприемник" и "кузов", представляющие собой два его агрегатных компонента. Если повреждается радиоприемник, то обычно считается, что автомобиль по-прежнему существует.

Однако, если разрушен кузов, то и автомобиль обычно также считается разрушенным. Поскольку на подобные вопросы относительно удаления можно отвечать только в рамках семантики более высокого уровня, необходимо оставить открытым решение вопроса о том, как поддерживать инвариант (i). Когда проектируются транзакции, программист может выбрать, какая альтернатива в наибольшей мере соответствует тем ограничениям целостности, которые он желает поддерживать.

Аналогичные соображения применимы к инварианту (iv). Пусть мы имеем общий класс объектов x, который включает все объекты из более специального класса y. Вопрос состоит в том, следует ли удалять объект из x, когда он удаляется из y. Допустим, например, что некоторый объект прекращает быть автомобилем Форд. Поскольку изменение изготовителя – не слишком осмысленное действие, естественно предположить, что объект вообще перестает быть "автомобилем". С другой стороны, допустим, что некоторый объект прекратил быть "красным автомобилем". Поскольку достаточно легко перекрасить красный автомобиль в голубой цвет, можно предположить, что этот объект по-прежнему остается "автомобилем". Следовательно, решение о том, как следует поддерживать инвариант (iv) при операциях удаления, должно приниматься на более высоком уровне моделирования.

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

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

Что произойдет, если какие- либо два из этих путей пересекаются? Может ли одно инициируемое обновление аннулировать результаты работы другого? Является ли итоговый результат определенной пользователем операции обновления независимым от порядка, в котором выполнялись запускаемые операции обновления? Может ли последовательность запускаемых обновлений стать циклической? Если инициируемое обновление является неприемлемым (в связи с тем, что были бы нарушены инварианты (ii) или (v)), то должен быть произведен откат последовательности запускаемых обновлений, и должно быть отвергнуто первоначальное обновление. Каким образом можно узнать, что никакое "корректное" определенное пользователем обновление не будет отвергнуто по этой причине?

Нам хотелось бы потребовать, чтобы любая процедура поддержки инвариантов обладала, по крайней мере, следующими тремя свойствами:

распространение запускаемых обновлений должно в конечном счете завершаться;

общий эффект после завершения распространения не должен зависить от порядка, в котором выполняются запускаемые обновления;

"корректное" определяемое пользователем обновление может отвергаться в единственном случае, когда оно требует поместить значение "пусто" в какой-либо ключевой домен.

Назовем эти свойства завершаемостью (termination), детермнированностью (determinancy) и пластичностью (compliancy). Мы предполагаем, что процедуры поддержки инвариантов, приведенные в , обладают всеми этими тремя свойствами.

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