Основы баз данных

Введение в реляционные базы данных

2-е издание, исправленное

Кузнецов С.Д.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 004.655.3(075.8)
ББК 15
К-89
Основы баз данных / Кузнецов С.Д. - M.: Национальный Открытый Университет “ИНТУИТ”, 2016
(Основы информационных технологий)
ISBN 5-9556-00028-0

В курсе излагаются основные понятия и методы организации реляционных баз данных и
манипулирования ими, а также описываются базовые подходы к проектированию реляционных баз
данных. Вводится понятие реляционной модели данных, обсуждаются структурная,
манипуляционная и целостная составляющие модели. Обсуждаются важные аспекты теории баз
данных, связанные с функциональными зависимостями. Описываются процесс проектирования
реляционных баз данных на основе принципов нормализации, а также подходы к проектированию
реляционных баз данных с использованием диаграммных семантических моделей данных.
В первой, вводной лекции обосновывается потребность в технологии баз данных и обсуждаются
основные функции СУБД. В лекции 2 предлагается общее введение в реляционную модель данных.
Вводятся основные термины, обсуждаются структурная и целостная части модели. Лекции 3-5
посвящаются манипуляционной части реляционной модели данных. В лекции 3 описываются
классический вариант реляционной алгебры, восходящий к основоположнику реляционного подхода
Эдгару Кодду, а в лекции 4 – современная версия алгебры Криса Дейта и Хью Дарвена. В лекции 5
обсуждаются две разновидности реляционных исчислений – исчисления кортежей и доменов. В
лекции 6 приводятся основные определения, утверждения и теоремы теории реляционных баз
данных, связанные с функциональными зависимостями. В лекции 7 рассматриваются
фундаментальные методы проектирования реляционных баз данных путем нормализации отношений
на основе учета функциональных зависимостей, а лекция 8 посвящена методам дальнейшей
нормализации реляционных баз данных с принятием во внимание и многозначных зависимостей и
зависимостей проекции/соединения. Наконец, материал лекций 9-10 посвящен более практическим
методам проектирования реляционных баз данных с использованием семантических моделей
данных. Мы ограничиваемся двумя разновидностями диаграммных семантических моделей, а
именно диаграммами “сущность/связь”, введенными в обиход Питером Ченом, и диаграммами
классов языка UML. Вводятся основные понятия этих моделей и обсуждаются методы перехода от
концептуальных схем баз данных, представленных в терминах диаграммных моделей, к
реляционным схемам баз данных.

(c) ООО “ИНТУИТ.РУ”, 2005-2016
(c) Кузнецов С.Д., 2005-2016

3

Эволюция устройств внешней памяти и программных систем
управления данными

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

Устройства внешней памяти

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

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

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

4

поверхности.

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

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

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

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

Именно требования к устройствам внешней памяти со стороны бизнес-приложений

5

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

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

Рис. 1.1.  Грубая схема дискового устройства памяти с подвижными головками

При выполнении обмена с диском аппаратура выполняет три основных действия:
подвод головок к нужному цилиндру (обозначим время выполнения этого действия как

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

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

6

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

Файловые системы

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

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

Первая развитая файловая система была разработана специалистами IBM в середине
60-х гг. для выпускавшейся компанией серии компьютеров “360”. В этой системе
поддерживались как чисто последовательные, так и индексно-последовательные
файлы, а реализация во многом опиралась на возможности только появившихся к
этому времени контроллеров управления дисковыми устройствами. Контроллеры
обеспечивали возможность обмена с дисковыми устройствами порциями данных
произвольного размера, а также индексный доступ к записям файлов, и эти функции
контроллеров активно использовались в файловой системе ОS/360.

Файловая система ОS/360 обеспечила будущих разработчиков уникальным опытом
использования дисковых устройств с подвижными головками, который отражается во

7

всех современных файловых системах.

Структуры файлов

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

Во-первых, как указывалось в разделе “Устройства внешней памяти”, считывание или
запись только части блока не приводит к существенному выигрышу в суммарном
времени обмена. Во-вторых, для работы с частями блоков файловая система должна
обеспечить буферы оперативной памяти соответствующего размера, что существенно
усложняет распределение оперативной памяти. Алгоритмы распределения памяти
порциями произвольного размера плохи тем, что любой из них рано или поздно
приводит к внешней фрагментации памяти. В памяти образуется большое число
маленьких свободных фрагментов. Их совокупный размер может быть больше размера
любого требуемого буфера, но его можно выделить, только если произвести сжатие
памяти, т. е. подвижку всех занятых фрагментов таким образом, чтобы они
располагались вплотную один к другому. Во время выполнения операции сжатия
памяти нужно приостановить выполнение обменов, а сама эта операция занимает
много времени.

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

В некоторых файловых системах базовый уровень был доступен пользователю, но
чаще он прикрывался некоторым более высоким уровнем, стандартным для
пользователей. Существуют два основных подхода. При первом подходе,
свойственном, например, файловым системам операционных систем компании DEC
RSX и VMS, пользователи представляют файл как последовательность записей. Каждая
запись – это последовательность байтов, имеющая постоянный или переменный
размер. Можно читать или писать записи последовательно либо позиционировать файл
на запись с указанным номером. Некоторые файловые системы позволяют
структурировать записи на поля и объявлять некие поля ключами записи.

8

Рис. 1.2.  Схематичное изображение базового файла

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

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

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

Логическая структура файловых систем и именование файлов

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

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

9

каталогов.

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

Во многих системах управления файлами требуется, чтобы каждый архив файлов
(полное дерево каталогов) целиком располагался на одном дисковом пакете или
логическом диске – разделе физического дискового пакета, логически представляемом
в виде отдельного диска с помощью средств операционной системы. В этом случае
полное имя файла начинается с имени дискового устройства, на котором установлен
соответствующий диск. Такой способ именования использовался в файловых системах
компаний IBM и DEC; очень близки к этому и файловые системы, реализованные в
операционных системах семейства Windows компании Microsoft. Можно назвать такую
организацию поддержкой изолированных файловых систем.

Другой крайний вариант был реализован в файловых системах операционной системы
Multics. Эта система заслуживает отдельного разговора, в ней был реализован целый
ряд оригинальных идей, но мы остановимся только на особенностях организации
архива файлов. В файловой системе Multics пользователям обеспечивалась
возможность представлять всю совокупность каталогов и файлов в виде единого
дерева. Полное имя файла начиналось с имени корневого каталога, и пользователь не
обязан был заботиться об установке на дисковое устройство каких-либо конкретных
дисков. Сама система, выполняя поиск файла по его имени, запрашивала у оператора
установку необходимых дисков. Такую файловую систему можно назвать полностью
централизованной.

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

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

Компромиссное решение применяется в файловых системах ОС UNIX. На базовом

10