Реляционная модель данных для больших совместно используемых банков данных
Е.Ф. Кодд
Будущие пользователи больших банков данных должны быть освобождены от необходимости знать организацию данных в машине (внутреннее представление). Нельзя считать удовлетворительной какую-либо службу, если она предоставляет такую информацию. Изменение внутреннего представления данных и даже изменение некоторых аспектов их внешнего представления не должны влиять на работу пользователей за их терминалами и на выполнение большинства прикладных программ. Изменения представления данных часто требуются по причине изменения потока запросов, операций обновления и отчетов, естественного увеличения числа типов хранимой информации.
Существующие системы форматированных данных предоставляют пользователям файлы с древовидной структурой или немного более общие сетевые модели данных. В разд. 1 обсуждаются недостатки таких моделей. Вводятся модель, основанная на n-арных отношениях, нормальная форма отношений базы данных и универсальный подъязык данных. В разд. 2 обсуждаются некоторые операции над отношениями (отличные от операций логического вывода), а затем эти операции применяются к проблемам избыточности и согласованности пользовательской модели.
Ключевые слова и фразы: банк данных, база данных, структура данных, организация данных, иерархии данных, сети данных, отношения, порождаемость, избыточность, согласованность, композиция, соединение, язык выборки, исчисление предикатов, безопасность, целостность данных.
1. Реляционная модель и нормальная форма
1.1. Введение
Эта статья посвящается применению элементарной теории отношений к системам, которые обеспечивают совместный доступ к большим банкам форматированных данных. За исключением статьи Чайлдса [1], основной областью применения отношений к системам данных являются дедуктивные системы ответов на вопросы. В статье Ливейна и Марона [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. Проекты подчинены Деталям
|
Файл |
Сегмент |
Поля |
|
F |
ДЕТАЛЬ |
номер детали |
|
|
|
наименование детали |
|
|
|
описание детали |
|
|
|
имеющееся количество |
|
|
|
заказанное количество |
|
|
ПРОЕКТ |
номер проекта |
|
|
|
наименование проекта |
|
|
|
описание проекта |
|
|
|
подтвержденное количество |
Структура 2. Детали подчинены Проектам
|
Файл |
Сегмент |
Поля |
|
F |
ПРОЕКТ |
номер проекта |
|
|
|
наименование проекта |
|
|
|
описание проекта |
|
|
ДЕТАЛЬ |
номер детали |
|
|
|
наименование детали |
|
|
|
описание детали |
|
|
|
имеющееся количество |
|
|
|
заказанное количество |
|
|
|
подтвержденное количество |
Структура 3. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Проектам
|
Файл |
Сегмент |
Поля |
|
F |
ДЕТАЛЬ |
номер детали |
|
|
|
наименование детали |
|
|
|
описание детали |
|
|
|
имеющееся количество |
|
|
|
заказанное количество |
|
G |
ПРОЕКТ |
номер проекта |
|
|
|
наименование проекта |
|
|
|
описание проекта |
|
|
ДЕТАЛЬ |
номер детали |
|
|
|
подтвержденное количество |
Структура 4. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Деталям
|
Файл |
Сегмент |
Поля |
|
F |
ДЕТАЛЬ |
номер детали |
|
|
|
наименование детали |
|
|
|
описание детали |
|
|
|
имеющееся количество |
|
|
|
заказанное количество |
|
|
ПРОЕКТ |
номер проекта |
|
|
|
подтвержденное количество |
|
G |
ПРОЕКТ |
номер проекта |
|
|
|
наименование проекта |
|
|
|
описание проекта |
Структура 5. Детали, Проекты и Связь назначения деталей проектам наравне
|
Файл |
Сегмент |
Поля |
|
F |
ДЕТАЛЬ |
номер детали |
|
|
|
наименование детали |
|
|
|
описание детали |
|
|
|
имеющееся количество |
|
|
|
заказанное количество |
|
G |
ПРОЕКТ |
номер проекта |
|
|
|
наименование проекта |
|
|
|
описание проекта |
|
H |
ПОДТВЕРЖДЕНИЕ |
номер детали |
|
|
|
номер проекта |
|
|
|
подтвержденное количество |
Теперь рассмотрим проблему выборкиномера детали, названия детали и количества деталей этого типа для каждой детали, используемой в проекте с названием "альфа". Следующие наблюдения могут быть сделаны независимо от того, какая конкретная информационная система с древовидной организацией информации выбирается для решения этой проблемы. Если программа P разрабатывается для ее решения на основе использования одной из приведенных выше структур (т.е. P не определяет, какая структура задана на самом деле), то при любом выборе работа P будет неудачной для, по меньшей мере, трех оставшихся структур. Более точно, если P следует структуре 5, то ей не удастся работать со всеми другими структурами; если P следует структуре 3 или 4, то ей, по меньшей мере, не удастся работать со структурами 1,2 и 5; если P следует структуре 1 или 2, ей, как минимум , не удастся работать со структурами 3, 4 и 5. В каждом случае причина проста. Если отсутствуют проверки для определения реально заданной структуры, работа P заканчивается неудачей по причине попытки перехода по ссылке к несуществующему файлу (в доступных сегодня системах это трактуется как ошибка) или из-за отсутствия перехода по ссылке к файлу, содержащему нужную информацию. Если читатель не верит в это, ему рекомендуется попробовать написать пробные программы для решения этой простой проблемы.
Поскольку в общем случае непрактично создавать прикладные программы, которые проверяют все древовидные структуризации, допускаемые системой, эти программы перестают работать после необходимых изменений структуры.
Системы, которые предоставляют пользователям сетевую модель данных, порождают аналогичные трудности. И в случае деревьев, и в случае сетей пользователь (или его программа) должен обеспечить набор путей доступа к данным. Неважно, находятся ли эти пути в точном соответствии с определяемыми ссылками путями в хранимом представлении (в IDS это соответствие является предельно простым, в TDMS - совсем наоборот). В результате, независимо от конкретного вида хранимого представления интерактивная деятельность и программы становятся зависимыми от существования пользовательских путей доступа.
Одно из решений состоит в следовании той политике, что определенный пользователем путь доступа не может выйти из употребления до тех пор, пока существуют программы, использующие этот путь доступа. Такая политика непрактична, поскольку число путей доступа в модели, общей для сообщества пользователей банка данных, в конце концов станет чрезмерно велико.