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

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

      Е.Ф. Кодд  
Перевод: М.Р. Когаловский

      Источник: журнал Системы Управления Базами Данных # 1/1995, издательский дом  «Открытые системы»  
Новая редакция: Сергей Кузнецов, 2009 г.

      Оригинал: E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June, 1970. Текст доступен здесь.

      Содержание

      1. Реляционная модель  и нормальная форма 

      1.1. Введение 

      1.2. Зависимости данных  в существующих  системах 

      1.3. Реляционное представление  данных 

      1.4. Нормальная форма 

      1.5. Некоторые лингвистические  аспекты 

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

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

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

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

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

      2.4. Заключение 

      Литература 

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

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

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

      1. Реляционная модель  и нормальная форма 

      1.1. Введение 

      Эта статья посвящается применению элементарной теории отношений к системам, которые  обеспечивают совместный доступ к большим  банкам форматированных данных. За исключением статьи Чайлдса (Childs) [1], основной областью применения отношений к системам данных являются дедуктивные системы ответов на вопросы. В статье Ливейна (Levein) и Марона (Maron) [2] приводятся многочисленные ссылки на работы в этой области.

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

      Реляционное представление (или модель) данных, описываемое в разд. 1, обладает некоторыми преимуществами по отношению к графовой, или сетевой модели [3,4], которая в настоящее время наиболее распространена среди систем, не основанных на логике. Реляционная модель предоставляет средства описания данных на основе только их естественной структуры, т.е. без потребности введения какой-либо дополнительной структуры для целей машинного представления. Соответственно, эта модель обеспечивает основу языка данных высокого уровня, который поддерживает максимальную независимость программ, с одной стороны, и машинного представления и организации данных с другой.

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

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

      1.2. Зависимости данных в существующих системах

      Обеспечение таблиц описания данных в разрабатываемых  сегодня системах является существенным продвижением на пути к независимости  данных [5,6,7]. Наличие таких таблиц облегчает изменения некоторых  характеристик представления данных, хранимых в банках данных. Однако набор характеристик представления данных, которые могут быть изменены без нанесения логического ущерба некоторым прикладным программам, продолжает оставаться ограниченным. Далее, модель данных, с которыми работают пользователи, по-прежнему загромождается характеристиками представления; в особенности это касается представлений коллекций данных (а не одиночных элементов данных). Тремя основными видами зависимости данных, которые все еще требуется устранить, являются зависимость порядка, зависимость индексации и зависимость путей доступа. В некоторых системах эти зависимости четко не отделены одна от другой.

      1.2.1. Зависимость порядка. Элементы данных в банке данных могут храниться разными способами, некоторые из которых не предполагают наличия какого-либо порядка, некоторые допускают участие каждого элемента только в одном порядке, а некоторые – в нескольких порядках. Обратим внимание на те существующие системы, в которых требуется или хотя бы допускается хранение элементов данных, по крайней мере, в одном полном порядке, тесно связанном с зависимым от аппаратуры порядком адресов. Например, записи в файле, описывающем детали, могут храниться в порядке убывания серийных номеров. В таких системах обычно допускается, чтобы прикладные программы основывались на предположении о том, что порядок представления записей идентичен порядку их хранения (или является его частью). Эти прикладные программы, использующие свойства упорядоченности файла, скорее всего не смогут правильно работать, если по какой-то причине потребуется изменить этот порядок. Аналогичные замечания остаются в силе для случая, когда порядок хранения реализуется посредством указателей.

      Нет необходимости выделять в качестве примера какую-либо одну систему, поскольку  во всех хорошо известных информационных системах, имеющихся на сегодняшнем рынке, не проводится четкое разделение порядка представления и порядка хранения. Для обеспечения независимости такого рода требуется решить существенные реализационные проблемы.

      1.2.2. Зависимость индексации. В контексте форматированных данных индекс обычно полагается компонентом представления данных, ориентированным исключительно на увеличение эффективности. Наличие индексов ускоряет выполнение запросов и операций обновления, но в то же время замедляет выполнение операций вставки и удаления. С точки зрения информативности индекс является избыточным компонентом представления данных. Если в системе используются индексы, и она должна хорошо справляться с изменениями активности среды по отношению к банку данных, то, вероятно, потребуется возможность время от времени создавать и уничтожать индексы. Возникает вопрос: могут ли при этом остаться неизменными прикладные программы и интерактивная деятельность?

      В современных системах форматированных данных применяются разнообразные подходы к индексации. В TDMS [7] обеспечивается обязательная индексация по всем атрибутам. В текущей версии IMS [5] пользователю предоставляется выбор для каждого файла: между полным отсутствием индексации (иерархическая последовательная организация) и индексацией только по первичному ключу (иерархическая индексно-последовательная организация). Ни в одном из этих случаев логика пользовательского представления не зависит от обязательно поддерживаемых индексов. Однако в IDS [8] проектировщикам файлов предоставляется возможность выбора индексных атрибутов и добавления индексов в структуру файла с использованием средств дополнительных цепочек. Прикладные программы, в которых для повышения эффективности используются эти индексные цепочки, должны ссылаться на них по именам. Такие программы не смогут работать правильно, если эти цепочки будут впоследствии удалены.

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

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

       
Структура 1. Проекты подчинены Деталям 

  
Структура 2. Детали подчинены Проектам

  
Структура 3. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Проектам

  
Структура 4. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Деталям 

  
Структура 5. Детали, Проекты и Связь  назначения деталей проектам наравне

      Теперь  рассмотрим задачу выборки номера детали, названия детали и количества деталей  этого типа для каждой детали, используемой в проекте с названием "альфа". Следующие наблюдения могут быть сделаны независимо от того, какая конкретная информационная система с древовидной организацией информации выбирается для решения этой задачи. Если для этого разрабатывается программа P, ориентированная на использование одной из приведенных выше структур (т.е. P не определяет, какова реальная структура представления данных), то при любом выборе P не сможет работать, по меньшей мере, с тремя потенциально возможными структурами. Более точно, если P следует структуре 5, то ей не удастся работать со всеми другими структурами; если PP следует структуре 3 или 4, то ей, по меньшей мере, не удастся работать со структурами 1,2 и 5; если P следует структуре 1 или 2, ей, как минимум , не удастся работать со структурами 3, 4 и 5. В каждом случае причина проста. Если отсутствуют проверки для определения реально заданной структуры, то работа P заканчится неудачей по причине попытки перехода по ссылке к несуществующему файлу (в доступных сегодня системах это трактуется как ошибка) или из-за отсутствия перехода по ссылке к файлу, содержащему нужную информацию. Читателю, который в этом сомневается, рекомендуется написать пробные программы для решения этой простой задачи.

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

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

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

      1.3. Реляционное представление  данных 

      Термин  отношение используется здесь в его общепринятом математическом смысле. Для заданных множеств S₁, S₂, ..., S_n (не обязательно различных) R является отношением на этих n множествах, если представляет собой множество кортежей степени n, у каждого из которых первый элемент взят из множества S₁, второй – из множества S₂ и т.д.¹⁾ Мы будем называть S_j j-тым доменом R. Говорят, что такое отношение R имеет степень n. Отношения степени 1 часто называют унарными, степени 2 – бинарными, степени 3 – тернарными и степени n – n-арными.

      Для наглядности мы будем часто использовать представление отношений в виде массивов, но нужно помнить, что это конкретное представление не является существенной частью излагаемого реляционного представления. Массив, представляющий n-арное отношение R, обладает следующими свойствами:

