Теория баз данных

Рассмотрены основные понятия теории баз 
данных, эволюция программных систем управления данными. Дано понятие модели данных, 
а также представлен обзор ее разновидностей. 
Подробно описаны реляционная модель данных 
и базисные средства манипулирования реляционными данными, реляционное исчисление, 
алгебра Кодда, функциональные зависимости 
и декомпозиция без потерь. Уделено внимание 
проектированию реляционных баз данных и таким подходам, как нормализация, ER-диаграммы, семантические модели.

В. В. Кукарцев, Р. Ю. Царев, О. А. Антамошкин 
ТЕОРИЯ БАЗ ДАННЫХ

Учебник

ИНСТИТУТ КОСМИЧЕСКИХ  
И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

В. В. Кукарцев, Р. Ю. Царев, О. А. Антамошкин     
ТЕОРИЯ БАЗ ДАННЫХ

 

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
 
В. В. Кукарцев  
Р. Ю. Царев  
О. А. Антамошкин  
 
 
 
ТЕОРИЯ БАЗ ДАННЫХ 
 
 
 
 
 
Допущено Учебно-методическим советом  
Сибирского федерального университета в качестве учебника  
для студентов, обучающихся по направлению подготовки бакалавров 
09.03.04 – Программная инженерия (протокол № 9 от 14.06.2017 г.) 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2017 

 

УДК 004.65(07) 
ББК 32.972.53я73 
К896 
 
 
 
 
Р е ц е н з е н т ы:  
С. И. Сенашов, доктор физико-математических наук, профессор, 
заведующий кафедрой информационных экономических систем Сибирского государственного аэрокосмического университета имени 
академика М. Ф. Решетнева; 
С. А. Качанов, доктор технических наук, профессор, заместитель 
начальника Всероссийского научно-исследовательского института по 
проблемам гражданской обороны и чрезвычайных ситуаций МЧС России (Федеральный центр науки и высоких технологий), генеральный 
конструктор 
 
 
Кукарцев, В. В. 
К896 
 
Теория баз данных : учебник / В. В. Кукарцев, Р. Ю. Царев,  
О. А. Антамошкин. – Красноярск : Сиб. федер. ун-т, 2017. – 180 с. 
ISBN 978-5-7638-3621-9 
 
Рассмотрены основные понятия теории баз данных, эволюция программных систем управления данными. Дано понятие модели данных,  
а также представлен обзор ее разновидностей. Подробно описаны реляционная модель данных и базисные средства манипулирования реляционными 
данными, реляционное исчисление, алгебра Кодда, функциональные зависимости и декомпозиция без потерь. Уделено внимание проектированию реляционных баз данных и таким подходам, как нормализация, ER-диаграммы, 
семантические модели. 
Предназначен студентам направления 090304 «Программная инженерия». 
 
Электронных вариант издания см.:  
УДК  004.65(07) 
http://catalog.sfu-kras.ru  
ББК  32.972.53я73 
  
 
 
 
 
 
ISBN 978-5-7638-3621-9 
 
 
© Сибирский федеральный университет, 2017 
 

ОГЛАВЛЕНИЕ 

3 

 
 
 

ОГЛАВЛЕНИЕ 

 
 
1. Эволюция устройств внешней памяти и программных систем 
управления данными .................................................................................... 5 
1.1. Устройства внешней памяти ................................................................... 5 
1.2. Файловые системы ................................................................................... 9 
1.3. Потребности информационных систем ............................................... 13 

2. Понятие модели данных. Обзор разновидностей моделей данных ... 21 
2.1. Модель данных ....................................................................................... 21 
2.2. Модель данных  инвертированных таблиц ......................................... 22 
2.3. Современные модели данных ............................................................... 27 
2.4. Объектно-ориентированная модель данных ....................................... 28 

3. Реляционная модель данных .................................................................... 34 
3.1. Основные понятия реляционных баз данных ..................................... 34 
3.2. Общая характеристика реляционной модели ...................................... 39 

4. Базисные средства манипулирования реляционными данными: 
реляционная алгебра Кодда ...................................................................... 41 
4.1. Общая интерпретация реляционных операций ................................... 42 
4.2. Специальные реляционные операции .................................................. 44 

