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

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

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

      Опять-таки, если принять реляционное представление, в котором каждое n-арное отношение (n>2) должно быть описано пользователем как вложенное выражение, включающее только бинарные отношения (см., например, LEAP System Фельдмана (Feldman) [10]), то вместо всего лишь n+1 имен при использовании прямой n-арной нотации, описанной в разделе 1.2, потребуется образовать 2n-1 имен. Например, 4-арное отношение поставка, приведенное на рис.1 и содержащее 5 имен в n-арной нотации, во вложенной двоичной нотации было бы представлено в виде

      P ( поставщик, Q ( деталь, R( проект, количество)))

      и, таким образом, в нем использовались бы 7 имен.

      Другим  недостатком такого представления  является его асимметрия. Несмотря на то, что эта асимметрия не препятствует симметричному использованию, она, определенно, составляет некую основу для запросов, которые трудно формулировать пользователям (попробуйте, например, выразить с использованием Q и R запрос о том, какие детали и в каком количестве используются в данном проекте).

      1.6. Выразимые, именованные  и хранимые отношения 

      С банком данных связаны два набора отношений: множество именованных и множество выразимых отношений. Множество именованных отношений составляют те отношения, которые сообщество пользователей может идентифицировать посредством простых имен (или идентификаторов). Отношение R входит во множество именованных отношений после его объявления пользователем, обладающим соответствующими правами; оно выходит из этого множества, когда этот пользователь отменяет объявление R.

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

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

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

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

      2. Избыточность и  согласованность

      2.1. Операции над отношениями. 

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

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

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

      2.1.1. Перестановка. Бинарное отношение представляется в виде массива с двумя столбцами. В результате перестановки этих столбцов получается обратное отношение. В общем случае, при перестановке столбцов n-арного отношения про результирующее отношение говорят, что оно является перестановкой заданного отношения. Существует, например, 4! = 24 перестановок отношения поставка, приведенного на рис. 1, с учетом тождественной перестановки, которая оставляет порядок столбцов неизменным.

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

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

      Оператор  селекции π используется для получения  любой требуемой перестановки, проекции или комбинации этих операций. Так, если L – список из k значений⁷⁾ L = i₁, i₂,...,i_k, и R – n-арное отношение (n≥k), то π_L (R) есть k-арное отношение, j-тый столбец которого есть i_j-тый столбец R (i=1,2,...,k) и в котором удалены дубликаты результирующих строк. Рассмотрим отношение поставка на рис.1. Перестановка проекции этого отношения приведена на рис.4. Заметьте, что в этом частном случае проекция имеет меньше n-кортежей, чем исходное отношение.

      Рисунок 4. Перестановка проекции отношения c рис.1

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

      В примере на рис.5 показаны два отношения R и S, которые могут быть соединены без потери информации, а на рис.6 представлен результат соединения R и S. Бинарное отношение R соединимо с бинарным отношением S, если существует тернарное отношение U такое, что π₁₂(U)=R и π₂₃(U)=S. Любое такое тернарное отношение называется соединением R и S. Если R, S являются бинарными отношениями, такими, что π₂(R) = π₁(S), то R соединимо с S. Одно из соединений, которое всегда существует в таком случае, это естественное соединение, определяемое так:

      R*S = {(a,b,c) : R(a,b) ∧ S(b,c)},

      где R(a,b) имеет значение истина, если (a,b) является элементом R, и S(b,c) – аналогично. Очевидно, что

      π₁₂(R*S) = R

      и

      π₂₃(R*S) = S.

      Заметим, что соединение, показанное на рис.6, является естественным соединением отношений R и S, представленных на рис.5. Другое соединение показано на рис.7.

      Рисунок 5.Два соединимых отношения 

      Рисунок 6.Естественное соединение R и S (рис. 5)

      Рисунок 7. Другое соединение R и S (рис.5)