1. Каждая строка представляет кортеж степени n.
2. Порядок строк не является существенным.
3. Все строки различны.
4. Порядок столбцов является существенным – он соответствует порядку S₁, S₂,..., S_n доменов, на которых определяется R (однако обратите внимание на приводимые ниже замечания по поводу отношений с упорядоченными и неупорядоченными доменами).
5. Значимость каждого столбца частично выражается посредством его пометки именем соответствующего домена.

      В примере на рис.1 показано отношение  степени 4 поставка. В этом отношении отражаются выполняемые поставки деталей от указанных поставщиков для указанных проектов в указанных количествах.

      Рисунок 1. Отношение степени 4

      Можно спросить: если столбцы помечены именами соответствующих доменов, зачем нужна упорядоченность столбцов? Как показывает рис.2, для двух столбцов могут иметься одинаковые заголовки (означающие одинаковые домены), но смысл этих столбцов может быть различным. Показанное отношение называется компонент. В этом тернарном отношении два первых домена называются деталь, а третий – количество. Смысл отношения компонент (x, y, z) состоит в том, что деталь x является непосредственным компонентом (или составной частью) детали y, и для сборки одного экземпляра детали y требуется z экземпляров детали x. Это отношение играет критическую роль в проблеме разборки деталей.

      Рисунок 2.Отношение с двумя одинаковыми доменами

      Примечательным  фактом является то, что некоторые  современные системы (главным образом, те, которые основываются на файлах с древовидной структурой) не в  состоянии обеспечить представление  данных для отношений, которые имеют  два или более одинаковых домена. Примером такой системы является текущая версия IMS/360 [5].

      Ко  всем данным, находящимся в банке  данных, можно относиться как к  коллекции изменяющихся во времени  отношений. Эти отношения обладают разными степенями. Во время существования каждого n-арного отношения в него могут вставляться дополнительные кортежи степени n, удаляться существующие кортежи и изменяться компоненты существующих в нем кортежей.

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