5. Базисные средства манипулирования  реляционными данными:  
реляционное исчисление ............................................................................ 52 
5.1. Исчисление кортежей ............................................................................ 54 
5.2. Исчисление доменов .............................................................................. 54 

6. Элементы теории реляционных баз данных: функциональные 
зависимости и декомпозиция без потерь ................................................ 56 
6.1. Функциональные зависимости ............................................................. 57 
6.2. Декомпозиция без потерь  и функциональные зависимости ............. 61 

7. Проектирование реляционных баз данных на основе принципов 
нормализации: первые шаги нормализации ......................................... 67 
7.1. ПроектированиЕ базы данных .............................................................. 67 
7.2. Возможная декомпозиция ..................................................................... 72 
7.3. Приведение отношения к ВCNF не должно быть самоцелью ........... 73 

ОГЛАВЛЕНИЕ 

4 

8. Проектирование  реляционных баз данных  с использованием 
семантических моделей: ER-диаграммы ............................................... 78 
8.1. Ограниченность реляционной модели при проектировании баз 
данных ............................................................................................................ 78 
8.2. Нормальные формы ER-диаграмм ....................................................... 81 
8.3. Более сложные элементы ER-модели .................................................. 86 
8.4. Основные понятия ER-модели .............................................................. 90 
8.5. Получение реляционной схемы  из ER-диаграммы ........................... 94 

9. Проектирование реляционных баз данных с использованием 
семантических моделей: диаграммы классов языка UML ................ 97 
9.1. Основные понятия диаграмм классов UML ........................................ 97 
9.2. Ограничения целостности и язык OCL .............................................. 107 
9.3. Получение схемы реляционной базы данных   
из диаграммы классов UML ....................................................................... 109 

10. Общая организация СУБД. Физическое представление 
реляционных баз данных во внешней памяти.  
Индексные структуры .............................................................................. 112 
10.1. Основные понятия, цели  и общая организация System R ............. 112 
10.2. Принципы организации данных во внешней памяти  
в SQL-ориентированных СУБД ................................................................. 118 

11. Общая характеристика оператора SELECT и организация  
списка ссылок на таблицы в разделе FROM ....................................... 130 
11.1. Скалярные выражения ....................................................................... 130 
11.2. Общая структура оператора выборки в языке SQL ........................ 139 
11.3. Табличное выражение, спецификация запроса и выражение 
запросов ........................................................................................................ 144 

12. Предикаты раздела WHERE оператора SELECT ............................ 147 
12.1. Логические выражения раздела WHERE......................................... 147 
12.2. Предикаты выбора ............................................................................. 153 

13. Объектные расширения ......................................................................... 166 
13.1. Объектная модель SQL ...................................................................... 166 
13.2. Цели объектной модели SQL ............................................................ 168 
13.3. Типизированные таблицы ................................................................. 169 

Список литературы ....................................................................................... 178 

1. ЭВОЛЮЦИЯ УСТРОЙСТВ ВНЕШНЕЙ ПАМЯТИ И ПРОГРАММНЫХ СИСТЕМ УПРАВЛЕНИЯ ДАННЫМИ 

5 

 
 
 

1. ЭВОЛЮЦИЯ УСТРОЙСТВ  
ВНЕШНЕЙ ПАМЯТИ И ПРОГРАММНЫХ СИСТЕМ  
УПРАВЛЕНИЯ ДАННЫМИ 

 
 
 
Рассмотрим предпосылки появления в компьютерах устройств 
внешней памяти, их важность для организации информационных систем 
дисковых устройств с подвижными магнитными головками, особенности 
организации и основное функциональное назначение одного из ключевых 
компонентов современных операционных систем – систем управления 
файлами. Естественные требования информационных систем к средствам 
управления данными во внешней памяти приводят к необходимости наличия систем управления базами данных (СУБД). Определим основные черты, которыми должны обладать СУБД.  
 
 
 
