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

Эдвард Сьоре

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

Database Design  
and Implementation

Edward Sciore

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

Эвард Сьоре

Москва, 2021

УДК 004.655
ББК 32.973.26-018.2
 
C96

Эдвард Сьоре
C96 Проектирование и реализация систем управления базами данных / 
пер. с анг. А. Н. Киселева;  научн. ред. Е. В. Рогов. – М.: ДМК Пресс, 
2021. – 466 с.: ил.

ISBN 978-5-97060-488-5

В книге рассматриваются системы баз данных с точки зрения разработчика 
ПО. Автор подробно разбирает исходный код полностью функциональной, но при 
этом очень простой для изучения системы баз данных SimpleDB и предлагает 
читателям, изменяя отдельные ее компоненты, разобраться в том, к чему это 
приведет. Это отличный способ погрузиться в тему и изучить, как работают базы 
данных, на уровне исходного кода.
В начале книги приводится краткий обзор систем баз данных; рассказывается о том, как написать приложение базы данных на Java. Далее подробно 
описываются отдельные компоненты типичной системы баз данных, начиная 
с самого низкого уровня абстракции (управление дисками и диспетчер файлов) 
и заканчивая самым верхним (интерфейс клиента JDBC). Заключительные главы 
посвящены эффективной обработке запросов. В конце каждой главы приводятся 
практические упражнения и список дополнительных ресурсов.
Издание предназначено для студентов вузов, изучающих курс информатики, 
а также всех, кто хочет научиться создавать системы баз данных. Предполагается, 
что читатель знаком с основами программирования на Java.

УДК 004.655
ББК 32.973.26-018.2

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or 
transmitted in any form or by any means, without the prior written permission of the publisher, 
except in the case of brief quotations embedded in critical articles or reviews.

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

©  Springer Nature Switzerland AG 2021
© Оформление, издание, перевод, ДМК Пресс, 2021
ISBN  (анг.) 978-3-030-33835-0
ISBN  (рус.) 978-5-97060-488-5

Оглавление

Предисловие от издательства .....................................................................9

Вступление ........................................................................................................10

Об авторе ...........................................................................................................14

Глава 1. Системы баз данных ....................................................................15
1.1. Зачем нужны системы баз данных? ..............................................................15
1.2. Система баз данных Derby .............................................................................20
1.3. Механизмы баз данных .................................................................................22
1.4. Система баз данных SimpleDB ......................................................................24
1.5. Версия SQL, поддерживаемая в SimpleDB ....................................................25
1.6. Итоги ...............................................................................................................26
1.7. Для дополнительного чтения ........................................................................27
1.8. Упражнения ....................................................................................................27

Глава 2. JDBC .....................................................................................................29
2.1. Ядро JDBC .......................................................................................................29
2.2. Дополнительные инструменты JDBC ............................................................39
2.4. Итоги ...............................................................................................................57
2.5. Для дополнительного чтения ........................................................................59
2.6. Упражнения ....................................................................................................59

Глава 3. Управление дисками и файлами .............................................61
3.1. Долговременное хранилище данных ...........................................................61
3.2. Интерфейс блочного доступа к диску ...........................................................73
3.3. Интерфейс файлов для доступа к диску .......................................................74
3.4. Система баз данных и операционная система ............................................78
3.5. Диспетчер файлов в SimpleDB ......................................................................79
3.6. Итоги ...............................................................................................................86
3.7. Для дополнительного чтения ........................................................................88
3.8. Упражнения ....................................................................................................89

Глава 4. Управление памятью....................................................................93
4.1. Два принципа управления памятью баз данных .........................................93
4.2. Управление журналом ...................................................................................95
4.3. Диспетчер журнала в SimpleDB .....................................................................97

4.4. Управление пользовательскими данными .................................................102
4.5. Диспетчер буферов в SimpleDB ...................................................................107
4.6. Итоги .............................................................................................................114
4.7. Для дополнительного чтения ......................................................................114
4.8. Упражнения ..................................................................................................115

Глава 5. Управление транзакциями ......................................................118
5.1. Транзакции ...................................................................................................118
5.2. Использование транзакций в SimpleDB .....................................................121
5.3. Управление восстановлением .....................................................................123
5.4. Диспетчер конкуренции ..............................................................................138
5.5. Реализация транзакций в SimpleDB ...........................................................157
5.6. Итоги .............................................................................................................161
5.7. Для дополнительного чтения ......................................................................163
5.8. Упражнения ..................................................................................................165

Глава 6. Управление записями ................................................................172
6.1. Архитектура диспетчера записей ...............................................................172
6.2. Реализация файла с записями ....................................................................178
6.3. Страницы записей в SimpleDB ....................................................................183
6.4. Сканирование таблиц в SimpleDB ...............................................................191
6.5. Итоги .............................................................................................................196
6.6. Для дополнительного чтения ......................................................................197
6.7. Упражнения ..................................................................................................198

