Реляционная модель данных для больших совместно используемых банков данных

      2.1.5. Ограничение. Подмножество отношения является отношением. Один из способов воздействия отношения S на отношение R для получения подмножества R заключается в применении операции ограничения отношения R по отношению S. Эта операция является обобщением ограничения функции на подмножество ее области определения и определяется следующим образом.

      Пусть L, M – списки индексных значений одинаковой длины такие, что L = i₁, i₂,..., i_k, M = j₁, j₂, ..., j_k, где k≤ степень R и k≤ степень S. Тогда L,M-ограничение R по S, обозначаемое как R_L|_MS, есть максимальное подмножество R' множества R, такое, что

      π_L(R') = π_M (S).

      Эта операция определена только в том  случае, если применима операция равенства между элементами π_ih( R), с одной стороны и p_jh(S), с другой, для всех h=1,2,...k.

      Три отношения R, S, R', приведенные на рис.13, удовлетворяют соотношению R'=R_(2,3)|_(1,2)S.

      Рисунок 13. Пример ограничения 

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

      2.2. Избыточность 

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

      Предположим, что θ – это набор операций над отношениями, и каждая операция обладает тем свойством, что вырабатывает единственное отношение из своих операндов (т.е. естественное соединение допустимо, а соединение нет). Отношение R является θ-выводимым из множества отношений S, если существует последовательность операций из набора θ, которая "в любой момент времени" производит R из элементов S. Фраза "в любой момент времени" присутствует потому, что мы рассматриваем изменяющиеся во времени отношения, и для нас представляет интерес свойство порождаемости, сохраняющееся в течение длительного периода времени. Для набора именованных связей в системах без логического вывода достаточный набор θ₁ содержит следующие операции: проекция, естественное соединение, связывание и ограничение. Перестановка неуместна, а естественную композицию включать не требуется, т.к. ее можно получить путем естественного соединения с последующей проекцией. Для хранимого множества представлений достаточный набор θ₂ должен включать перестановку и дополнительные операции, связанные с получением подмножеств и слиянием отношений, упорядочиванием и связыванием их элементов.

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

      служащий (номер, имя, номер_менеджера, имя_менеджера)

      где номер является первичным ключом, и номер_менеджера является внешним ключом. Обозначим активный домен через Δ_t и предположим, что

      Δ_t (номер_менеджера) ⊂ Δ_t (номер)

      и

      Δ_t (имя_менеджера) ⊂ Δ_t (имя)

      в любой момент времени t. В этом случае избыточность очевидна: домен имя_менеджера не является необходимым. Чтобы убедиться в том, что эта избыточность является сильной избыточностью в соответствии с приведенным выше определением, заметим, что

      π₃₄ (служащий) = π₁₂ (служащий)₁|₁π₃(служащий).

      Во  втором примере набор отношений  включает описывающее поставщиков  отношение S с первичным ключом s#, описывающее отделы отношение D с первичным ключом d# и описывающее проекты отношение J с первичным ключом j#, а также следующие отношения:

      P(s#, d#,...), Q(s#, j#,...), R(d#, j#,...),

      где в каждом случае многоточие означает домены, отличающиеся от s#, d#, j#. Предположим, что удовлетворяется следующее не зависящее от времени условие C: поставщик s обслуживает отдел d (отношение P) тогда и только тогда, когда поставщик s обслуживает некоторый проект j# (отношение Q), который выполняется отделом d# (отношение R). Тогда мы можем записать соотношение

      π₁₂(P) = π₁₂ (Q) · π₂₁ (R)

      и таким образом показать наличие сильной избыточности.

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

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

      Мы  можем проиллюстрировать слабую избыточность, рассмотрев второй пример сильной избыточности (из приведенных выше) и предположив, что условие C в некоторые моменты времени не выполняется. Отношения π₁₂(P), π₁₂(Q), π₁₂(R) являются сложными ¹⁰⁾ отношениями с возможным существованием точек неоднозначности, появляющихся иногда в потенциальных соединениях каких-либо двух отношений. При этих условиях ни одно из них не порождается из двух других. Однако между ними существует зависимость, поскольку каждое из них является проекцией некоторого циклического соединения трех отношений. Один из видов слабой избыточности может быть охарактеризован следующим утверждением: в любой момент времени π₁₂(P) является некоторой композицией π₁₂(Q) и π₂₁(R). Эта композиция может быть естественной при одних обстоятельствах и может не являться таковой при других.

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

      2.3. Согласованность 

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

      Для данного набора C изменяемых во времени отношений, ассоциированного с ним множества Z ограничительных утверждений и значения V набора C в какой-либо момент времени мы будем называть состояние (C, Z, V) согласованным или несогласованным в зависимости от того, удовлетворяет ли V набору условий Z или нет. Например, для набора хранимых отношений R,S,T вместе с ограничительным утверждением "π₁₂(T) является композицией π₁₂ (R) и π₁₂ (S)" мы можем периодически проверять, что значения, хранящиеся в R,S,T, удовлетворяют этому условию. Алгоритм осуществления такой проверки должен просматривать первые два столбца каждого из отношений R,S,T (вне зависимости от способа их представления в системе) и определять, выполняются ли следующие условия

1. π₁(T) = π₁ (R)
2. π₂(T) = π₂ (S)
3. для каждой пары элементов (a,c) отношения π₁₂ (T) существует элемент b, такой, что (a,b) содержится в π₁₂ (R) и (b,c) содержится в π₁₂ (S).

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

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

      Предположим, что множество именованных отношений  C содержит отношения S, J, D, P, Q, R из примера раздела 2.2, и что P, Q, R обладают сильной или слабой избыточностью в определенном выше смысле (в рассматриваемом нами случае не важно, какая именно избыточность имеет место). Далее, предположим, что в некоторый момент времени t банк данных находится в согласованном состоянии и не содержит никакого проекта j такого, что поставщик 2 обслуживает проект j, и проект j ведется отделом 5. Соответственно, в π₁₂(P) не существует элемента (2,5). Пусть теперь пользователь вводит элемент (2,5) в π₁₂(P), вставляя соответствующий элемент в P. В этот момент состояние банка данных является несогласованным. Эта несогласованность могла возникнуть вследствие оплошности, если появление (2,5) является правильным, и действительно существует проект j такой, что поставщик 2 обслуживает проект j и проект j ведется отделом 5. В этом случае очень вероятно, что пользователь собирается в ближайшем будущем добавить элементы в Q и R, результатом чего явится появление (2,j) в π₁₂(Q) и (5,j) в π₁₂(R). С другой стороны, ввод (2,5) мог быть ошибочным. Так могло бы получиться, если бы пользователь намеревался вставить в P некоторый другой элемент, появление которого перевело бы согласованное состояние в согласованное состояние. Суть в том, что как правило, в системе будут отсутствовать средства разрешения этого вопроса без опроса окружения системы (например, пользователя, породившего несогласованность).