1.1. УСТРОЙСТВА ВНЕШНЕЙ ПАМЯТИ 
 
 
В самом широком смысле информационная система представляет 
собой программный комплекс, функции которого состоят в поддержке надежного хранения информации в памяти компьютера, выполнении специфических для данного приложения преобразований информации и/или вычислений, предоставлении пользователям удобного и легко осваиваемого 
интерфейса. Обычно объемы данных, с которыми приходится иметь дело 
таким системам, достаточно велики, а сами данные обладают сложной 
структурой. Классическими примерами информационных систем являются 
банковские, а также резервирования авиационных или железнодорожных 
билетов, мест в гостиницах и т. д.  
О надежном и долговременном хранении информации можно говорить только при наличии запоминающих устройств, сохраняющих информацию после выключения электропитания. Оперативная (основная) память 
этим свойством обычно не обладает. В первые десятилетия развития  
вычислительной техники использовалось два вида устройств внешней  

ТЕОРИЯ БАЗ ДАННЫХ 

6 

памяти: магнитные ленты и магнитные барабаны. При этом емкость магнитных лент была достаточно велика, но по своей природе они обеспечивали последовательный доступ к данным. Емкость магнитной ленты пропорциональна ее длине. Чтобы получить доступ к требуемой порции данных, 
нужно в среднем перемотать половину ее длины. Но чисто механическую 
операцию перемотки нельзя выполнить очень быстро. Поэтому быстрый 
произвольный доступ к данным на магнитной ленте невозможен.  
Магнитный барабан представлял собой массивный металлический 
цилиндр с намагниченной внешней поверхностью и неподвижным пакетом 
магнитных головок. Такие устройства обеспечивали возможность достаточно быстрого произвольного доступа к данным, но позволяли сохранять 
их сравнительно небольшой объем. Быстрый произвольный доступ осуществлялся благодаря высокой скорости вращения барабана и наличию  
отдельной головки на каждую дорожку магнитной поверхности; ограниченность объема была обусловлена наличием всего одной магнитной  
поверхности.  
Указанные ограничения не очень существенны для систем численных расчетов. Какие реальные потребности возникают у разработчиков 
систем численных расчетов? Прежде всего для получения требуемых результатов серьезные вычислительные программы должны проработать 
достаточно долгое время (недели, месяцы и даже, может быть, годы).  
Наличие гарантии надежности со стороны производителей аппаратных 
компьютерных средств не избавляет программистов от необходимости использования программного сохранения частичных результатов вычислений, чтобы при возникновении непредвиденных сбоев аппаратуры можно 
было продолжить выполнение расчетов с некоторой контрольной точки. 
Для сохранения промежуточных результатов идеально подходят магнитные ленты: при выполнении процедуры установки контрольной точки данные последовательно сбрасываются на ленту, а при необходимости перезапуска от сохраненной контрольной точки данные также последовательно 
с ленты считываются.  
Вторая традиционная потребность численных программистов – максимально большой объем оперативной памяти. Большая оперативная память требуется, во-первых, для того, чтобы обеспечить программе быстрый доступ к большому количеству обрабатываемых данных. Во-вторых, 
сложные вычислительные программы сами могут иметь большой объем. 
Поскольку объем реально доступной в ЭВМ оперативной памяти всегда 
являлся недостаточным для удовлетворения текущих потребностей вычислений, требовалась быстрая внешняя память для организации оверлеев 
и/или виртуальной памяти. Не будем здесь вдаваться в детали организации 
этих механизмов программного расширения оперативной памяти, но заме

1. ЭВОЛЮЦИЯ УСТРОЙСТВ ВНЕШНЕЙ ПАМЯТИ И ПРОГРАММНЫХ СИСТЕМ УПРАВЛЕНИЯ ДАННЫМИ 

7 