Глава 7. Управление метаданными .......................................................201
7.1. Диспетчер метаданных ................................................................................201
7.2. Метаданные таблиц ......................................................................................202
7.4. Статистические метаданные .......................................................................207
7.5. Метаданные индексов ..................................................................................212
7.6. Реализация диспетчера метаданных ..........................................................215
7.7. Итоги ..............................................................................................................219
7.8. Для дополнительного чтения ......................................................................220
7.9. Упражнения ..................................................................................................221

Глава 8. Обработка запросов ...................................................................223
8.1. Реляционная алгебра ...................................................................................223
8.2. Образ сканирования ....................................................................................226
8.3. Обновляемые образы ...................................................................................229
8.4. Реализация образов сканирования.............................................................230
8.5. Конвейерная обработка запросов ...............................................................235
8.6. Предикаты ....................................................................................................236
8.7. Итоги .............................................................................................................242
8.8. Для дополнительного чтения ......................................................................243
8.9. Упражнения ..................................................................................................244

6  Оглавление

Глава 9. Синтаксический анализ .............................................................247
9.1. Синтаксис и семантика ................................................................................247
9.2. Лексический анализ .....................................................................................248
9.3. Лексический анализатор в SimpleDB ..........................................................250
9.4. Грамматика ...................................................................................................253
9.5. Алгоритм рекурсивного спуска ...................................................................256
9.6. Добавление действий в синтаксический анализатор ................................258
9.7. Итоги .............................................................................................................268
9.8. Для дополнительного чтения ......................................................................269
9.9. Упражнения ..................................................................................................270

Глава 10. Планирование ............................................................................275
10.1. Проверка .....................................................................................................275
10.2. Стоимость выполнения дерева запросов .................................................276
10.3. Планы ..........................................................................................................281
10.4. Планирование запроса ..............................................................................285
10.5. Планирование операций изменения ........................................................288
10.6. Планировщик в SimpleDB ..........................................................................290
10.7. Итоги ...........................................................................................................294
10.8. Для дополнительного чтения ....................................................................295
10.9. Упражнения ................................................................................................295

Глава 11. Интерфейсы JDBC .....................................................................300
11.1. SimpleDB API ...............................................................................................300
11.2. Встроенный интерфейс JDBC ....................................................................302
11.3. Вызов удаленных методов .........................................................................306
11.4. Реализация удаленных интерфейсов .......................................................309
11.5. Реализация интерфейсов JDBC .................................................................311
11.6. Итоги ...........................................................................................................313
11.7. Для дополнительного чтения ....................................................................313
11.8. Упражнение ................................................................................................314

Глава 12. Индексирование ........................................................................317
12.1. Ценность индексирования ........................................................................317
12.2. Индексы в SimpleDB ...................................................................................320
12.4. Расширяемое хеширование .......................................................................326
12.5. Индексы на основе B-дерева .....................................................................331
12.6. Реализации операторов с поддержкой индексов ....................................351
12.7. Планирование обновления индекса .........................................................356
12.8. Итоги ...........................................................................................................359
12.9. Для дополнительного чтения ....................................................................360
12.10. Упражнения ..............................................................................................362

Глава 13. Материализация и сортировка ...........................................367
13.1. Цель материализации ................................................................................367

Оглавление  7

13.2. Временные таблицы...................................................................................368
13.3. Материализация .........................................................................................369
13.4. Сортировка .................................................................................................372
13.5. Группировка и агрегирование ...................................................................384
13.6. Соединение слиянием ...............................................................................389
13.7. Итоги ...........................................................................................................395
13.8. Для дополнительного чтения ....................................................................396
13.9. Упражнения ................................................................................................397

Глава 14. Эффективное использование буферов ...........................401
14.1. Использование буферов в планах запросов .............................................401
14.2. Многобуферная сортировка ......................................................................402
14.3. Многобуферное прямое произведение ....................................................404
14.4. Определение необходимого количества буферов ...................................406
14.5. Реализация многобуферной сортировки .................................................407
14.6. Реализация многобуферного прямого произведения .............................408
14.7. Соединение хешированием .......................................................................412
14.8. Сравнение алгоритмов соединения .........................................................416
14.9. Итоги ...........................................................................................................419
14.10. Для дополнительного чтения ..................................................................420
14.11. Упражнения ..............................................................................................420

