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

Эдвард Сьоре

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

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 содержит именно