8.10.1. Коммутативный и ассоциативный законы
Для упрощения алгебраических выражений самых разных типов наиболее широко применяются коммутативный и ассоциативный законы. Коммутативный закон (commutative law) для некоторого оператора гласит, что в каком бы порядке ни задавались аргументы оператора, результат оказывается одинаковым. Например, к коммутативным арифметическим операторам относятся операторы сложения (+) и умножения (*): если говорить формально, для любых числовых величин х и у справедливы соотношения х + у = у + х и х*у = у*х,, С другой стороны, оператор вычитания (-) не коммутативен: х-у ≠ у-х.
Ассоциативный закон (associative law) разрешает группирование аргументов не-; скольких одноименных операторов. Те же арифметические операторы + и * являются ассоциативными: для любых числовых значений х, у и z имеют место тождества (x + y) + z = x +(y + z) и (х*у) *z = x*(у*z). Оператор вычитания, напротив, не ассоциативен: (х-у)- z ≠ x-(y-z). Если оператор одновременно коммутативен и ассоциативен, его результат не изменяется при любом мыслимом упорядочении и/или группировании аргументов: например, ((w + х) + у) + z = (у + х) + (z + w).
Некоторые операторы реляционной алгебры являются как коммутативными, так и ассоциативными, а именно:
R×S=R×S; (R×S) ×T=R× (S×T).
R S=R S; (R S) T=R (S T).
R
S=R
S;
(R
S)
T=R
(S
T).
R S=R S; (R S) T=R (S T).
Заметим, что указанные законы справедливы для операторов, работающих и с множествами, и с мультимножествами.
Мы не будем строго доказывать каждый из этих законов, хотя один пример подобного доказательства все-таки приведем. Общий метод проверки справедливости выражения реляционной алгебры, претендующего на роль "закона", таков: надлежит убедиться в том, что каждый кортеж, получаемый с помощью выражения из левой части, также возвращается в результате вычисления выражения правой части и наоборот.
Пример. Попытаемся доказать справедливость коммутативного закона для оператора соединения (join): R S = S R. Прежде всего, предположим, что в отношении, служащем итогом операции R S из левой части выражения, присутствует кортеж t.
Иными словами, должны существовать кортежи r в R и s в S, которые согласуются с t в каждом общем атрибуте. Поэтому при вычислении оператора из правой части выражения, S R, те же кортежи s и r дадут возможность образовать кортеж t.
Правомерно спросить, не будут ли компоненты t следовать в различном порядке при вычислении операторов из левой и правой частей. Формально говоря, в контексте реляционной алгебры порядок перечисления компонентов кортежей не существен, мы вольны при необходимости переставлять компоненты кортежей, не забывая соответствующим образом упорядочивать заголовки столбцов таблицы-отношения.
Доказательство пока не завершено. Поскольку реляционная алгебра — это, вообще говоря, алгебра мультимножеств, а не множеств, следует убедиться, что если кортеж t присутствует в итоговом отношении левой части выражения n раз, количество экземпляров t в отношении из правой части также должно быть равно п и наоборот. Пусть отношение из левой части содержит n копий кортежа t. Тогда следует признать, что кортеж r из R, согласующийся с t, присутствует в отношении R S из левой части в некотором количестве nR экземпляров, а кортеж s из S, также совпадающий с t в общих атрибутах, — в nS экземплярах, причем nRnS = n. При вычислении оператора S R правой части обнаруживается, что количество копий кортежа s из S по-прежнему равно nS, а количество копий кортежа r из R — nR, что дает возможность получить nsnR, или n, копий t.
Строго говоря, доказательство все еще не полно — рассмотрена та его часть, которая гласит, что все кортежи, присутствующие в отношении из левой части выражения, должны наличествовать и в правой части, но, помимо того, следовало бы доказать и обратное утверждение — если кортеж содержится в отношении правой части выражения, он обязан пребывать в составе отношения левой части. Ввиду очевидной симметрии все доводы сохраняют силу, так что повторять те же рассуждения нецелесообразно.
Мы не причисляем к категории коммутативно-ассоциативных оператор тета-соединения (theta-join), и вот почему. Несомненно, оператор коммутативен:
R
S=S
R.
Более того, если условия С сохраняют смысл при различном группировании аргументов, операция тета-соединения является ассоциативной. Однако существуют примеры, подобные приведенному ниже, где ассоциативный закон утрачивает силу ввиду того, что условия операторов не допускают применения к атрибутам отношений, подвергающихся тета-соединению.
Пример. Предположим, что даны отношения R(a, b), S{b, с) и Т(с, d), и выражение
преобразуется посредством применения гипотетического ассоциативного закона в следующее:
.
Однако отношения S и Т нельзя соединить на основе условия а < d, поскольку а не является атрибутом ни S, ни Т (и, более того, d присутствует только в T). Поэтому ассоциативный закон не может применяться к произвольным выражениям с операторами тета-соединения.