Глава 15. Оптимизация запросов ...........................................................424
15.1. Использование буферов в планах запросов .............................................424
15.2. Необходимость оптимизации запросов ...................................................431
15.3. Структура оптимизатора запросов ...........................................................434
15.4. Поиск наиболее перспективного дерева запроса ....................................435
15.5. Поиск наиболее эффективного плана ......................................................445
15.6. Объединение двух этапов оптимизации ..................................................446
15.7. Объединение блоков запроса ....................................................................454
15.8. Итоги ...........................................................................................................455
15.9. Для дополнительного чтения ....................................................................457
15.10. Упражнения ..............................................................................................458
Предметный указатель ..............................................................................461

8  Оглавление

Предисловие от издательства

Отзывы и пОжелания

Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете 
об этой книге – что понравилось или, может быть, не понравилось. Отзывы 
важны для нас, чтобы выпускать книги, которые будут для вас максимально 
полезны.
Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на 
страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также 
можно послать письмо главному редактору по адресу dmkpress@gmail.com; 
при этом напишите название книги в теме письма.
Если вы являетесь экспертом в какой-либо области и заинтересованы 
в написании новой книги, заполните форму на нашем сайте по адресу 
http://dmkpress.com/authors/publish_book/ или напишите в издательство 
по адресу dmkpress@gmail.com.

СпиСОк ОпечатОк

Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете 
ошибку в одной из наших книг – возможно, ошибку в основном тексте или 
программном коде, – мы будем очень благодарны, если вы сообщите нам 
о ней. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги.
Если вы найдете какие-либо ошибки в тексте, пожалуйста, сообщите о них 
главному редактору по адресу dmkpress@gmail.com, и мы исправим это 
в следующих тиражах.

нарушение автОрСких прав

Пиратство в интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной 
публикацией какой-либо из наших книг, пожалуйста, пришлите нам ссылку 
на интернет-ресурс, чтобы мы могли применить санкции.
Ссылку на подозрительные материалы можно прислать по адресу электронной почты dmkpress@gmail.com.
Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.

Вступление

Системы баз данных широко распространены в корпоративном мире как видимый инструмент – сотрудники часто напрямую взаимодействуют с такими 
системами, чтобы отправить данные или создать отчеты. Но не менее часто 
они используются как невидимые компоненты программных систем. Например, представьте веб-сайт электронной коммерции, использующий базу 
данных на стороне сервера для хранения информации о клиентах, товарах 
и продажах. Или вообразите систему навигации GPS, использующую встроенную базу данных для управления картами дорог. В обоих этих примерах 
система баз данных скрыта от пользователя; с ней взаимодействует только 
код приложения.
С точки зрения разработчика программного обеспечения, обучение непосредственному использованию базы данных выглядит скучным занятием, потому что современные системы баз данных имеют интеллектуальные 
пользовательские интерфейсы, упрощающие создание запросов и отчетов. 
С другой стороны, включение поддержки базы данных в программное приложение выглядит более захватывающим, поскольку открывает множество 
новых и неисследованных возможностей.
Но что означает «включение поддержки базы данных»? Система баз данных обеспечивает множество новых возможностей, таких как долговременное хранение данных, поддержка транзакций и обработка запросов. Какие 
из этих возможностей необходимы, и как их интегрировать в программное 
обеспечение? Предположим, например, что программиста просят изменить 
существующее приложение и добавить возможность сохранения состояния, 
повысить надежность или эффективность доступа к файлам. Программист 
оказывается перед выбором между несколькими архитектурными вариантами. Он может:
 
 приобрести полноценную систему баз данных общего назначения, а затем изменить приложение и организовать в нем подключение к базе 
данных в качестве клиента;
 
 взять узкоспециализированную систему, реализующую только нужные 
функции, и встроить ее код непосредственно в приложение;
 
 написать необходимые функции самостоятельно.
Чтобы сделать правильный выбор, программист должен понимать последствия работы каждого из этих вариантов. Он должен знать не только то, что 
делают системы баз данных, но также как они это делают и почему.
В этой книге мы рассмотрим системы баз данных с точки зрения разработчика программного обеспечения. Это позволит нам понять, почему системы баз 
данных являются такими, какие они есть. Конечно, важно уметь писать запросы, но не менее важно знать, как они обрабатываются. Мы должны не просто 
уметь использовать JDBC, но и знать и понимать, почему API содержит именно 

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

Организация книги

Первые две главы содержат краткий обзор систем баз данных и принципов 
их использования. Глава 1 обсуждает назначение и особенности системы баз 
данных и знакомит с системами Derby и SimpleDB. Глава 2 рассказывает, как 
написать приложение базы данных на Java. В ней будут представлены основы 
JDBC – фундаментального API для программ на Java, взаимодействующих с базами данных.
В главах 3–11 рассматривается внутреннее устройство типичного механизма 
базы данных. Каждая из этих глав охватывает отдельный компонент, начиная 
с самого низкого уровня абстракции (диспетчер дисков и файлов) и заканчивая 
интерфейсом самого верхнего уровня (интерфейс клиента JDBC). При обсуждении каждого компонента объясняются вероятные проблемы и рассмат риваются 
возможные проектные решения. Благодаря такому подходу вы сможете увидеть, какие услуги предоставляет каждый компонент и как он взаимодействует 
друг с другом. На протяжении этой части книги вы будете наблюдать постепенное развитие простой, но вполне функциональной системы.
Остальные четыре главы посвящены эффективной обработке запросов. 
В них исследуются сложные приемы и алгоритмы, предназначенные для замены простых решений, описанных в предыдущей части. Среди всего прочего 
здесь рассматриваются: индексация, сортировка, интеллектуальная буферизация и оптимизация запросов.