тим, что для этого идеально подходили магнитные барабаны. Они обеспечивают быстрый доступ к внешней памяти, а для расширения оперативной 
памяти одной программы (сложные вычислительные программы, как правило, выполняются на компьютере в одиночку) большой объем внешней 
памяти не требуется.  
Даже если программа должна обработать (или произвести) большой 
объем информации, при программировании можно продумать расположение этой информации во внешней памяти, чтобы программа работала как 
можно быстрее. Развитая поддержка работы с внешней памятью со стороны общесистемных программных средств не обязательна, а иногда и вредна, поскольку приводит к дополнительным накладным расходам аппаратных ресурсов.  
Однако для информационных систем, в которых объем постоянно 
хранимых данных определяется спецификой бизнес-приложения, а потребность в текущих данных – пользователем приложения, одних только 
магнитных барабанов и лент недостаточно. Емкость магнитного барабана 
просто не позволяет долговременно хранить данные большого объема. Что 
же касается лент, то представьте себе состояние человека, который, стоя  
у билетной кассы, должен дожидаться полной перемотки магнитной ленты. Естественным требованием к таким системам является обеспечение 
высокой средней скорости выполнения операций при наличии больших 
объемов данных.  
Именно требования к устройствам внешней памяти со стороны бизнес-приложений вызвали появление устройств внешней памяти со съемными пакетами магнитных дисков и подвижными головками чтения/записи, что явилось революцией в истории вычислительной техники. 
Эти устройства памяти обладали существенно большей емкостью, чем 
магнитные барабаны (за счет наличия нескольких магнитных поверхностей), обеспечивали удовлетворительную скорость доступа к данным в режиме произвольной выборки, а возможность смены дискового пакета на 
устройстве позволяла иметь архив данных практически неограниченного 
объема.  
Магнитные диски представляют собой пакеты магнитных пластин 
(поверхностей), между которыми на одном рычаге двигается пакет магнитных головок (рис. 1.1). Шаг движения пакета головок является дискретным, и каждому положению пакета головок логически соответствует 
цилиндр пакета магнитных дисков. На каждой поверхности цилиндр «высекает» дорожку, так что каждая поверхность содержит число дорожек, 
равное числу цилиндров. При разметке магнитного диска (специальном 
действии, предшествующем использованию диска) каждая дорожка размечается на одно и то же количество блоков. Таким образом, предельная  

ТЕОРИЯ БАЗ ДАННЫХ 

8 

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

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

1. ЭВОЛЮЦИЯ УСТРОЙСТВ ВНЕШНЕЙ ПАМЯТИ И ПРОГРАММНЫХ СИСТЕМ УПРАВЛЕНИЯ ДАННЫМИ 

9 

режим работы не позволял или очень затруднял поддержание на одном 
внешнем носителе нескольких архивов долговременно хранимой информации. Кроме того, каждой прикладной программе приходилось решать 
проблемы именования частей данных и структуризации данных во внешней памяти.  
 
 
 
1.2. ФАЙЛОВЫЕ СИСТЕМЫ 
 
 
Историческим шагом стал переход к использованию систем управления файлами. С точки зрения прикладной программы файл – это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные. Правила именования файлов, способ доступа 
к данным, хранящимся в файле, и структура этих данных зависят от конкретной системы управления файлами и, возможно, от типа файла. Система управления файлами берет на себя распределение внешней памяти, 
отображение имен файлов в соответствующие адреса внешней памяти  
и обеспечение доступа к данным.  
Рассмотрим историю файловых систем, их основные черты и области разумного применения. Однако сначала сделаем два замечания.  
Во-первых, в области управления файлами исторически существует некоторая терминологическая путаница. Термин «файловая система» (file system) используется для обозначения программной системы, управляющей 
файлами, и архива файлов, хранящегося во внешней памяти. Было бы 
лучше в первом случае использовать термин «система управления файлами», оставив за термином «файловая система» только второе значение. 
Однако принятая практика заставляет использовать термин «файловая система» в обоих смыслах. Надеемся, что точный смысл термина будет понятен из контекста. (Заметим, что среди непрофессионалов аналогичная путаница возникает при использовании терминов «база данных» и «система 
управления базами данных»). Во-вторых, ограничимся описанием свойств 
так называемых традиционных файловых систем, не обсуждая особенности современных систем с повышенной надежностью, поскольку это заставило бы нас сильно отклониться от основной темы курса.  
Первая развитая файловая система была разработана специалистами 
IBM в середине 1960-х гг. для выпускавшейся компанией серии компьютеров «360». В этой системе поддерживались как чисто последовательные, 
так и индексно-последовательные файлы, а реализация во многом опиралась на возможности только появившихся к этому времени контроллеров