предварительные требОвания

Эта книга предназначена для студентов вузов старших курсов, изучающих курс 
информатики. Предполагается, что читатель знаком с основами программирования на Java, например он умеет использовать классы из java.util, в частности коллекции и ассоциативные массивы. Более сложные понятия из мира 
Java (такие как RMI и JDBC) будут полностью объяснены в тексте.
Сведения, представленные в данной книге, обычно изучаются в углубленном курсе по системам баз данных. Однако в моей преподавательской практике их с успехом усваивали студенты, не имеющие опыта работы с базами 
данных. Поэтому можно сказать, что для понимания идей, представленных 
в этой книге, не требуется иметь какие-либо знания о базах данных, кроме поверхностного знакомства с SQL. Впрочем, студенты, незнакомые с SQL, также 
смогут усвоить необходимые им знания.

прОграммнОе ОбеСпечение SimpleDB

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

дент должен написать всю систему баз данных в своей курсовой работе, так же, 
как он написал бы целый компилятор при изучении курса по компиляторам. 
Однако системы баз данных намного сложнее компиляторов, поэтому такой 
подход выглядит непрактичным. Поэтому я решил сам написать простую, но 
полнофункциональную систему баз данных под названием SimpleDB и дать 
возможность студентам применить свои знания для изучения кода SimpleDB 
и его изменения.
По своим возможностям и структуре SimpleDB «выглядит» как коммерческая система баз данных. Функционально это многопользовательский сервер 
баз данных с поддержкой транзакций, который выполняет операторы SQL 
и взаимодействует с клиентами через интерфейс JDBC. Конструктивно она 
содержит те же основные компоненты, что и коммерческая система с похожим API. Каждому компоненту SimpleDB посвящена отдельная глава в книге, 
где обсуждается код компонента и проектные решения, стоящие за ним.
SimpleDB является прекрасным наглядным пособием благодаря небольшому объему кода, который легко читается и модифицируется. В ней отсутствует 
необязательная функциональность, реализована только малая часть языка SQL 
и используются лишь самые простые (и часто очень неоптимальные) алгоритмы. Как результат перед студентами открывается широкое поле возможностей 
расширения системы дополнительными функциями и применения более эффективных алгоритмов; многие из этих расширений предлагаются в конце 
каждой главы как упражнения.
Исходный код SimpleDB можно получить по адресу http://cs.bc.edu/~sciore/
simpledb. Подробная информация об установке и использовании SimpleDB 
представлена на этой же веб-странице и в главе 1. Я с благодарностью приму 
любые предложения по улучшению кода, а также сообщения о любых ошибках. 
Пишите мне по адресу sciore@bc.edu.

СпиСОк дОпОлнительных реСурСОв в кОнце каждОй главы

Главная задача этой книги – дать ответы на два основных вопроса: какие 
функции предоставляют системы баз данных и какие алгоритмы и проектные 
решения лучше всего подходят для их реализации? Книгами, посвященными 
различным аспектам этих вопросов, можно заполнить не одну книжную полку. Поскольку ни одна книга не может охватить все и вся, я решил представить только те алгоритмы и методы, которые наиболее четко иллюстрируют 
соответствующие проблемы. Моя главная цель – познакомить вас с основными принципами, даже если придется опустить (или сократить) обсуждение 
более жизнеспособной версии того или иного метода. Поэтому в конце каждой главы имеется раздел «Для дополнительного чтения». В этих разделах 
обсуждаются интересные идеи и направления исследований, не упомянутые 
в тексте, и даются ссылки на соответствующие веб-страницы, исследовательские статьи, справочные руководства и книги.

12  
Вступление

упражнения в кОнце каждОй главы 

В конце каждой главы дается несколько упражнений. Некоторые, имеющие 
целью закрепить полученные знания, можно решить карандашом на бумаге. 
В других предлагаются интересные модификации в SimpleDB, и многие из 
них могут служить отличными программными проектами. Для большинства 
упражнений я написал свои решения. Если вы преподаете курс по этому учебнику и хотите получить копию руководства с решениями, напишите мне по 
адресу sciore@bc.edu.

Вступление  13

Об авторе

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