DB Design - CL2

Question 1

Understanding RDBMS architecture

Answer 1

Теперь, после изучения вводной главы, мы можем ознакомиться с архитектурой
системы баз данных. Наша цель — “заложить фундамент”, на котором будет
строиться дальнейшее изложение. Именно на него мы будем опираться при
описании общих понятий и изучении структуры конкретных систем баз данных.
Однако это отнюдь не означает, что каждая система баз данных обязательно должна
соответствовать этому определению или что предложенная конкретная архитектура
является единственно возможной. Например, “малые” системы (см. главу 1), весьма
вероятно, не будут поддерживать все функции предложенной архитектуры. Тем не
менее, рассматриваемая архитектура с достаточной точностью описывает
большинство систем (и не только реляционных). Более того, она практически
полностью согласуется с архитектурой, предложенной исследовательской группой ANSI/SPARC (Study Group on Data Management Systems), — так называемой
архитектурой ANSI/SPARC [2.1], [2.2]. Однако здесь мы не будем придерживаться тер-
минологии ANSI/SPARC во всех деталях.
Следует отметить, что материал этой главы подобен материалу предыдущей в том
смысле, что он является основой, необходимой для полного понимания структуры и воз-
можностей современных систем баз данных. По этой причине он также носит несколько
абстрактный характер, следовательно, достаточно “академичен”. Учитывая это, как и в
случае изучения главы 1, предварительно можно бегло просмотреть настоящую главу, а
затем, по мере освоения излагаемого в книге материала, возвращаться к отдельным ее
разделам, непосредственно связанным с той или иной изучаемой темой.

ТРИ УРОВНЯ АРХИТЕКТУРЫ
Архитектура ANSI/SPARC включает три уровня: внутренний, внешний и концепту-
альный (рис. 2.1). В общих чертах они представляют собой следующее.
■ Внутренний уровень (называемый также физическим) наиболее близок к физиче
скому хранилищу информации, т.е. связан со способами сохранения информации
на физических устройствах.
■ Внешний уровень (называемый также пользовательским логическим) наиболее бли
зок к пользователям, т.е. связан со способами представления данных для отдель
ных пользователей.
■ Концептуальный уровень (называемый также общим логическим или просто логиче
ским, без дополнительного определения) является “промежуточным” уровнем ме
жду двумя первыми.

Если внешний уровень связан с индивидуальными представлениями пользователей, то
концептуальный уровень связан с обобщенным представлением пользователей. Как было
отмечено в главе 1, большинству пользователей нужна не вся база данных, а только ее
небольшая часть, поэтому может существовать несколько внешних представлений, каж-
дое из которых состоит из более или менее абстрактного представления определенной
части базы данных, и только одно концептуальное представление, состоящее из абст-
рактного представления базы данных в целом. Кроме того, и внешний, и концептуальный уровни представляют собой уровни моделирования, а внутренний служит в качестве
уровня реализации; иными словами, первые два уровня определены в терминах таких
пользовательских информационных конструкций, как записи и поля, а последний
— в терминах машинно-ориентированных конструкций наподобие битов и байтов.
Для лучшего понимания этих идей рассмотрим пример, представленный на рис. 2.2.
Здесь отображено концептуальное представление простой базы данных о персонале, а
также соответствующие ему внутреннее и два внешних представления (одно — для поль-
зователя, применяющего язык PL/I, а другое — для пользователя, применяющего язык
COBOL) 1 . Конечно, этот пример полностью гипотетичен и мало похож на реальные сис-
темы, поскольку в нем умышленно исключены многие не относящиеся к делу детали.

ВНЕШНИЙ УРОВЕНЬ
Внешний уровень — это индивидуальный уровень пользователя. Как было сказано в
главе 1, пользователь может быть прикладным программистом или конечным пользова-
телем с любым уровнем профессиональной подготовки. Особое место среди пользовате-
лей занимает администратор базы данных (АБД). В отличие от остальных пользователей,
АБД интересуют также концептуальный и внутренний уровни. Об этом еще будет сказа-
но в следующих двух разделах.
У каждого пользователя есть свой язык для работы с СУБД.
■ Для прикладного программиста это либо один из распространенных языков про-
граммирования (например, PL/I, C++ или Java), либо специальный язык рас-
сматриваемой системы. Такие оригинальные языки называют языками четвертого
поколения на том (не вполне формальном!) основании, что машинный код, язык
ассемблера и такие языки, как PL/I, можно считать языками трех первых “поко-
лений”, а оригинальные языки модернизированы по сравнению с языками третьего
поколения в такой же степени, как языки третьего поколения улучшены по срав-
нению с языком ассемблера.
Для конечного пользователя это или специальный язык запросов, или язык
специального назначения, который может быть основан на использовании
форм и меню, разработан специально с учетом требований пользователя и
может интерактивно поддерживаться некоторым оперативным приложением
(как указывалось в главе 1).

Для нашего обсуждения важно, что все эти языки включают подъязык данных, т.е.
подмножество операторов всего языка, связанное только с объектами баз данных и опе-
рациями с ними. Иначе говоря, подъязык данных встроен в базовый язык, который до-
полнительно предоставляет различные не связанные с базами данных средства, та-
кие как локальные (временные) переменные, вычислительные операции, логические
операции и т.д. Система может поддерживать любое количество базовых языков и
любое количество подъязыков данных. Однако существует один язык, который под-
держивается практически всеми сегодняшними системами. Это язык SQL, который
кратко был представлен в главе 1. Большинство систем позволяет использовать язык
SQL и интерактивно, как самостоятельный язык запросов, и в форме внедрения его
операторов в другие языки программирования, такие как PL/I и Java (подробности
приведены в главе 4).
Хотя с точки зрения архитектуры удобно различать подъязык данных и включаю-
щий его базовый язык, на практике они могут быть неразличимы настолько, насколько
это имеет отношение к пользователю. Безусловно, с точки зрения пользователя пред-
почтительнее, чтобы они были неразличимыми. Если они неразличимы или трудно
различимы, их называют сильно связанными (и сочетание этих языков именуется языком
программирования базы данных) 2 . Если они ясно и легко различаются, говорят, что эти
языки слабо связаны. В то время как некоторые коммерческие системы (включая и
конкретные продукты SQL, такие как СУБД Oracle) поддерживают сильную связь,
многие системы обеспечивают лишь слабую связь. Системы с сильной связью могли
бы предоставить пользователю более унифицированный набор возможностей, но оче-
видно, что они требуют больше усилий со стороны системных проектировщиков и раз-
работчиков, поэтому, вероятно, и сохраняется такое положение дел.
В принципе, любой подъязык данных является на самом деле комбинацией по крайней
мере двух подчиненных языков — языка определения данных (Data Definition Language —
DDL), который позволяет формулировать определения или объявления объектов базы
данных, и языка манипулирования 3 данными (Data Manipulation Language — DML),
который поддерживает операции с такими объектами или их обработку. Например, рас-
смотрим пользователя языка PL/I (см. рис. 2.2). Подъязык данных этого пользователя включает определенные средства языка PL/I, применяемые для организации взаимодей-
ствия с СУБД.
■ Язык определения данных включает некоторые описательные структуры языка
PL/I, необходимые для объявления объектов базы данных. Это сам оператор
DECLARE (или DCL), определенные типы данных языка PL/I, а также возможные
специальные дополнения для языка PL/I, предназначенные для поддержки новых
объектов, которые не предусмотрены в существующей версии языка PL/I.
■ Язык обработки данных состоит из тех выполняемых операторов языка PL/I, ко
торые передают информацию в базу данных и из нее; опять же, возможно, вклю
чая новые специальные операторы.

Примечание. В качестве уточнения следует отметить, что современный язык PL/I на
самом деле вообще не включает никаких особых средств для работы с базами данных.
Оператор языка обработки данных (оператор CALL), в частности, обычно просто обраща-
ется к СУБД (хотя такие обращения могут быть синтаксически упрощены, чтобы они
стали более дружественными по отношению к пользователю). Разговор о внедрении опе-
раторов языка SQL будет продолжен в главе 4.
Вернемся к архитектуре. Как уже отмечалось, отдельного пользователя интересует
лишь некоторая часть всей базы данных. Кроме того, представление пользователя об
этой части будет, безусловно, более абстрактным по сравнению с выбранным способом
физического хранения данных. В соответствии с терминологией ANSI/SPARC, пред-
ставление отдельного пользователя называется внешним представлением. Таким образом,
внешнее представление — это содержимое базы данных, каким его видит определенный
пользователь (т.е. для каждого пользователя внешнее представление и есть та база дан-
ных, с которой он работает). Например, пользователь из отдела кадров может рассматри-
вать базу данных как набор записей с информацией об отделах плюс набор записей с ин-
формацией о служащих, и ничего не знать о записях с информацией о материалах и их
поставщиках, с которыми работают пользователи в отделе снабжения.
В общем случае внешнее представление состоит из некоторого множества экземпля-
ров каждого из многих типов внешних записей (которые вовсе не обязательно должны
совпадать с хранимыми записями) 4 . Предоставляемый в распоряжение пользователя
подъязык данных всегда определяется в терминах внешних записей. Например, операция
выборки языка обработки данных осуществляет выборку экземпляров внешних, а не хра-
нимых записей. (Теперь становится очевидно, что термин логическая запись, употреб-
лявшийся в главе 1, на самом деле относится к внешним записям. Поэтому в дальнейшем
мы будем избегать его использования.)
Каждое внешнее представление определяется посредством внешней схемы, которая
в основном состоит из определений записей каждого из типов, присутствующих в этом
внешнем представлении (см. рис. 2.2). Внешняя схема записывается с помощью языка определения данных, являющегося подмножеством подъязыка данных пользователя.
(Поэтому язык определения данных иногда называют внешним языком определения
данных.) Например, тип внешней записи о работнике можно определить как шестисим-
вольное поле с номером работника, как поле из пяти десятичных цифр, предназначенное
для хранения данных о его зарплате, и т.д. Кроме того, может потребоваться определить
отображение между внешней и исходной концептуальными схемами (подробности —
в следующем разделе). Это отображение рассматривается в разделе 2.6.

КОНЦЕПТУАЛЬНЫЙ УРОВЕНЬ
Концептуальное представление — это представление всей информации базы данных
в несколько более абстрактной форме (как и в случае внешнего представления) по
сравнению с описанием физического способа хранения данных. Однако концептуаль-
ное представление существенно отличается от представления данных какого-либо от-
дельного пользователя. Вообще говоря, концептуальное представление — это пред-
ставление данных в том виде, какими они являются на самом деле, а не в том, какими
их вынужден рассматривать пользователь в рамках, например, определенного языка
или используемого аппаратного обеспечения.
Концептуальное представление состоит из некоторого множества экземпляров
каждого из существующих типов концептуальных записей. Например, оно может со-
стоять из набора экземпляров записей, содержащих информацию об отделах, набора
экземпляров записей, содержащих информацию о поставщиках, набора экземпляров
записей, содержащих информацию о материалах и т.д. Концептуальная запись вовсе
не обязательно должна совпадать с внешней записью, с одной стороны, и с храни-
мой записью — с другой.
Концептуальное представление определяется с помощью концептуальной схемы,
включающей определения для каждого существующего типа концептуальных записей
(см. рис. 2.2). Концептуальная схема использует другой язык определения данных —
концептуальный. Чтобы добиться независимости от данных, нельзя включать в опре-
деления концептуального языка какие-либо указания о структурах хранения или ме-
тодах доступа. Определения концептуального языка должны относиться только к
содержанию информации. Это означает, что в концептуальной схеме не должно быть
никакого упоминания о представлении хранимого файла, упорядоченности храни-
мых записей, индексировании, хэш-адресации, указателях или других подробностях
хранения данных или доступа к ним. Если концептуальная схема действительно
обеспечивает независимость от данных в этом смысле, то внешние схемы, опреде-
ленные на основе концептуальной (раздел 2.6), заведомо будут обеспечивать незави-
симость от данных.
Концептуальное представление — это представление всего содержимого базы данных,
а концептуальная схема — это определение такого представления. Однако было бы
ошибкой полагать, что концептуальная схема представляет собой не более чем набор оп-
ределений, весьма напоминающих простые определения записей в программе на языке
COBOL (или каком-либо другом языке). Определения в концептуальной схеме могут
характеризовать большое количество различных дополнительных аспектов обработки
данных, например таких, как ограничения защиты или требования поддержки целостно-
сти данных, упомянутые в главе 1. Более того, некоторые авторитетные специалисты
предлагают в качестве конечной цели создания концептуальной схемы рассматривать описание всего предприятия — не только самих его данных, но и того, как эти данные
используются, как они перемещаются внутри предприятия, для чего используются в ка-
ждом конкретном месте, какая проверка и иные типы контроля применяются к ним в
каждом отдельном случае и т.д. [2.3]. Однако необходимо подчеркнуть, что ни одна сего-
дняшняя система реально не поддерживает такого концептуального уровня, который
хотя бы немного приблизился к указанной выше степени развития 5 . В большинстве су-
ществующих систем концептуальная схема в действительности представляет собой не-
что, что лишь немного больше простого объединения всех независимых внешних схем с
привлечением дополнительных средств защиты и поддержкой правил обеспечения цело-
стности. Вероятно, со временем системы станут гораздо “интеллектуальнее” с точки зре-
ния поддержки концептуального уровня.

ВНУТРЕННИЙ УРОВЕНЬ
Третьим уровнем архитектуры является внутренний уровень. Внутреннее представле-
ние — это низкоуровневое представление всей базы данных как базы, состоящей из неко-
торого множества экземпляров каждого из существующих типов внутренних записей.
Термин внутренняя запись относится к терминологии ANSI/SPARC и означает конструк-
цию, иначе называемую хранимой записью (в дальнейшем мы будем использовать именно
этот термин). Внутреннее представление, так же как внешнее и концептуальное, отделе-
но от физического уровня, поскольку в нем не рассматриваются физические записи,
обычно называемые блоками или страницами, и физические области устройства хране-
ния, такие как цилиндры и дорожки. Другими словами, внутреннее представление пред-
полагает наличие бесконечного линейного адресного пространства. Особенности методов
отображения этого адресного пространства на физические устройства хранения в значи-
тельной степени зависят от используемой операционной системы и по этой причине не
включены в общую архитектуру. Следует отметить, что блоки (или страницы) устройства
ввода—вывода — это количество данных, передаваемых из вторичной памяти (памяти
накопителя) в основную (оперативную) память за одну операцию ввода-вывода. Обычно,
страницы имеют размер от 1 Кбайт и выше, но не больше 64 Кбайт (1 Кбайт = 1024 байт).
Внутреннее представление описывается с помощью внутренней схемы, которая опре-
деляет не только различные типы хранимых записей, но также существующие индексы,
способы представления хранимых полей, физическую упорядоченность хранимых запи-
сей и т.д. (Соответствующий простой пример также приведен на рис. 2.2; см. также при-
ложение Г.) Внутренняя схема формируется с использованием еще одного языка опреде-
ления данных — внутреннего.
Примечание. В этой книге вместо терминов внутреннее представление и внутренняя
схема обычно будут использоваться интуитивно более понятные термины хранимая
структура (или хранимая база данных) и определение структуры хранения, соответственно.
В заключение отметим, что в некоторых исключительных ситуациях прикладные
программы, в частности те из них, которые называются утилитами (о чем подробнее
будет рассказано в разделе 2.11), могут выполнять операции непосредственно на внут-
реннем, а не на внешнем уровне. Конечно, использовать такую практику не рекомендуется,
поскольку она связана с определенным риском с точки зрения защиты (игнорируются правила защиты) и сохранения целостности данных (правила целостности также игнори-
руются). К тому же такая программа будет зависеть от определения обрабатываемых дан-
ных. Однако иногда подобный подход может быть единственным способом реализации
требуемой функции или достижения необходимого быстродействия (иногда по анало-
гичным причинам приходится обращаться к средствам языка ассемблера пользователю
языка высокого уровня).

ОТОБРАЖЕНИЯ
Представленная на рис. 2.3 архитектура, кроме элементов самих трех уровней, вклю-
чает определенные отображения: отображение концептуального уровня на внутренний и
несколько отображений внешних уровней на концептуальный.
■ Отображение “концептуальный-внутренний” устанавливает соответствие между
концептуальным представлением и хранимой базой данных, т.е. описывает, как
концептуальные записи и поля представлены на внутреннем уровне. При измене
нии структуры хранимой базы данных (т.е. при внесении изменений в определение
структуры хранения) отображение “концептуальный—внутренний” также изменя
ется, с учетом того, что концептуальная схема остается неизменной. (Осуществле
ние подобных изменений входит в обязанности администратора базы данных и
может обеспечиваться самой СУБД.) Иначе говоря, чтобы обеспечивалась незави
симость от данных, результаты внесения любых изменений в схему хранения не
должны обнаруживаться на концептуальном уровне.
■ Отображение “внешний—концептуальный” определяет соответствие между неко
торым внешним представлением и концептуальным представлением. В целом,
различия, которые могут существовать между этими двумя уровнями, подобны
различиям между концептуальным представлением и хранимой базой данных.
Например, данные полей могут относиться к разным типам, названия полей и за
писей могут быть изменены, несколько концептуальных полей могут быть объе
динены в одно (виртуальное) внешнее поле и т.д. В одно и то же время допустимо
существование любого количества внешних представлений, причем одно и то же
внешнее представление может принадлежать нескольким пользователям, а разные
внешние представления — перекрываться.
Очевидно, что отображение “концептуальный—внутренний” служит основой фи-
зической независимости от данных, а отображения “внешний—концептуальный”
являются ключом к логической независимости от данных. Как было показано в
главе 1, система обеспечивает физическую независимость от данных [1.3], если
пользователи и пользовательские программы обладают невосприимчивостью к
изменениям в физической структуре хранимой базы данных. Аналогично, система
обеспечивает логическую независимость от данных [1.4], если пользователи и
пользовательские программы обладают невосприимчивостью к изменениям в ло-
гической структуре базы данных (подразумеваются изменения на концептуальном
или “общем логическом” уровне). Этот важный вопрос будет обсуждаться в гла-
вах 3 и 10.
■ Следует отметить, что большинство систем позволяет выражать одно определение
внешнего представления через другое (по существу, с помощью отображения
“внешний-внешний”), не требуя обязательного явного определения отображения каждого внешнего представления на концептуальный уровень. Эта возможность
очень полезна, если несколько представлений подобны друг другу. В частности,
аналогичная возможность предусмотрена во многих реляционных СУБД.

Question 2

Transactions: ACID

Answer 2

ТРАНЗАКЦИИ
Транзакция — это логическая единица работы; она начинается с выполнения операции
BEGIN TRANSACTION и заканчивается операцией COMMIT или ROLLBACK. На рис. 15.1
показан псевдокод транзакции, которая предназначена для перечисления суммы 100 долл.
со счета 123 на счет 456. Вполне очевидно, что операция перевода денег с одного счета на
другой, которая по самой своей сути является неразрывной, фактически требует выпол-
нения в базе данных двух отдельных операций обновления. Более того, сама база данных
на этапе между этими двумя обновлениями находится в недопустимом состоянии, в том
смысле, что она не отражает действительное состояние дел в реальном мире; вполне оче-
видно, что в банковской практике перевод денег с одного счета на другой не должен вли-
ять на суммарное количество денежных средств на рассматриваемых счетах, а в данном
примере после выполнения первого обновления сумма в 100 долл. на время “исчезает” из базы данных. Поэтому такая логическая единица работы, как транзакция, не обязательно
связана с выполнением только одной операции в базе данных. Транзакция, как правило,
чаще всего состоит из последовательности подобных операций, и назначением такой
последовательности является преобразование одного действительного состояния базы
данных в другое такое состояние; при этом не обязательно требуется, чтобы на всех про-
межуточных этапах база данных находилась в допустимом состоянии.
Итак, вполне очевидно, что в данном примере следует избегать такой ситуации, когда
одно из обновлений будет выполнено, а другое — нет, поскольку в результате база данных
останется в недопустимом состоянии. В идеале желательно иметь абсолютную гарантию
того, что будут выполнены оба обновления. Но, к сожалению, действительно предоста-
вить любую подобную гарантию невозможно, поскольку всегда имеется вероятность, что
события будут развиваться по наихудшему сценарию, мало того, это может произойти в
самый неблагоприятный момент. Например, на этапе перехода от одного обновления к
другому может произойти аварийный останов системы 1 , во время выполнения второго
обновления может возникнуть арифметическое переполнение и т.д. Но система, которая
обеспечивает управление транзакциями, хотя и не предоставляет подобную гарантию,
вполне может ее заменить другими средствами. А именно, система с поддержкой тран-
закций гарантирует, что если в транзакции будут выполнены некоторые обновления, а
затем возникнет отказ еще до того, как транзакция достигнет своего завершения, то все
эти обновления будут отменены. Поэтому транзакция либо полностью выполняется, либо
полностью отменяется (т.е. создается такая ситуация, как если бы эта транзакция вообще
не выполнялась). Благодаря этому последовательность операций, которая по самой своей
сути не является неразрывной, может быть преобразована в такую последовательность,
которая внешне кажется неразрывной.
Компонент системы, который обеспечивает такую неразрывность (или подобие не-
разрывности), называется диспетчером транзакций (для его обозначения применяются
также термины монитор обработки транзакций или ТР-монитор), а в основе организации
его работы лежат операции COMMIT и ROLLBACK, которые описаны ниже.
■ Оператор COMMIT (Зафиксировать) сигнализирует об успешном окончании тран-
закции. Он сообщает диспетчеру транзакций, что логическая единица работы
успешно завершена, база данных вновь находится (или будет находиться после
выполнения этого оператора) в непротиворечивом состоянии, а все обновления,
выполненные данной логической единицей работы, теперь могут быть зафиксиро-
ваны, т.е. внесены в базу данных.
■ Оператор ROLLBACK (Выполнить откат) сигнализирует о неудачном окончании
транзакции. Он сообщает диспетчеру транзакций, что произошла какая-то ошибка,
база данных находится в противоречивом состоянии и следует осуществить
откат всех проведенных при выполнении этой транзакции обновлений, т.е. они
должны быть отменены.

Таким образом, в приведенном примере оператор COMMIT должен быть выполнен, если
оба обновления прошли успешно, после чего внесенные в базу данных изменения
станут постоянными. Если что-то произошло не так, например, если обновление было
прервано каким-либо условием ошибки, то выполняется оператор ROLLBACK И любые
проведенные до сих пор изменения отменяются.
На основании простого примера, приведенного на рис. 15.1, можно сделать ряд важ-
ных выводов, описанных ниже.
■ Неявно заданный оператор ROLLBACK . В данном примере явно предусмотрено вы
полнение проверок на наличие ошибок и явный вызов на выполнение оператора
ROLLBACK в случае обнаружения ошибки. Но не следует предполагать (и само это
предположение не имеет смысла), что транзакции всегда включают явно заданные
проверки на случай всех возможных ошибок. Поэтому система должна вызывать
на выполнение неявно заданный оператор ROLLBACK ДЛЯ всех транзакций, кото
рые по какой-то причине окончились неудачей и не достигли этапа планового за
вершения (здесь под плановым завершением подразумевается явно заданный опера
тор COMMIT ИЛИ ROLLBACK).
■ Обработка сообщений. Типичная транзакция не только вносит (или пытается вне
сти) обновления в базу данных, но и передает конечному пользователю те или
иные сообщения, позволяющие ему узнать, что происходит. Например, можно
предусмотреть передачу сообщения “Перевод денег со счета на счет выполнен”,
если достигнут оператор COMMIT, или сообщение “Ошибка — перевод денег со
счета на счет не выполнен” в противном случае. Обработка сообщений, в свою
очередь, требует применения дополнительных средств восстановления. Более под
робную информацию по этой теме можно найти в [15.12].
■ Журнал восстановления. На первый взгляд не всегда очевидно, как можно обеспе
чить отмену обновления. Ответ на этот вопрос состоит в том, что в системе ведется
журнал на ленте или (чаще всего) на диске, в котором регистрируются подробные
сведения обо всех обновлениях, в частности, значения обновляемых объектов (например кортежей) до и после каждого обновления, иногда называемые образами
данных до и после обновления. Поэтому, если возникает необходимость отменить
некоторые конкретные обновления, система использует соответствующую запись
журнала для восстановления предыдущего значения обновленного объекта.
Примечание. В действительности это описание слишком упрощено. На практике
журнал состоит из двух частей — активной (или оперативной) части и архивной (или
автономной) части. Оперативной называется та часть журнала, которая используется
в процессе текущей эксплуатации системы для регистрации подробных сведений об
обновлениях по мере их выполнения, и обычно хранится на диске. После заполнения
пространства памяти, отведенного для оперативной части журнала, ее содержимое
передается в автономную часть, которая теперь может быть записана на ленту
(поскольку всегда обрабатывается последовательно).
Неразрывность операций. Система должна гарантировать, что выполнение отдель
ных операций (весь процесс их выполнения) должно происходить неразрывно.
Такое требование становится особенно важным в реляционных системах, по
скольку в них операции выполняются на уровне множества и обычно затрагивают
одновременно большое количество кортежей, поэтому нельзя допустить, чтобы
такие операции оканчивались неудачей в ходе выполнения и оставляли базу дан
ных в противоречивом состоянии (например, в таком состоянии, что некоторые
кортежи обновлены, а другие — нет). Иными словами, если в ходе выполнения
подобного оператора возникла ошибка, то база данных должна остаться полно
стью в неизменном состоянии. Кроме того, как описано в главах 9 и 10, это условие
остается в силе, даже если рассматриваемая операция неявно требует выполнения
дополнительных обновлений (например, из-за того, что применяется правило
каскадного удаления или происходит обновление представления, в котором пре
дусмотрено соединение таблиц).
Выполнение программы как последовательности транзакций. Необходимо обратить
особое внимание на то, что операторы COMMIT и ROLLBACK завершают транзак
цию, а не прикладную программу. Как правило, процесс прогона отдельной про
граммы состоит из ряда транзакций, которые следуют одна за другой, как показа
но на рис. 15.2.
Отсутствие вложенных транзакций. Если явно не указано иное, то в данной главе
предполагается, что в прикладной программе оператор BEGIN TRANSACTION мо
жет быть вызван на выполнение, только если в настоящее время в этой программе
не выполняется какая-либо другая транзакция. Иными словами, транзакция не
может содержать в себе вложенную транзакцию. Но необходимо отметить, что в
следующей главе это предположение будет пересмотрено.
Допустимость. По определению база данных должна всегда находиться, по мень
шей мере, в непротиворечивом состоянии. Под понятием непротиворечивости,
согласно главе 9 (а также общепринятому толкованию этого термина), мы подра
зумеваем отсутствие нарушений каких-либо известных ограничений целостности.
Следует также отметить, что непротиворечивость базы данных, рассматриваемая с
точки зрения такого определения данного термина, обеспечивается средствами
самой СУБД. Из этого следует (также по определению), что транзакции всегда пе
реводят базу данных из одного непротиворечивого состояния в другое. Но одной непротиворечивости недостаточно; база данных должна отвечать требованиям до-
пустимости, а не только непротиворечивости! Например, в случае транзакции, по-
казанной на рис. 15.1, требуется, чтобы суммарное количество денег на счетах 123
и 456 в результате транзакции не изменилось. Но было бы неразумно ставить перед
собой задачу по подготовке ограничения целостности, которое соответствовало бы
такому требованию (объясните, почему), и поэтому нельзя рассчитывать на то, что
СУБД сможет следить за соблюдением данного требования. В действительности,
как уже было сказано в главе 9, непротиворечивость не подразумевает правиль-
ность. Поэтому, к сожалению, все, что мы можем сделать (и чего мы вообще мо-
жем добиться с помощью СУБД), это просто принять предположение, что тран-
закции являются правильными, в том смысле, что они достоверно отражают лишь
те операции реального мира, которые были реализованы с их помощью. Точнее,
мы предполагаем, что если т — транзакция, которая переводит базу данных из
состояния D1 в состояние D2 и состояние D1 является правильным, то D2 также
является правильным 2 . Но еще раз отметим, что это желаемое свойство не может
быть обеспечено самой системой (как было указано в главе 9, система может обес-
печить не истинность, а только непротиворечивость).
■ Множественное присваивание. Как было указано в главе 5 (в соответствии с дово-
дами, приведенными в [3.3]), в базе данных необходимо предусмотреть поддержку
множественной формы присваивания, которая позволяет выполнять одновре-
менно любое количество отдельных операций присваивания (т.е. обновлений).
Например, две отдельные операции UPDATE, показанные на рис. 15.1, могут быть
заменены следующим одним оператором (обратите внимание на применяемый в
нем разделитель в виде запятой).
Теперь эта транзакция будет включать только одну операцию обновления, поэтому ее
воздействие на базу данных будет неразрывным по определению и операторы BEGIN
TRANSACTION , COMMIT и ROLLBACK больше не потребуются (по крайней мере, в данном
конкретном случае). Но, как было отмечено в главе 5, современные программные про-
дукты не поддерживают множественное присваивание (или поддерживают эту операцию
не полностью). Поэтому по практическим соображениям до конца данной главы воз-
можность применения множественного присваивания не рассматривается. (Безусловно,
при проведении оригинальной исследовательской работы, посвященной транзакциям,
возможность применения множественного присваивания фактически даже не рассмат-
ривалась. Дополнительная информация на эту тему приведена в разделе 16.10.)

Свойства ACID транзакций
Как и в [15.14], можно подытожить материал этого и предыдущего разделов, сделав
заключение, что транзакции обладают (или должны обладать!) четырьмя важными
свойствами: неразрывностью (atomicity), правильностью 6 (correctness), изолированно-
стью (isolation) и устойчивостью (durability). Этот набор свойств принято называть свой-
ствами ACID (по первым буквам их английских названий).
■ Неразрывность. Транзакции неразрывны (выполняются по принципу “все или ни
чего”).
■ Правильность. Транзакции преобразуют базу данных из одного правильного со
стояния в другое; при этом правильность не обязательно должна обеспечиваться
на всех промежуточных этапах.
■ Изолированность. Транзакции изолированы одна от другой. Таким образом, даже
если будет запущено множество транзакций, работающих параллельно, результаты
любых операций обновления, выполняемых отдельной транзакцией, будут скрыты
от всех остальных транзакций до тех пор, пока эта транзакция не будет зафиксиро
вана. Иначе говоря, для любых отдельных транзакций А и В справедливо следую
щее утверждение: транзакция А сможет получить результаты выполненных тран
закцией в обновлений только после фиксации транзакции в, а транзакция в смо
жет получить результаты выполненных транзакцией А обновлений только после
фиксации транзакции А.
■ Устойчивость. После того как транзакция зафиксирована, выполненные ею об-
новления сохраняются в базе данных на постоянной основе, даже если в дальней-
шем произойдет аварийный останов системы.

Question 3

Transactions: Recovery

Answer 3

ВОССТАНОВЛЕНИЕ ТРАНЗАКЦИИ
Транзакция начинается с выполнения оператора BEGIN TRANSACTION и заканчива-
ется выполнением оператора COMMIT или ROLLBACK . Оператор COMMIT устанавливает
так называемую точку фиксации (которую называют также точкой синхронизации —
syncpoint, особенно в ранее созданных системах). Точка фиксации соответствует (успеш-
ному) окончанию логической единицы работы и, следовательно, точке, в которой база
данных находится (или будет находиться после фиксации) в непротиворечивом состоя-
нии. В противовес этому, после выполнения оператора ROLLBACK база данных вновь
возвращается в состояние, в котором она была в момент начала обработки оператора
BEGIN TRANSACTION , т.е. в предыдущую точку фиксации.
Примечание. Выражение предыдущая точка фиксации является вполне допустимым
даже в случае выполнения в программе первой транзакции, при условии, что первый
оператор BEGIN TRANSACTION по умолчанию устанавливает в программе первоначаль-
ную точку фиксации. Следует также отметить, что в этом контексте термин база данных
фактически означает доступную для транзакции часть базы данных. Другие транзакции
могут выполняться параллельно с данной транзакцией и вносить изменения в иные части
базы данных. Поэтому общая база данных может и не быть в полностью непротиворечи-
вом состоянии в момент фиксации конкретной транзакции. Но, как описано в разде-
ле 15.1, в данной главе не учитывается возможность параллельного выполнения транзак-
ций, поскольку такое упрощение существенно не влияет на рассматриваемый вопрос.
Ниже перечислены случаи установки точки фиксации.
1. Как описано в разделе 15.2, все обновления, совершенные программой с момента ус-
тановки предыдущей точки фиксации, выполнены, т.е. получили статус постоянных
в том смысле, что гарантирована запись их результатов в базу данных. До достиже-
ния точки фиксации все выполненные транзакцией обновления могут рассматри-
ваться только как намеченные в том смысле, что они могут быть отменены (т.е. суще-
ствует возможность их отката). Но гарантируется, что с момента фиксации обновле-
ние уже никогда не будет отменено 3 (это и есть определение понятия фиксации).
2. Утрачена вся информация о позиционировании базы данных и сняты все блоки-
ровки кортежей. Определение понятия позиционирования базы данных в этом кон-
тексте основано на том, что в любой заданный момент выполняющаяся программа
обычно адресуется к конкретным кортежам в базе данных (например, с помощью
определенных курсоров в случае языка SQL, как показано в главе 4). Эта адресуе-
мость в точке фиксации теряется. Понятие блокировка кортежей рассматривается
в следующей главе.
Примечание. В некоторых системах имеется опция, с помощью которой программа
может сохранять адресуемость к некоторым кортежам (а значит, сохранять неко-
торые кортежи заблокированными) от одной транзакции к другой; фактически та-
кая возможность была введена в стандарте SQL в 1999 году. Более подробно речь
об этом пойдет ниже, в разделе 15.8.
Примечание. Здесь п. 2 также действителен, если транзакция завершается оператором
ROLLBACK, а не COMMIT (за исключением замечания о возможности сохранения некото-
рой адресуемости и, следовательно, соответствующей блокировки кортежей). К п. 1 это,
безусловно, не относится.
Из всего сказанного выше следует, что транзакции — это не только логические еди-
ницы работы, но и единицы восстановления. Это означает, что при успешном завершении
транзакции система гарантирует, что выполненные ею обновления будут существовать в
базе данных постоянно, даже если в следующий момент в системе произойдет аварийный
останов. Вполне возможно, что в системе произойдет сбой после успешного выполнения
оператора COMMIT, но перед тем, как обновления будут физически записаны в базу дан-
ных (они все еще могут оставаться в буфере оперативной памяти 4 и, таким образом, мо-
гут быть утеряны в момент сбоя системы). Даже если подобное произойдет, процедура
перезапуска системы все равно должна зарегистрировать эти обновления в базе данных;
чтобы узнать о том, действительно ли эти значения были записаны в базу данных, можно
ознакомиться с соответствующими записями в журнале. (Из этого следует, что физическая
запись в журнал регистрации должна быть внесена перед завершением операции COMMIT.
Это важное правило называется правилом опережающей записи в журнал — write-ahead
log rule.) Процедура перезапуска позволяет восстановить любые успешно завершенные
транзакции, обновления которых не были физически записаны во вторичную память до
возникновения сбоя системы. Следовательно, как и указывалось ранее, транзакция дей-
ствительно является единицей восстановления.
Примечание. В следующей главе будет показано, что транзакции являются также еди-
ницами организации параллельной работы.
На данном этапе необходимо рассмотреть несколько вопросов реализации. Интуи-
тивно должно быть ясно, что практическое осуществление задачи поддержки транзакций
становится проще, если соблюдаются оба из описанных ниже условий.
■ Данные об обновлениях базы данных хранятся в буферах оперативной памяти и не
записываются физически на диск до фиксации транзакции. Таким образом, если
транзакция оканчивается неудачей, то нет необходимости отменять какие-либо
обновления, записанные на диске.
■ Обновления базы данных физически записываются на диск в процессе выполне-
ния оператора COMMIT транзакции. Таким образом, если в дальнейшем произой-
дет аварийный останов системы, то можно быть уверенным в том, что нет необхо-
димости повторно выполнять какие-либо операции обновления на диске.
Но на практике (как правило) ни одно из этих требований не соблюдается. Во-первых,
буфера могут просто оказаться недостаточно большими, а это означает, что потребуется
записывать на диск обновления транзакции А еще до того, как произойдет фиксация
транзакции А с помощью оператора COMMIT . Такая необходимость может, например,
возникнуть в связи с тем, что потребуется освободить место для обновлений транзакции
в (в подобных ситуациях принято говорить, что транзакция в вытесняет транзакцию А из
буферного пространства). Во-вторых, физическая (или принудительная) запись обновле-
ний на диск во время выполнения оператора COMMIT может оказаться очень неэффек-
тивной; например, если все 100 последовательных транзакций обновляют один и тот же
объект, то принудительная запись означает, что должно быть выполнено 100 физических
операций записи, когда вполне достаточно одной. По этим причинам в применяемых на
практике диспетчерах транзакций обычно предусмотрено так называемое правило кон-
фискации и отказа от принудительной записи (steal/no-force), а это, вполне очевидно,
весьма значительно усложняет реализацию. Дополнительные сведения об этом выходят
за рамки данной книги.
Итак, как уже было сказано, правило опережающей записи в журнал означает, что об-
работка оператора COMMIT может закончиться только после того, как будет выполнена
физическая запись в журнал. Безусловно, это утверждение остается в силе, но теперь его
можно расширить и уточнить, как описано ниже.
■ Запись журнала, касающаяся конкретного обновления базы данных, должна быть
физически внесена в журнал еще до того, как само обновление будет физически
внесено в базу данных.
■ Все другие записи журнала, касающиеся данной конкретной транзакции, должны
быть физически внесены в журнал еще до того, как в журнал будет физически вне
сена запись с оператором COMMIT, которая относится к указанной транзакции.
■ Обработка оператора COMMIT для данной транзакции не должна завершаться до
тех пор, пока в журнал не будет физически внесена запись с оператором COMMIT,
который относится к этой транзакции 5 .

ВОССТАНОВЛЕНИЕ СИСТЕМЫ
Система должна быть готова к восстановлению не только после локальных отказов,
подобных возникновению условия переполнения при выполнении операции в пределах
определенной транзакции, но и после глобальных нарушений, подобных отключению
питания. Локальное нарушение по определению влияет только на ту транзакцию, в кото-
рой оно, собственно говоря, и произошло. Подобные нарушения уже обсуждались выше,
в разделах 15.2 и 15.3. Глобальное нарушение воздействует сразу на все транзакции, вы-
полнявшиеся в момент его возникновения, и поэтому приводит к более значительным
для системы последствиям. В этом и следующем разделе кратко описано, какие действия
необходимо выполнить в процессе восстановления после глобального отказа системы.
Такие отказы подразделяются на две основные категории, которые описаны ниже.
■ Отказы системы (например, сбои в питании) воздействуют на все выполняющиеся
в данный момент транзакции, но не приводят к физическому повреждению базы
данных. Отказ системы иногда также называют мягким аварийным остановом.
■ Отказы носителей (например, поломка головки дискового накопителя), которые
могут представлять угрозу для физического состояния всей базы данных или ка-
кой-либо ее части, способны воздействовать, по крайней мере, на те транзакции,
которые используют поврежденную часть базы данных. Отказ носителя иногда на-
зывают также жестким аварийным остановом.
В этом разделе будут рассмотрены отказы системы, а в разделе 15.5 — отказы носителей.
Критическим моментом в отказе системы является потеря содержимого основной
(оперативной) памяти (в частности, буферов базы данных). Поскольку точное состояние
любой выполнявшейся в момент отказа системы транзакции остается неизвестным, та-
кая транзакция не может быть успешно завершена. Поэтому при перезапуске системы
любая такая транзакция будет отменена (т.е. будет выполнен ее откат).
Более того, при перезапуске системы, возможно, потребуется (как указывалось в раз-
деле 15.3) повторно выполнить некоторые транзакции, которые были успешно завершены
до аварийного останова, но выполненные ими обновления еще не были перенесены из
буферов оперативной памяти в физическую базу данных во вторичной памяти.
Возникает очевидный вопрос: как система определяет в процессе перезапуска, какую
транзакцию следует отменить, а какую выполнить повторно? Ответ заключается в том,
что система автоматически создает контрольные точки с некоторым наперед заданным
интервалом (обычно, когда в журнале накапливается определенное число записей). Для
создания контрольной точки требуется, во-первых, выполнить принудительное сохране-
ние содержимого буферов оперативной памяти в физической базе данных, и, во-вторых,
осуществить принудительное сохранение специальной записи контрольной точки в жур-
нале на физическом носителе. Запись контрольной точки содержит список всех транзак-
ций, выполняемых в тот момент, когда создавалась контрольная точка. Для того чтобы
ознакомиться с тем, как используется эта информация, рассмотрим рис. 15.3, который
можно описать словами следующим образом (ось времени на этом рисунке направлена
слева направо).
■ Отказ системы произошел в момент времени tf.
■ Ближайшая к моменту tf контрольная точка была создана в момент времени tc.
■ Транзакция типа Т1 успешно завершена до момента времени tc.
■ Транзакция типа Т2 начата до момента tc и успешно завершена после момента
времени tc, но до момента времени tf.
■ Транзакция типа ТЗ также начата до момента времени tc, но не завершена к мо
менту времени tf.
■ Транзакция типа Т4 начата после момента времени tc и успешно завершена до
момента времени tf.
■ Наконец, транзакция типа Т5 также начата после момента tc, но не завершена к
моменту времени tf.
Очевидно, что при перезапуске системы транзакции типов ТЗ и Т5 должны быть от-
менены, а транзакции типа Т2 и Т4 — выполнены повторно. Отметим, что транзакции
типа Т1 вообще не участвуют в процессе перезапуска, поскольку выполненные ими об-
новления были принудительно внесены в физическую базу данных к моменту времени tc
как часть процедуры создания этой контрольной точки. Обратите внимание также на то,
что транзакции, завершившиеся неудачно (т.е. для них был выполнен откат) до момента
времени tf, также не будут учитываться в процессе перезапуска (объясните, почему).
Следовательно, во время перезапуска система прежде всего выполняет описанную
ниже процедуру для выявления всех транзакций типовТ2-Т5.
1. Создаются два списка транзакций; назовем их UNDO (Отменить) и REDO (Выпол
нить повторно).
2. В список UNDO заносятся все транзакции, упомянутые в последней из существую
щих записей контрольной точки, a cписок REDO пока остается пустым.
3. В журнале регистрации поиск начинается с записи контрольной точки и происхо
дит в прямом направлении.
4. Если в журнале регистрации обнаружена запись BEGIN TRANSACTION с указани
ем о начале выполнения некоторой транзакции т, то эта транзакция добавляется в
СПИСОК UNDO.
5. Если в журнале регистрации обнаружена запись COMMIT, свидетельствующая об
окончании выполнения некоторой транзакции т, эта транзакция переносится из
СПИСКа UNDO В СПИСОК REDO.
6. По достижении конца файла журнала регистрации списки UNDO и REDO анализи
руются для выявления, соответственно, транзакций типов ТЗ и Т5, а также типов
Т2 и Т4.
После этого система просматривает журнал регистрации в обратном направлении,
выполняя откат транзакций из списка UNDO, а затем вновь просматривает журнал в пря-
мом направлении, повторно выполняя транзакции из cnиcкa REDO.
Примечание. Восстановление согласованного состояния базы данных посредством
отмены выполненных операций иногда называется обратным восстановлением. Анало-
гичным образом, восстановление согласованного состояния базы данных за счет повтор-
ного выполнения уже выполненных действий называется прямым восстановлением.
Необходимо учитывать, что при прямом восстановлении повторное внесение обновлений происходит в том порядке, в котором они были выполнены первоначально, а при обрат-
ном восстановлении отмена обновлений происходит в обратном порядке.
Система будет готова к дальнейшей работе тогда (и только тогда), когда такая восста-
новительная работа будет завершена.

Question 4

Transactions: Concurrency

Answer 4

Термин параллельность обозначает такое свойство СУБД, которое, как
правило, позволяет одновременно обращаться с помощью многих транзакций к
одной и той же базе данных. Очевидно, что в системе, обладающей таким
свойством, требуется определенный механизм управления, который позволяет
добиться того, чтобы параллельно выполняемые транзакции не нарушали
работу друг друга. (Примеры нарушений в работе различных типов, которые
могут возникать в отсутствие подобных средств управления, приведены в
разделе 16.2.) В настоящей главе дано подробное описание данной темы. Она
имеет указанную ниже структуру.
■ Как уже было отмечено, в разделе 16.2 рассматриваются некоторые проблемы, ко-
торые могут возникнуть, если не предусмотрены подходящие средства управления
параллельным доступом.
■ В разделе 16.3 представлен широко применяемый механизм устранения подобных
проблем, называемый блокировкой. (Блокировка — не единственный возможный
механизм управления параллельным доступом, но он находит гораздо более широ
кое применение на практике по сравнению с другими. Некоторые другие средства
описаны в аннотациях к литературе в конце данной главы.)
■ Затем в разделе 16.4 показано, как может использоваться блокировка для решения
проблем, описанных в разделе 16.2.
■ К сожалению, сама блокировка может стать причиной проблем, и одной из наи
более известных является взаимоблокировка. Описанию этой темы посвящен
раздел 16.5.
■ В разделе 16.6 рассматривается понятие упорядочиваемости, которое является об
щепризнанным формальным критерием правильной организации работы в этой
области.
■ В разделе 16.7 описано, как связана тема организации параллельной работы с те
мой предыдущей главы — восстановлением.
■ После этого в разделах 16.8 и 16.9 представлены два значительных усовершенство
вания основных принципов блокировки — применение уровней изоляции и наме
ченных блокировок.
■ В разделе 16.10 приведены довольно неожиданные и несколько скептические за
мечания на тему так называемых свойств ACID транзакций.
■ В разделе 16.11 описаны соответствующие средства языка SQL.
■ Наконец, в разделе 16.12 приведено резюме.
В завершение этого вступительного раздела приведем ряд общих замечаний. Во-первых,
способ организации параллельного выполнения, как и восстановления, в значительной
степени зависит от того, относится ли соответствующая система к типу реляционных
систем или к другому типу (но важно отметить, что основная часть ранних теоретических
работ в этой области, как и в области восстановления, была выполнена именно в реляци-
онном контексте, поскольку он позволяет достичь “большей определенности” [16.6]). Во-
вторых, параллельность, как и восстановление, — это очень обширная тема, и в этой главе
мы можем рассчитывать лишь на то, что в ней удастся изложить наиболее важные и
фундаментальные идеи. Некоторые более сложные аспекты этой темы кратко рассматри-
ваются в некоторых аннотациях к списку литературы в конце данной главы.

ТРИ ПРОБЛЕМЫ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНОЙ РАБОТЫ
Вначале рассмотрим некоторые из проблем, с которыми должен помочь справиться лю-
бой механизм управления параллельным выполнением. По сути, возникают три основные
ситуации, в которых могут происходить нарушения работы. Это такие ситуации, что тран-
закция, будучи правильной сама по себе в том смысле, который определен в главе 15, мо-
жет, тем не менее, выработать неправильный ответ, если в ее работу каким-то образом
вмешиваются другие транзакции. При этом необходимо учитывать важное замечание,
что и сами транзакции, нарушающие ее работу, также рассматриваются как правильные
(в соответствии с обычно принятым допущением), поэтому причиной получения общего
неправильного результата становится неконтролируемое чередование операций двух
транзакций, которые сами по себе являются правильными. Ниже перечислены три воз-
никающие при этом проблемы.
■ Проблема потерянного обновления.
■ Проблема зависимости от незафиксированных результатов.
■ Проблема анализа несовместимости.
Рассмотрим каждую из этих проблем по очереди.
Проблема потерянного обновления
Рассмотрим ситуацию, показанную на рис. 16.1. События, представленные на этом
рисунке, развиваются следующим образом: транзакция А выполняет выборку некоторого
кортежа t в момент времени tl, транзакция в выполняет выборку того же кортежа t в
момент времени t2, транзакция А обновляет кортеж в момент времени t3 (с учетом тех
значений, которые он имел во время tl), а транзакция в обновляет тот же кортеж в мо-
мент времени t4 (с учетом тех значений, которые он имел во время t2, которые остава-
лись такими же, как и во время tl). В момент времени t4 происходит потеря обновле-
ния, внесенного транзакцией А, поскольку транзакция в перезаписывает его, даже не
проверяя.
Проблема зависимости от незафиксированных результатов возникает, если одной
транзакции разрешено выполнять выборку (или, что еще хуже, обновление) кортежа,
который был обновлен другой транзакцией, но это обновление еще не было зафиксиро-
вано другой транзакцией. А поскольку это обновление еще не зафиксировано, то всегда
существует вероятность, что оно так и не будет зафиксировано, а вместо этого произойдет откат, и в этом случае первая транзакция будет работать с данными, которых больше не
существует (и которые в определенном смысле и не существовали).
В первом примере (рис. 16.2) транзакция А получает доступ к незафиксированному
обновлению (называемому также незафиксированным изменением) в момент времени t2.
Затем в момент времени t3 происходит отмена этого обновления. Таким образом, тран-
закция А действует на основании ложной предпосылки, что кортеж t имеет значение,
которое было ею получено во время t2, тогда как этот кортеж фактически имеет то значе-
ние, которое он имел к моменту времени tl. В связи с этим транзакция А вполне может
выработать неправильные результаты. Кстати, следует отметить, что откат транзакции в
вполне может произойти не из-за ошибки в в; например, он может произойти из-за ава-
рийного останова системы. (А если транзакция А к этому времени уже будет завершена,
то такой останов не повлечет за собой выполнение отката также и для А.)
Во втором примере (рис. 16.3) события развиваются по еще более худшему сценарию.
Транзакция А становится не только зависимой от незафиксированного изменения в
момент времени t2, но и фактически теряет свое обновление во время t3, поскольку
откат в момент времени t3 вызывает восстановление кортежа t до того значения, ко-
торое он имел к моменту времени tl, т.е. это еще один вариант проблемы потерянного
обновления.

Проблема анализа несовместимости
Рассмотрим рис. 16.4, где показаны две транзакции, А и в, оперирующие с кортежами
некоторого счета (ACCount — АСС). Транзакция А подсчитывает остатки на счетах, а
транзакция В переводит сумму 10 со счета 3 на счет 1. Очевидно, что результат, вырабо-
танный транзакцией А, — 110, является неправильным; если бы в ходе своего дальней-
шего выполнения транзакция А снова записала этот результат в базу данных, то фактически
оставила бы базу данных в противоречивом состоянии 1 . По сути, транзакция А обнару-
жила несовместимое состояние базы данных и поэтому выполнила анализ несовмести-
мости. Обратите внимание на различие между этим примером и предыдущим: в данном
случае не возникает проблема зависимости транзакции А от незафиксированного изме-
нения, поскольку в зафиксировала все свои обновления еще до того, как А прочитала
значение АСС 3.
Примечание. Кстати, следует отметить, что вместо термина анализ несовместимости
следовало бы применять анализ неправильности. Но мы по традиции придерживаемся
прежнего термина.

Более подробное описание рассматриваемых проблем ‘
Примечание. Этот подраздел при первом чтении можно пропустить.
В данном подразделе описанные выше проблемы рассматриваются немного более
подробно. Очевидно, что с точки зрения организации параллельной работы наибольший
интерес представляют такие операции, как выборка информации из базы данных и об-
новление базы данных; иными словами, любая транзакция может рассматриваться как
состоящая из последовательности только указанных операций (безусловно, если не
учитывать такие необходимые операции, как BEGIN TRANSACTION И COMMIT ИЛИ
ROLLBACK ). В дальнейшем эти операции будут сокращенно обозначаться, соответствен-
но, как R (чтение) и w (запись). В таком случае становится ясно, что если А и в — парал-
лельно выполняемые транзакции, то проблемы могут возникнуть, если в ходе выполне-
ния А и B требуется прочитать или записать один и тот же объект базы данных, например,
кортеж t. При этом возникают четыре возможные конфликтные ситуации, которые опи-
саны ниже.
■ Конфликт типа RR. И в транзакции А, и в транзакции в необходимо выполнить
чтение кортежа t. Операции чтения не могут нарушать работу друг друга, поэтому
в данной ситуации проблема не возникает.
■ Конфликт типа RW. В транзакции А выполняется чтение кортежа t, а затем в тран
закции в возникает необходимость записать кортеж t. Если транзакции в будет
разрешено выполнить эту запись, то (как показано на рис. 16.4) может возникнуть
проблема анализа несовместимости, поэтому можно утверждать, что проблема
анализа несовместимости вызвана конфликтами типа RW.
Примечание. Если транзакция В выполняет свою операцию записи, а затем транзак-
ция А снова считывает значение t, то последняя обнаруживает значение, отличное от того, что было прочитано раньше; такое стечение обстоятельств принято обо-
значать (не совсем точно) как неповторяемое чтение, поэтому проблема неповто-
ряемого чтения также вызывается конфликтом типа RW.
■ Конфликт типа WR. В транзакции А выполняется запись кортежа t, а затем в тран-
закции в возникает необходимость прочитать t. Если транзакции в будет разре-
шено выполнить эту операцию чтения, то (как показано на рис. 16.2, с учетом
того, что транзакции А И В поменялись ролями) может возникнуть проблема зави-
симости от незафиксированных обновлений; таким образом, можно утверждать,
что проблема зависимости от незафиксированных обновлений вызывается кон-
фликтами типа WR.
Примечание. Чтение в транзакции в, если оно будет разрешено, называется гряз-
ным чтением (dirty read).
■ Конфликт типа WW. В транзакции А выполняется запись кортежа t, а затем необ-
ходимость выполнить запись кортежа t возникает в транзакции в. Если транзак-
ции В будет разрешено выполнить эту запись, то (как показано на рис. 16.1, а также
на рис. 16.3) может возникнуть проблема потерянного обновления; таким обра-
зом, можно утверждать, что проблема потерянного обновления вызвана конфлик-
тами типа WW.

Question 5

Transactions: Locking

Answer 5

БЛОКИРОВКА
Как было указано в разделе 16.1, все проблемы, описанные в разделе 16.2, могут быть
устранены с помощью механизма управления параллельным выполнением, называемого
блокировкой. В его основе лежит простая идея — если для некоторой транзакции А требу-
ется гарантия, чтобы определенный объект, в котором она заинтересована (как правило,
кортеж базы данных), не изменился каким-то образом без ее ведома (как описано выше),
она приобретает блокировку на этот объект (как принято называть соответствующую опе-
рацию). Неформально выражаясь, следствием приобретения блокировки является то, что
к рассматриваемому объекту, условно говоря, “блокируются доступ других транзакций”,
и поэтому, в частности, предотвращается возможность внесения ими изменений. Благо-
даря этому транзакция А может продолжать свои операции обработки в полной уверен-
ности в том, что рассматриваемый объект останется в определенном состоянии до тех
пор, пока он требуется для этой транзакции.
Ниже приведено более подробное описание того, по какому принципу работает бло-
кировка.
1. Прежде всего, предположим, что в системе поддерживаются блокировки двух ти
пов: исключительные блокировки (блокировки X — exclusive) и разделяемые блоки
ровки (блокировки S — shared), которые определены, как указано в следующих
двух абзацах.
Примечание. Блокировки X и S иногда именуются, соответственно, блокировками
записи и блокировками чтения. Если не указано иное, то в данной главе предпола-
гается, что блокировки X и S являются единственными доступными типами бло-
кировок; описание других типов блокировок приведено в разделе 16.9. Кроме того,
если не указано иное, предполагается, что единственными типами объектов базы
данных, которые могут быть заблокированы, являются кортежи; описание других
возможностей также приведено в разделе 16.9.
2. Если транзакция А владеет исключительной блокировкой (X), то запрос от неко
торой другой транзакции в на получение блокировки кортежа t любого типа не
может быть немедленно удовлетворен.
3. Если транзакция А владеет разделяемой блокировкой (S) кортежа t, то выполня
ются следующие условия:
■ запрос некоторой другой транзакции в на получение блокировки X кортежа t
не может быть немедленно удовлетворен;
■ запрос некоторой другой транзакции в на получение блокировки S кортежа t
может и должен быть немедленно удовлетворен (это означает, что с этого вре
мени транзакция в также будет владеть блокировкой S кортежа).
Эти правила можно успешно подытожить с помощью матрицы совместимости типов
блокировок (рис. 16.5). Такая матрица интерпретируется следующим образом: рассмот-
рим некоторый кортеж t и предположим, что транзакция А в настоящее время владеет
блокировкой на t, которая обозначена одной из записей в заголовках столбцов (дефис обозначает, что блокировка отсутствует), а также предположим, что некоторая другая
транзакция в выдает запрос на получение блокировки t, которая обозначена одной из
записей в заголовках строк (для полноты здесь также предусмотрен случай “отсутствия
блокировки”). В этой матрице “N” указывает на конфликт (запрос транзакции в не мо-
жет быть немедленно удовлетворен), a “Y” указывает на совместимость (запрос транзак-
ции в может и должен быть немедленно удовлетворен). Очевидно, что эта матрица явля-
ется симметричной.
Теперь перейдем к описанию протокола доступа к данным, или протокола
блокировки,
который позволяет использовать только что описанные блокировки X и S для обеспече-
ния того, чтобы никогда не возникали проблемы, описанные в разделе 16.2.
1. Транзакция, в которой требуется выполнить выборку кортежа, должна вначале
приобрести блокировку S на этот кортеж.
2. Транзакция, в которой требуется выполнить обновление кортежа, должна вначале
приобрести X блокировку на этот кортеж. В ином случае, если она уже владеет
блокировкой S на этом кортеже, как происходит в ситуации, когда выполняется
последовательность операций выборки и обновления (RETRIEVE и UPDATE), то
эта транзакция должна, как принято называть такое действие, расширить, или по
высить уровень блокировки S до уровня X.
Примечание. В этот момент необходимо прервать изложение, чтобы пояснить, что
запросы на получение блокировок обычно бывают неявными — операция выборки
кортежа неявно запрашивает блокировку S на соответствующий кортеж, а операция
обновления кортежа неявно запрашивает блокировку X (или неявно запрашивает
расширение существующей блокировки S до уровня X) на соответствующий кор-
теж. Кроме того, в этом описании, как обычно, под операцией обновления подра-
зумеваются любые операции вставки (INSERT) и удаления (DELETE), а также
обновления (UPDATE) как таковые, но рассматриваемые правила требуют опреде-
ленного уточнения с учетом особенностей операторов INSERT и DELETE. В дан-
ном разделе дополнительные сведения по этому вопросу не приведены.
3. Если запрос на блокировку от транзакции в не может быть немедленно удовлетво
рен из-за того, что он конфликтует с блокировкой, которой уже владеет транзак
ция А, то в переходит в состояние ожидания. Транзакция в ожидает до тех пор, по
ка не появится возможность удовлетворить ее запрос на блокировку, а это может
произойти не раньше, чем транзакцияА освободит блокировку.
Примечание. Выше было применено выражение “не раньше, чем”, поскольку после
освобождения блокировки транзакцией А может быть удовлетворен другой запрос на блокировку соответствующего кортежа, но это будет не запрос транзакции В,
поскольку освобождения блокировки могут также ожидать другие транзакции.
Безусловно, система должна обеспечить, чтобы транзакция в не ожидала до беско-
нечности (такая ситуация называется активным тупиком — livelock, или истощением
ресурсов — starvation). Один из простых предотвращения такой ситуации состоит в том,
чтобы запросы на блокировку обслуживались в порядке простой очереди (“первым
поступил—первым обслуживается”). 4. Блокировки X освобождаются по завершении
транзакции (COMMIT или ROLLBACK ). Блокировки S также обычно освобождаются в
это время (по крайней мере, такого предположения мы будем придерживаться до
раздела 16.8).
Описанный выше протокол называется строгим протоколом двухфазной блокировки.
Он рассматривается более подробно в разделе 16.6. В частности, в этом разделе указано,
почему он получил такое название.

ДАЛЬНЕЙШЕЕ ОПИСАНИЕ ТРЕХ ПРОБЛЕМ ОРГАНИЗАЦИИ
ПАРАЛЛЕЛЬНОЙ РАБОТЫ
Теперь мы имеем возможность рассмотреть, каким образом с помощью строгого про-
токола двухфазной блокировки решаются три проблемы, описанные в разделе 16.2.
В этом разделе они снова рассматриваются по очереди.
Проблема потерянного обновления
Рис. 16.6 представляет собой модифицированную версию рис. 16.1. На нем показано,
что произойдет при выполнении чередующихся операций данного рисунка в условиях
применения строгого протокола двухфазной блокировки. Выполнение операции UPDATE
транзакцией А в момент времени t3 не допускается, поскольку эта операция представляет
собой неявный запрос на блокировку X кортежа t, а такой запрос конфликтует с бло-
кировкой S, которой уже владеет транзакция в, поэтому А переходит в состояние ожидания.
По аналогичным причинам транзакция в переходит в состояние ожидания в момент вре-
мени t4. При таких обстоятельствах обе транзакции не могут выполнять свои действия,
поэтому проблема потери какого-либо обновления не возникает. Итак, проблема поте-
рянного обновления свелась к другой проблеме! Но, по крайней мере, решена первона-
чальная проблема. Новая проблема называется взаимоблокировкой, и она рассматривается
в разделе 16.5.
Проблема зависимости от незафиксированного обновления
На рис. 16.7 и 16.8, соответственно, приведены модифицированные версии рис. 16.2 и
16.3. На них показано, что произойдет при выполнении чередующихся операций, показан-
ных на этих рисунках, в условиях применения строгого протокола двухфазной блокировки.
В обоих случаях выполнение операций транзакцией А в момент времени t2 (RETRIEVE
на рис. 16.7 и UPDATE на рис. 16.8) не допускается, поскольку они представляют собой
неявный запрос на блокировку кортежа t, а любой такой запрос конфликтует с блоки-
ровкой X, которой уже владеет транзакция в, поэтому А переходит в состояние ожидания.
Эта транзакция остается в состоянии ожидания до тех пор, пока в не достигнет своего за-
вершения (в результате выполнения либо оператора COMMIT, либо оператора ROLLBACK).
После этого блокировка транзакции в освобождается и транзакция А получает возмож-
ность продолжить работу. В этот момент транзакция А обнаруживает уже зафиксирован-
ное значение (либо значение, предшествовавшее выполнению транзакции в, если про-
изошел ее откат, либо значение, полученное после выполнения транзакции в, в ином
случае). Так или иначе, успешное выполнение транзакции А больше не зависит от неза-
фиксированного обновления, поэтому первоначальная проблема решена.

Проблема анализа несовместимости
На рис. 16.9 приведена модифицированная версия рис. 16.4. На этом рисунке пока-
зано, что произойдет при чередующемся выполнении операций данного рисунка в усло-
виях применения строгого протокола двухфазной блокировки. Выполнение операции
UPDATE транзакцией в в момент времени t6 не допускается, поскольку она представляет
собой неявный запрос на блокировку X кортежа АСС 1, а такой запрос конфликтует с
блокировкой S, которой уже владеет транзакция А, поэтому транзакция в переходит в
состояние ожидания. Аналогичным образом, выполнение операции RETRIEVE транзак-
цией А в момент времени t7 также не допускается, поскольку она представляет собой
неявный запрос на блокировку S кортежа АСС 3, а такой запрос конфликтует с блоки-
ровкой X, которой уже владеет транзакция в, поэтому транзакция А также переходит в
состояние ожидания. Поэтому первоначальная проблема (в данном случае проблема ана-
лиза несовместимости) снова решена, но это привело к возникновению взаимоблоки-
ровки. Еще раз отметим, что взаимоблокировка рассматривается в разделе 16.5.

ВЗАИМОБЛОКИРОВКА
Выше было описано, как может использоваться блокировка (а точнее, строгий прото-
кол двухфазной блокировки) для решения трех основных проблем управления парал-
лельным выполнением. Но, к сожалению, было также показано, что блокировка может
сама стать причиной возникновения проблем, из которых основной является проблема
взаимоблокировки. В предыдущем разделе были приведены два примера взаимоблоки-
ровки. На рис. 16.10 показан немного более общий вариант этой проблемы; на данном
рисунке через rl и г2 обозначены любые блокируемые ресурсы, а не только кортежи
базы данных (см. раздел 16.9), а с помощью операторов “LOCK . . . EXCLUSIVE” обо-
значаются любые операторы, для выполнения которых требуется выдача запросов на
блокировки X, явных или неявных.
Поэтому в общем взаимоблокировка представляет собой такую ситуацию, в которой
две или несколько транзакций одновременно находятся в состоянии ожидания, причем
каждая из них ожидает, пока одна из остальных транзакций не освободит блокировку, чтобы получить возможность продолжить свою работу 2 . На рис. 16.10 показана взаимо-
блокировка, в которой участвуют две транзакции, но возможны также такие ситуации (по
крайней мере, в принципе), когда во взаимоблокировке участвуют три, четыре или боль-
шее количество транзакций. Однако эксперименты, проведенные в системе System R,
показывают, что на практике взаимоблокировки, в которых участвуют больше двух тран-
закций, почти никогда не возникают [16.9].
Если произошла взаимоблокировка, желательно, чтобы система обнаружила ее и ра-
зорвала. Для обнаружения взаимоблокировки необходимо определить наличие цикла в
графе ожидания (Wait-For Graph). Так называется граф, который, неформально выража-
ясь, показывает “кто кого ожидает” (см. упр. 16.4). Чтобы разорвать взаимоблокировку,
необходимо выбрать одну из транзакций, участвующих во взаимоблокировке (т.е. одну из
транзакций, которые входят в состав цикла в графе ожидания), в качестве “жертвы” и выполнить ее откат, что позволяет освободить ее блокировки и дать возможность другим
транзакциям продолжить свою работу.
Примечание. Фактически на практике не все системы обнаруживают взаимоблоки-
ровки как таковые; в некоторых системах используется лишь механизм тайм-аутов и
просто предполагается, что если некоторая транзакция не выполняет никакой работы в
течение некоторого заранее установленного периода времени, то она находится в состоя-
нии взаимоблокировки.
Кстати, следует отметить, что неудачное завершение работы транзакции, выбранной в
качестве жертвы, и последующий ее откат происходят не по вине самой этой транзакции.
В некоторых системах осуществляется автоматический перезапуск такой транзакции с са-
мого начала на основании предположения о том, что условия, которыми прежде было вы-
звано возникновение взаимоблокировки, вероятно, больше не повторятся. В других систе-
мах просто предусмотрена передача в ответ приложению кода исключения “deadlock
victim” (жертва взаимоблокировки); выбор способа дальнейших действий для правиль-
ного выхода из этой ситуации предоставляется самому приложению. Разумеется, что с
точки зрения прикладного программиста первый из этих двух подходов является более
предпочтительным. А если даже сам программист иногда захочет принять участие в уст-
ранении указанной проблемы, он имеет для этого все возможности, но по очевидным
причинам всегда желательно скрывать ее существование от конечного пользоштеля.

Предотвращение взаимоблокировок
Некоторые подходы к устранению взаимоблокировок основаны на том, что существует
возможность модифицировать протокол блокировки различными способами, с тем
чтобы полностью избежать взаимоблокировок, а не ожидать их возникновения, после
чего их устранять (как это делается в большинстве систем). Один из подобных подходов
кратко рассматривается в данном разделе. Этот подход реализован в двух версиях, назы-
ваемых “ожидание-отмена” и “отмена-ожидание”, и был впервые предложен для ис-
пользования в распределенных системах [16.19], но может также применяться в центра-
лизованных системах. Краткое описание рассматриваемого подхода к предотвращению
взаимоблокировок приведено ниже.
■ Каждая транзакция обозначается отметкой времени ее начала (которая должна
быть уникальной).
■ Если транзакция А запрашивает блокировку на кортеже, который уже заблокиро
ван транзакцией в, то выполняются описанные ниже действия в зависимости от
применяемого варианта.
■ “Ожидание-отмена” (Wait-Die). Если выполнение транзакции А началось рань
ше, чем в, А переходит в состояние ожидания; в противном случае происходит ее
отмена. Это означает, что осуществляется откат и перезапуск транзакции А.
■ “Отмена—ожидание” (Wound-Wait). Если выполнение транзакции А началось
позже, чем в, она переходит в состояние ожидания; в противном случае, она
отменяет В. Это означает, что происходит откат и перезапуск транзакции В.
■ Если транзакция должна быть перезапущена, ей после запуска присваивается ее
первоначальная отметка времени.
Следует отметить, что первый компонент названия используемой версии (ожидание
или отмена) в любом случае указывает, что произойдет, если выполнение транзакции А
началось раньше, чем В. Вполне очевидно, что в версии “ожидание-отмена” множество
всех ожидающих транзакций состоит из транзакций, начавшихся раньше и ожидающих
завершения работы тех транзакций, которые были начаты позже, а в версии “отмена-
ожидание” множество всех ожидающих транзакций состоит из транзакций, начавшихся
позже и ожидающих завершения работы тех транзакций, которые были начаты раньше.
Вполне очевидно, что при использовании любой из этих версий взаимоблокировка не
может вообще возникнуть. Кроме того, можно легко убедиться в том, что в конечном
итоге гарантировано успешное завершение работы каждой транзакции. Это означает, что
возникновение активного тупика невозможно (ни одна из транзакций не должна ожидать
до бесконечности), к тому же ни одна транзакция не должна перезапускаться снова и
снова бесконечное количество раз. Основным недостатком этого подхода (при использо-
вании любой из версий) является то, что в нем приходится выполнять слишком много
откатов.

УПОРЯДОЧИВАЕМОСТЬ
Выше в данной главе была заложена основа для изучения крайне важного понятия
упорядочиваемости, к чему мы теперь приступаем. Упорядочиваемость — это общеприня-
тый критерий правильной организации чередующегося выполнения множества транзак-
ций; иными словами, такая организация выполнения считается правильной тогда и
только тогда, когда она является упорядочиваемой 3 . Любая конкретная процедура орга-
низации выполнения заданного множества транзакций является упорядочиваемой (а сле-
довательно, правильной) тогда и только тогда, когда она эквивалентна некоторой проце-
дуре последовательного выполнения тех же транзакций (т.е. гарантирует достижение таких же результатов). Пояснения к некоторым терминам, которые использовались в данном
определении, приведены ниже.
■ Последовательным выполнением транзакций называется такая организация их вы
полнения, при которой транзакции выполняются одна за другой в некоторой по
следовательности.
■ Под гарантированным достижением таких же результатов подразумевается то,
что рассматриваемый вариант чередующегося выполнения транзакций и вариант
их последовательного выполнения всегда вырабатывают одни и те же результаты
независимо от начального состояния базы данных.
Ниже дано дополнительное обоснование применяемого определения упорядочивае-
мого множества транзакций.
1. Предполагается, что отдельные транзакции являются правильными; это означает,
что они по определению переводят базу данных из одного правильного состояния
в другое правильное состояние, как описано в главе 15.
2. Таким образом, любая последовательность транзакций, на основании которой
может быть организовано выполнение транзакций одна за другой, также является
правильной (поскольку предполагается, что если отдельные транзакции не зависят
друг от друга, то может быть выбрана любая последовательность их выполнения).
3. Поэтому имеет смысл ввести определение правильной организации чередующего
ся выполнения операций отдельных транзакций, причем только такой организа
ции выполнения, которая эквивалентна некоторой последовательной организации
выполнения отдельных транзакций (т.е. организация выполнения может быть
правильной тогда и только тогда, когда она является упорядочиваемой). В этой
формулировке заслуживает особого внимания выражение “тогда и только тогда”!
Дело в том, что некоторый вариант организации чередующегося выполнения мо
жет быть неупорядочиваемым и при этом все равно приводить к результату, кото
рый окажется правильным в некотором определенном начальном состоянии базы
данных (см. упр. 16.3), но этого недостаточно, поскольку правильная организация
чередующегося выполнения должна гарантироваться (т.е. быть независимой от
конкретных состояний базы данных), а не возникать лишь по стечению обстоя
тельств.
Снова обратившись к примерам, приведенным в разделе 16.2 (рис. 16.1-16.4), можно
убедиться, что в каждом из рассматриваемых случаев проблема состояла именно в том,
что применяемая процедура организации чередующегося выполнения транзакций не
была упорядочиваемой. Это означает, что в этих вариантах выполнение “вначале А, затем
В” или “вначале в, затем А” не приводит к получению одинаковых результатов. Кроме
того, анализ материала, изложенного в разделе 16.4, под этим новым углом зрения по-
казывает, что действие строгого протокола двухфазной блокировки сводится именно к
тому, что он в каждом случае обеспечивает соблюдение принципов упорядочиваемости.
На рис. 16.7 и 16.8 принятая организация чередующегося выполнения транзакций экви-
валентна варианту “вначале в, затем А”. На рис. 16.6 и 16.9 показано, что происходит взаи-
моблокировка, а это означает, что для одной из двух транзакций должен быть выполнен
откат (и, предположительно, повторный запуск на выполнение в какой-то последующий момент времени). Если будет выполнен откат транзакции А, то данный вариант органи-
зации чередующегося выполнения снова становится эквивалентным варианту “вначале в,
затем А”.
Терминология. Если дано множество транзакций, то любая процедура организации
выполнения этих транзакций, с их чередованием или без чередования, называется графи-
ком. Если транзакции выполняются одна за другой, без чередования, то применяемый
при этом график называется последовательным. График, не являющийся последователь-
ным, называется чередующимся (или просто непоследовательным). Два графика называ-
ются эквивалентными тогда и только тогда, когда они гарантируют выработку одних и тех
же результатов, независимо от начального состояния базы данных. Таким образом, гра-
фик называется упорядочиваемым и правильным тогда и только тогда, когда он эквивален-
тен некоторому последовательному графику.
Следует отметить, что два разных последовательных графика, в которых участвуют
одни и те же транзакции, вполне могут вырабатывать разные результаты, и это при том,
что оба графика являются правильными. Это означает, что два разных чередующихся
правильных графика, в которых участвуют одни и те же транзакции, также могут выраба-
тывать различные результаты. В качестве примера рассмотрим транзакцию А, смысл ко-
торой сводится к тому, чтобы “сложить 1 с х”, и транзакцию в, которая имеет своей це-
лью “удвоить х” (где х — некоторый элемент в базе данных). Предположим также, что
начальное значение х равно 10. В таком случае последовательный график “А, затем в”
приводит к получению результата х = 22, а последовательный график “вначале в, затем А “
приводит к получению результатах = 21. Оба эти результата в равной степени являются
правильными, и поэтому любой график, который гарантирует эквивалентность последо-
вательным графикам “вначале А, затем В” или “вначале в, затем А”, также является пра-
вильным.
Понятие упорядочиваемоеTM было впервые введено (хотя и не под таким названием)
Эсвараном (Eswaran) и др. в [16.6]. Кроме того, в той же статье была доказана важная
теорема, называемая теоремой двухфазной блокировки, которую мы будем рассматривать
в приведенной ниже формулировке 4 .
Если все транзакции подчиняются протоколу двухфазной блокировки, то все возможные
чередующиеся графики являются упорядочиваемыми.
Протокол двухфазной блокировки, в свою очередь, формулируется следующим образом:
■ прежде чем выполнить операцию с любым объектом (например, кортежем базы
данных), транзакция должна приобрести блокировку на этот объект;
■ после освобождения любой блокировки транзакция больше не должна приобре
тать какие-либо дополнительные блокировки.
Таким образом, любая транзакция, которая подчиняется этому протоколу, имеет две
фазы: фаза приобретения блокировок (или фаза расширения) и фаза освобождения бло-
кировок (или фаза сужения).
Примечание. На практике фаза сужения часто сводится к единственной операции
или ROLLBACK , выполняемой в конце транзакции (к этой теме мы вернемся в
разделах 16.7 и 16.8). Если соблюдается такое условие, то данный протокол становится
равносильным строгой версии, которая была описана в разделе 16.3.
Рассматриваемое здесь понятие упорядочиваемости оказывает значительную помощь
в анализе этой области, которая может стать источником многих затруднений, поэтому в
данном разделе приведено еще несколько дополнительных замечаний на эту тему. Пред-
положим, что I — чередующийся график, который охватывает некоторое множество
транзакций Т1, Т2, . . ., тп. Если график I является упорядочиваемым, то существует
по меньшей мере один последовательный график S, который включает множество
транзакций Т1, Т2, . . ., Тп, такой что I эквивалентен S. График s называется упо-
рядочением графика I.
Теперь предположим, что Ti и тj — две любые разные транзакции в множестве Т1,
Т2, . . ., Тп. Допустим, что Ti предшествует Tj в упорядочении S. Поэтому в чере-
дующемся графике I достигнутый эффект организации чередующегося выполнения
должен быть таким, как если бы транзакция Ti действительно выполнялась перед Tj.
Иными словами, неформальной, но очень удобной характеристикой упорядочиваемости
является соблюдение того требования, что если А и в — любые две транзакции, участ-
вующие в некотором упорядочиваемом графике, то в этом графике либо А логически
предшествует в, либо в логически предшествует А; это означает, что либо в может вос-
пользоваться результатами выполнения А, либо А — результатами выполнения в.
(Если А вырабатывает выходные результаты х, у, . . . , z и в получает в качестве
входных любые из данных х, у, . . ., z, то в в любом случае получает эти данные
либо так, как если бы все они были выведены транзакцией А, либо все они были такими,
как перед выводом из транзакции А (т.е. перед ее выполнением), а не в виде смеси
результатов этих двух типов.) И наоборот, если эффект действия чередующегося
графика не сводится к такой ситуации, как если бы А выполнялась перед в или В
выполнялась перед А, то этот график нельзя считать упорядочиваемым и правильным.
Наконец, необходимо подчеркнуть такую мысль, что если некоторая транзакция А не
является двухфазной (т.е. не подчиняется протоколу двухфазной блокировки), то всегда
можно сформировать некоторую другую транзакцию в, которая может выполняться, че-
редуясь с А таким образом, что в результате будет получен общий график, не являющийся
упорядочиваемым и правильным. Отметим, что в целях уменьшения конкуренции за
ресурсы и повышения за счет этого производительности и пропускной способности, в
системах, применяемых на практике, обычно разрешено формирование транзакций, не
являющихся двухфазными; это означает, что транзакции могут преждевременно освобо-
ждать блокировки (до выполнения оператора COMMIT ), а затем приобретать другие бло-
кировки. Но должно быть вполне очевидно, что предложение использовать такие тран-
закции является довольно рискованным; при этом, допуская применение транзакция А,
не являющейся двухфазной, можно лишь надеяться на то, что в системе не будет выпол-
няться одновременно с А транзакция в, которая обращается к тем же данным (поскольку
при возникновении указанной ситуации система становится способной вырабатывать
неправильные ответы).

Question 6

Transactions: Isolation

Answer 6

УРОВНИ ИЗОЛЯЦИИ
Упорядочиваемость гарантирует изолированность транзакций, в той трактовке этого
термина, которая применяется при описании свойств ACID. Одним из непосредствен-
ных и весьма благоприятных следствий из этого факта является то, что если все графики
— упорядочиваемые, то прикладной программист, разрабатывая код для любой кон-
кретной транзакции А, не должен обращать абсолютно никакого внимания на тот факт,
что одновременно с ней в системе может выполняться некоторая другая транзакция в.
Но можно также утверждать, что протоколы, применяемые для обеспечения упорядочи-
ваемоеTM, снижают степень распараллеливания, или общую производительность системы,
до неприемлемых уровней. Поэтому на практике в системах обычно поддерживаются
целый ряд других уровней “изоляции” (этот термин заключен в кавычки, поскольку лю-
бой уровень ниже максимального означает, что транзакция в конечном итоге не является
в полном смысле слова изолированной от других, как показано ниже).
Уровень изоляции применительно к данной конкретной транзакции можно опреде-
лить как степень постороннего вмешательства, которую рассматриваемая транзакция
готова выдерживать в ходе параллельного выполнения транзакций. А если должна гаран-
тироваться упорядочиваемость, то единственно возможной степенью вмешательства,
которую следует допускать по отношению к любой транзакции, безусловно, является
полное отсутствие какого-либо вмешательства! Иными словами, уровень изоляции дол-
жен быть максимально возможным, поскольку в противном случае невозможно будет в
общем гарантировать наличие правильных, восстанавливаемых и не допускающих кас-
кадных откатов графиков. Но остается неоспоримым фактом то, что во многих системах,
как уже было сказано, обычно поддерживаются уровни изоляции меньше максимального,
и данный вопрос кратко рассматривается в настоящем разделе.
Может быть определено по меньшей мере пять разных уровней изоляции, но в [16.10],
в стандарте SQL и в СУБД DB2 поддерживаются лишь четыре. Вообще говоря, чем выше
уровень изоляции, тем меньше степень вмешательства транзакций в работу друг друга (и
тем ниже степень распараллеливания), а чем ниже уровень изоляции, тем больше степень
вмешательства (и выше степень распараллеливания). В качестве иллюстрации рассмот-
рим два уровня, поддерживаемых в СУБД DB2, — стабильность курсора и повторяемое
чтение. Максимальным уровнем является повторяемое чтение (Repeatable Read — RR);
если все транзакции действуют на этом уровне, то все графики становятся упорядочи-
ваемыми. В отличие от этого, при использовании другого уровня, а именно стабильности
курсора (Cursor Stability — CS) соблюдаются следующие условия:
■ если транзакция А получает возможность обратиться к некоторому кортежу 6 t и в
результате
■ приобретает блокировку на t, а затем
■ освобождает структуры адресации, применяемые для доступа к” кортежу t без его
обновления, и поэтому
■ не расширяет свою блокировку до уровня X, то
■ данная блокировка может быть освобождена без ожидания конца транзакции.
Но следует учитывать, что теперь некоторая другая транзакция в может обновить кор-
теж t и зафиксировать изменение. Если в дальнейшем транзакция А возвратится на не-
который предыдущий этап своей работы и снова прочитает кортеж t (следует отметить,
что при этом происходит нарушение протокола двухфазной блокировки!), то обнаружит
внесенное изменение и поэтому фактически столкнется с несовместимым состоянием
базы данных. С другой стороны, при повторяемом чтении (RR) все блокировки кортежей
(а не только блокировки X) удерживаются до конца транзакции и поэтому только что
указанная проблема не возникает.
Из этого следуют приведенные ниже выводы.
1. Указанная проблема является не единственной, которая может возникнуть при
использовании уровня CS; мы здесь привели ее описание лишь потому, что она
является наиболее очевидной. Но, к сожалению, из этого описания следует, что
уровень RR якобы требуется лишь в том сравнительно маловероятном случае, если
в некоторой определенной транзакции потребуется дважды считывать один и тот
же кортеж. С другой стороны, имеются весомые доводы в пользу того, что уровень
RR всегда является более приемлемым по сравнению с CS; транзакция, выпол
няемая в условиях применения CS, не является двухфазной и поэтому (как было
описано в предыдущем разделе) ее упорядочиваемость больше нельзя гарантиро
вать. Но другой весомый контрдовод состоит в том, что уровень CS обеспечивает
большую степень распараллеливания, чем RR (тем не менее, справедливость этого
утверждения является вероятной, но не обязательной).
2. Создается впечатление, что на практике часто недостаточно учитывается тот факт,
что при использовании уровня CS упорядочиваемость не может гарантироваться.
Поэтому следует еще раз подчеркнуть, что справедливо такое утверждение: “Если
транзакция т действует на уровне изоляции меньше максимального, то нельзя
больше гарантировать, что при выполнении т параллельно с другими транзакция
ми она переведет базу данных из одного правильного состояния в другое правиль
ное состояние”.
3. В любой реализации, которая поддерживает любой уровень изоляции ниже мак
симального, должны быть, как правило, предусмотрены некоторые средства яв
ного управления параллельностью, позволяющие пользователям создавать свои
приложения так, чтобы гарантировалась безопасность эксплуатации базы данных
в отсутствие подобных гарантий со стороны самой системы (обычно явно задан
ные операторы LOCK ). Например, в СУБД DB2 предусмотрен явно заданный опе
ратор LOCK TABLE, который дает возможность пользователям, работающим на
уровне меньше максимального, приобретать явные блокировки, превосходящие
те, которые приобретаются в DB2 автоматически для соблюдения требований те
кущего уровня. (Кстати, следует отметить, что в стандарте SQL не предусмотрены
подобные явно заданные механизмы управления параллельностью, как описано в
разделе 16.11.)
Кроме того, необходимо учитывать, что приведенное выше описание уровня RR как
максимального уровня изоляции относится к реализации повторяемого чтения в СУБД DB2. К сожалению, в стандарте SQL термин повторяемое чтение используется для обо-
значения уровня изоляции, который является строго более низким, чем максимальный
уровень (об этом также сказано в разделе 16.11).
Фантомы
Одной из особых проблем, которая может возникнуть, если транзакции действуют на
уровне изоляции меньше максимального, является так называемая проблема фантомов.
Рассмотрим приведенный ниже пример (он является довольно надуманным, но вполне
позволяет проиллюстрировать рассматриваемое понятие).
■ Прежде всего, предположим, что в транзакции А вычисляется средний остаток на
всех счетах, принадлежащих клиенту Джо. Допустим, что в настоящее время име
ются три таких счета и на каждом из них остаток составляет 100 долл. Поэтому
транзакция А просматривает три счета, в ходе своего выполнения приобретает на
них разделяемые блокировки и получает результат (100 долл.).
■ А теперь предположим, что выполняется параллельная транзакция в, в результате
которой в базу данных вводится еще один счет клиента Джо, с остатком 200 долл.
Для определенности допустим, что новый счет вводится после того, как в транзак
ции А было вычислено среднее значение, равное 100 долл. Предположим также,
что сразу же после введения нового счета в транзакции в происходит фиксация
(и освобождение исключительной блокировки нового счета, которой она владела).
■ Затем допустим, что было принято решение снова воспользоваться транзакцией А
для просмотра счетов клиента Джо, подсчета их количества и суммирования их ос
татков, а затем деления суммы остатков на количество счетов (возможно, потому
что пользователь захотел определить, действительно ли полученное раньше сред
нее значение равно сумме, деленной на количество). На данный момент обнару
живаются четыре счета вместо трех, а полученный результат равен 125 долл. вме
сто 100 долл.!
Итак, в данном случае в обоих транзакциях применялась строгая двухфазная блоки-
ровка и все же случилось что-то неправильное, а именно: в транзакции А было обнаруже-
но то, чего не существовало при первом ее выполнении, — фантом. Вследствие этого упо-
рядочиваемость была нарушена (очевидно, что в данном случае чередующееся выполне-
ние не эквивалентно ни последовательности “вначале А, затем в”, ни последовательно-
сти “вначале в, затем А”).
Но заслуживает особого внимания то, что рассматриваемая здесь проблема не имеет
ничего общего с двухфазной блокировкой как таковой. Скорее, эта проблема состоит в
том, что в транзакции А не было заблокировано то, что логически должно было быть за-
блокировано; вместо блокировки лишь трех имеющихся счетов клиента Джо в ней фак-
тически нужно было заблокировать множество всех счетов, принадлежащих Джо или,
иными словами, счетов, соответствующих предикату “владелец счета — Джо” (см. [16.6]
и [16.13]) 7 . Если бы можно было обеспечить такую возможность, то транзакции в при-
шлось бы перейти в состояние ожидания после осуществления в ней попытки ввести новый счет (поскольку в, безусловно, пришлось бы затребовать блокировку на этот новый счет, а
такая блокировка вошла бы в противоречие с блокировкой, принадлежащей транзакции А).
Хотя по причинам, описанным в [15.12], в большинстве современных систем не под-
держивается блокировка предикатов как таковая, в них все равно, как правило, удается
избежать возникновения фантомов благодаря блокировке пути доступа, который ис-
пользуется для обращения к рассматриваемым данным. Например, если в случае исполь-
зования тех счетов, которые принадлежат Джо, путем доступа является индекс на имени
клиента, то система может заблокировать запись в этом индексе, относящуюся к клиенту
Джо. Такая блокировка предотвращает возникновение фантомов, поскольку для созда-
ния такого фантома требуется обновление пути доступа (в данном примере записи ин-
декса) и поэтому приобретение блокировки X на такой путь доступа. Дополнительные
сведения на эту тему приведены в [15.12].

Question 7

Optimization database (performance, volume)

Answer 7

Для реляционных систем оптимизация представляет собой как проблему,
так и благоприятную возможность. Проблема состоит в том, что для
достижения приемлемого уровня производительности оптимизация в подобных
системах просто необходима. Причем одной из сильных сторон и несомненных
достоинств реляционного подхода является то, что реляционные выражения
реализуются и оптимизируются на достаточно высоком семантическом уровне.
В противоположность этому, в нереляционных системах, где запросы
пользователей выражаются на более низком семантическом уровне, любая
“оптимизация” должна выполняться самим пользователем вручную (здесь
термин “оптимизация” взят в кавычки, поскольку обычно он употребляется для
обозначения автоматической, а не ручной оптимизации). В подобных системах
пользователь (а не система) определяет, какие именно низкоуровневые
операции должны быть выполнены и в какой последовательности. И если
пользователь принял неправильное решение, то система не способна исправить
положение. Отметим также, что для работы в подобных системах пользователь
должен обладать некоторыми навыками в программировании, иначе он не
сможет достаточно полно применять средства этих систем.
Преимущество автоматической оптимизации заключается в том, что пользователь
может не задумываться над наилучшим способом выражения своих запросов (т.е. над
тем, как следует сформулировать запрос, чтобы система выполнила его с максимальной
производительностью). Но и это далеко не все. Вполне вероятно, что оптимизатор сфор-
мулирует запрос лучше, чем сам пользователь. Для подобного утверждения есть несколько
веских причин. Ниже приведены лишь некоторые из них.
1. Хороший оптимизатор обладает большим объемом полезной информации, кото
рая для пользователя обычно недоступна. Говоря конкретнее, оптимизатор владе
ет определенными статистическими данными (в частности о кардинальности пе
ременных отношения и т.д.), в том числе следующими:
■ количество различных значений каждого типа;
■ текущее количество кортежей в каждой базовой переменной отношения;
■ текущее количество различающихся значений для каждого атрибута в каждой
базовой переменной отношения;
■ количество вхождений каждого значения в каждом из атрибутов и т.п.
(Вся эта информация хранится в системном каталоге, о чем речь пойдет ниже в
этой главе, в разделе 18.5.) Благодаря наличию таких данных оптимизатор спосо-
бен более точно оценить эффективность любой возможной стратегии реализации
конкретного запроса. Исходя из полученных результатов он сможет выбрать наи-
лучшую стратегию реализации запроса.
2. Если со временем статистические показатели базы данных значительно изменятся
(например, в результате ее физической реорганизации), то при реализации запроса
может оказаться целесообразнее использовать иную стратегию, отличную от при
менявшейся ранее. Другими словами, возникнет необходимость в повторной оп
тимизации, или реоптимизации. В реляционных системах процесс реоптимизации
вполне тривиален и сводится к простой повторной обработке исходного запроса
системным оптимизатором. В нереляционных же системах выполнение реоптими
зации, как правило, требует корректировки программы и, вполне возможно, мо
жет оказаться вообще невыполнимым.
3. Оптимизатор — это программа, которая по определению “всегда доводит начатую
работу до конца”, в отличие от человека. Оптимизатор способен рассматривать
буквально сотни различных стратегий реализации конкретного запроса, в то время
как программист едва ли проанализирует более трех-четырех возможных страте
гий (по крайней мере, достаточно глубоко).
4. В оптимизаторе реализованы знания и опыт лучших из лучших программистов, в
результате чего эти знания и опыт становятся доступными для всех. Это позволяет
применять ограниченный набор ресурсов, предоставленный широкому кругу
пользователей, наиболее эффективно и экономично.
Приведенные выше соображения служат убедительным доказательством сделанного в
начале данного раздела заявления о том, что оптимизируемость (т.е. возможность оптими-
зации запросов) является сильной стороной реляционных систем.
Общее назначение оптимизатора состоит в выборе наиболее эффективной стратегии
вычисления реляционного выражения. В этой главе описаны некоторые фундаментальные принципы и методы, применяемые в процессе оптимизации. После обсуждения вступи-
тельного примера, приведенного в разделе 18.2, в разделе 18.3 предложен обзор принци-
пов работы оптимизатора. Затем в разделе 18.4 обсуждается один из важнейших аспектов
процедуры оптимизации — преобразование выражений (или перезапись запроса). Далее в
разделе 18.5 кратко излагается вопрос о статистических показателях базы данных. В
разделе 18.6 дается более подробное описание одного из конкретных методов оптими-
зации, известного как декомпозиция запросов. Затем в разделе 18.7 обсуждается вопрос о
том, как в действительности реализуются некоторые реляционные операторы (например
оператор соединения и др.), и кратко описывается использование рассматривавшихся в
разделе 18.5 статистических показателей для вычисления стоимостных оценок. Наконец,
в разделе 18.8 приводится краткое резюме по всему материалу данной главы.
Еще одно вводное замечание. Достаточно часто данную тему связывают с оптимизацией
запросов. Однако подобный термин несколько неточен, поскольку выражение, которое
нужно оптимизировать (запрос), на самом деле может формироваться в контексте, отлич-
ном от интерактивной выборки информации из базы данных. В частности, оно может
быть частью операции обновления, а не операции выборки, понимаемой под запросом.
Более того, сам по себе термин оптимизация является несколько преувеличенным, так
как обычно не существует гарантий, что выбранная стратегия реализации действительно
оптимальна в некотором объективном смысле. На практике под оптимизированной стра-
тегией реализации обычно понимается просто улучшенный вариант исходного неоптими-
зированного выражения. (Тем не менее, в некоторых немногочисленных случаях можно
вполне обоснованно утверждать, что выбранная стратегия реализации будет действи-
тельно оптимальной в определенном смысле [18.30]. См. также приложение А.)

ПРИМЕР ВЫПОЛНЕНИЯ ОПТИМИЗАЦИИ
Начнем изложение с простого примера (он уже кратко рассматривался в разделе 7.6
главы 7), дающего представление о поразительных результатах, которых можно достичь с
помощью оптимизации. Рассмотрим следующий запрос: “Определить имена поставщи-
ков детали с номером Р2”. Алгебраическая запись этого запроса такова:
( ( SP JOIN S ) WHERE P# = Р# (‘Р2’) ) { SNAME }
Предположим, что в базе данных содержится информация о 100 поставщиках и 10 000
поставок деталей, из которых только 50 включают партии деталей с номером Р2. Предпо-
ложим для простоты, что переменные отношения s и SP сохраняются на диске как два
отдельно хранимых файла, в каждой записи которых помещается по одному кортежу
данных. В этом случае, если система будет вычислять данное выражение непосредственно
(т.е. вообще без оптимизации), последовательность выполняемых операций становится
такой, как описано ниже.
1. Соединение переменных отношения SP и S (по атрибуту S#). При выполнении этой
операции потребуется считать информацию о 10 000 поставок партий деталей и
10 000 раз считать информацию о 100 поставщиках (по одному разу для каждой
поставки деталей из 10 000). В результате будет получен промежуточный набор
данных, содержащий 10 000 соединенных кортежей. Этот набор данных записыва-
ется на диск (предположим, что для размещения промежуточного результата в ос-
новной (оперативной) памяти не хватает места).
2. Выборка из полученного на этапе 1 результата кортежей с данными о детали с номе
ром Р2. На этом этапе выполняется чтение 10 000 соединенных кортежей обратно
в оперативную память, причем полученный результат состоит только из 50 корте
жей, которые, по нашему предположению, вполне могут поместиться в оператив
ной памяти.
3. Выполнение проекции по атрибуту SNAME результата, полученного на этапе 2. На
этом этапе формируется результирующий набор исходного запроса (состоящий
максимум из 50 кортежей, которые вполне могут быть размещены в оперативной
памяти).
Представленная ниже процедура полностью эквивалентна описанной выше в том
смысле, что она обязательно приведет к тому же конечному результату, но он будет полу-
чен более эффективным способом.
1. Выборка из переменной отношения sp кортежей с данными только о детали с номе
ром Р2. На этом этапе выполняется чтение 10 000 кортежей и создается результи
рующий набор, состоящий только из 50 кортежей, который, как мы предполагаем,
может поместиться в оперативной памяти.
2. Соединение полученного на этапе 1 результата с переменной отношения S (по атрибу
ту s#). На этом этапе выполняется считывание данных обо всех 100 поставщиках
(но только один раз, а не по одному разу для каждой поставки партии деталей Р2,
так как данные обо всех поставленных партиях деталей с номером Р2 уже находят
ся в оперативной памяти). Результат содержит 50 соединенных кортежей (которые
также помещаются в оперативной памяти).
3. Выполнение проекции по атрибуту SNAME результата, полученного на этапе 2 (анало
гично этапу 3 предыдущей последовательности действий). Требуемый результат
(не более 50 кортежей) помещается в оперативной памяти.
В первой из показанных процедур в целом выполняется 1 030 000 операций ввода-
вывода кортежей, в то время как во второй процедуре выполняется только 10 100 опера-
ций ввода-вывода. Итак, совершенно очевидно, что если принять в качестве меры оцен-
ки производительности количество выполненных операций ввода—вывода кортежей, то
вторая процедура больше чем в 100 раз эффективнее первой. Кроме того, вполне понят-
но, что предпочтительнее реализовать данный запрос именно с помощью второй проце-
дуры, а не первой!
Примечание. На практике мерой оценки производительности служит количество опе-
раций ввода—вывода страниц, а не отдельных кортежей, но для упрощения предполо-
жим, что каждый кортеж занимает отдельную страницу.
Приведенный пример показывает, что следствием даже незначительных изменений в
алгоритме реализации (выполнения выборки, а затем соединения, вместо соединения
и последующей выборки) может быть существенное увеличение производительности
(в сотни раз). Производительность повысится еще больше, если переменная отношения
SP будет индексирована или хэширована по атрибуту Р#. В этом случае количество кор-
тежей, считываемых на этапе 1 второй процедуры, уменьшится с 10 000 всего лишь до 50,
в результате чего вся процедура окажется в 7 000 раз эффективнее ее исходного варианта.
Аналогично этому, применение индекса или хэш-функции для доступа к атрибуту S. S#
позволит уменьшить количество операций ввода—вывода кортежей на этапе 2 со 100 до 50,
в результате чего процедура вычисления запроса окажется более чем в 10 000 раз эффек-
тивнее исходного варианта. Это означает, что если на вычисление исходного варианта
реализации запроса потребуется три часа, то оптимизированная версия этого же запроса
будет выполнена примерно за одну секунду. К тому же, безусловно, возможны и многие
другие улучшения.
Несмотря на то, что приведенный выше пример достаточно прост, он весьма нагляд-
но демонстрирует необходимость использования оптимизации. Кроме того, он показы-
вает вероятные улучшения, которые могут применяться на практике. В следующем раз-
деле используется более систематический подход к решению проблемы оптимизации.
В частности, в нем описано, как общая проблема может быть разделена на последова-
тельность из нескольких более или менее независимых подзадач. Это позволит нам пе-
рейти к рассмотрению отдельных стратегий и приемов оптимизации, обсуждаемых в сле-
дующих разделах.

ОПТИМИЗАЦИЯ ЗАПРОСОВ
Рассмотрим четыре стадии процесса оптимизации запросов, который схематически
представлен на рис. 18.1.
1. Преобразование запроса во внутреннюю форму.
2. Преобразование запроса в каноническую форму.
3. Выбор потенциальных низкоуровневых процедур.
4. Генерация различных вариантов планов вычисления запроса и выбор плана с ми
нимальными затратами.
Перейдем к подробному рассмотрению каждой стадии процесса оптимизации.
Стадия 1. Преобразование запроса во внутреннюю форму
На этой стадии выполняется преобразование первоначального запроса в некоторое
внутреннее представление, более удобное для машинной обработки. В результате из рас-
смотрения полностью исключаются конструкции сугубо внешнего уровня (например,
разнообразные варианты конкретного синтаксиса используемого языка запросов) и го-
товится почва для последующих стадий оптимизации.
Примечание. Обработка представлений (т.е. процесс замены ссылок на представления
выражениями, определяющими соответствующие представления) также выполняется на
этом этапе.
Возникает очевидный вопрос: “Какое формальное представление должно использо-
ваться для внутреннего представления запроса?”. Независимо от того, какой именно ва-
риант формального представления будет выбран, он должен быть достаточно полным,
чтобы допускать представление любых запросов, которые могут быть определены на
внешнем языке запросов. Кроме того, выбранный способ формального представления
должен быть нейтральным, насколько это возможно, в том смысле, что он не должен за-
ранее предопределять последующие оптимизационные решения. Чаще всего для внут-
реннего представления запросов используется та или иная модификация абстрактного
синтаксического дерева, которое в этом случае называют деревом запроса. Например, на
рис. 18.2 показано дерево для запроса, рассматривавшегося выше в этой же главе в разделе
18.2 (“Определить имена поставщиков детали с номером Р2”).
Однако для наших целей удобнее всего предположить, что для внутреннего представ-
ления запросов используется один из тех формальных методов, с которыми мы уже зна-
комы: реляционная алгебра или реляционное исчисление. В этом случае дерево запроса,
подобное представленному на рис. 18.2, можно рассматривать просто как альтернатив-
ный схематический вариант представления некоторого выражения, записанного в системе обозначений одного из двух предложенных выше формальных методов (реляционная
алгебра или реляционное исчисление). Предположим, что выбранный формальный ме-
тод — реляционная алгебра. С этого момента будем считать, что внутренним представле-
нием дерева запроса, показанного на рис. 18.2, является следующее алгебраическое вы-
ражение 1 :
( { SP JOIN S ) WHERE P# = Р# (‘Р2’) ) { SNAME }
Стадия 2. Преобразование запроса в каноническую форму
На этой стадии оптимизатор выполняет несколько операций оптимизации, которые
гарантированно являются приемлемыми независимо от реальных значений данных и су-
ществующих путей доступа к ним. Суть в том, что обычно реляционные языки позволяют
сформулировать любые запросы (за исключением разве что простейших) несколькими
разными (по крайней мере, внешне) способами. Например, даже простой запрос
“Определить имена поставщиков детали с номером Р2” на языке SQL может быть запи-
сан буквально десятками способов 2 , не считая таких тривиальных вариантов, как замена
А = в на в = А или р AND q на q AND p. Производительность вычисления запроса
не должна зависеть от формы записи запроса, которую выбрал пользователь. Поэтому
следующий этап в обработке запроса — преобразование его внутреннего представления
в некоторую эквивалентную каноническую форму (см. следующий абзац). Назначением
данного преобразования является исключение внешних различий в эквивалентных пред-
ставлениях запроса и, что более важно, поиск представления запроса, в некотором смыс-
ле более эффективного по сравнению с исходным представлением.
Замечание о канонической форме. Понятие канонической формы является центральным
во многих разделах математики и связанных с ней дисциплинах. Каноническая форма
может быть определена следующим образом. Пусть Q — множество объектов (запросов) и
пусть существует понятие об их эквивалентности (а именно, запросы ql и q2 эквива-
лентны тогда и только тогда, когда дают идентичные результаты). Тогда подмножество С
множества Q является множеством канонических форм для запросов из множества Q в
смысле определенной выше эквивалентности тогда и только тогда, когда каждому объекту
q из множества Q соответствует только один объект с из множества с. В этом случае
говорят, что объект с является канонической формой объекта q. Все интересующие нас
свойства, которыми обладает объект q, присущи также объекту с. Поэтому, чтобы дока-
зать различные интересующие нас результаты, достаточно изучить менее мощное множе-
ство объектов С, а не более мощное множество Q.
Вернемся к основной теме обсуждения. Чтобы преобразовать результаты выполнения
стадии 1 в некоторую эквивалентную, но более эффективную форму, оптимизатор ис-
пользует определенные и хорошо известные правила, или законы преобразования. Ниже
приведен пример такого правила. Здесь выражение
( A JOIN В ) WHERE ограничение, распространяющееся на А
может быть преобразовано в эквивалентное, но более эффективное выражение
( A WHERE ограничение, распространяющееся на А ) JOIN В
Подобное преобразование кратко рассматривалось в разделе 7.6 главы 7. Кроме того,
оно было описано выше, при обсуждении примера в разделе 18.2, который ясно проде-
монстрировал, зачем нужны подобные преобразования. Многие другие правила преобра-
зования описываются ниже, в разделе 18.4.
Стадия 3. Выбор потенциальных низкоуровневых процедур
После преобразования внутренней формы запроса в более подходящую (каноничес-
кую) форму, оптимизатор должен определить, как следует выполнять запрос, представ-
ленный в этой канонической форме. На данной стадии принимаются во внимание такие
факторы, как наличие индексов и других физических путей доступа, статистическое рас-
пределение существующих значений данных, физическая кластеризация хранимых дан-
ных и т.п. Обратите внимание на то, что на стадиях 1 и 2 этим аспектам совсем не уделя-
лось внимания.
Основная стратегия состоит в том, чтобы рассматривать выражение запроса как се-
рию низкоуровневых операций 3 , которые в определенной степени зависят одна от другой.
Ниже приведен пример такой взаимной зависимости. При программной реализации
операции проекции обычно требуется, чтобы считываемые кортежи следовали в опреде-
ленном порядке; это позволяет исключить дублирующиеся результирующие кортежи.
В свою очередь, это означает, что операция, выполняемая непосредственно перед опера-
цией проекции, должна выдавать выходные кортежи именно в такой, требуемой после-
довательности.
Для каждой низкоуровневой операции (а также, возможно, для нескольких часто
встречающихся комбинаций подобных операций) оптимизатор имеет набор низкоуров-
невых процедур реализации. Например, существует набор процедур для реализации опе-
рации сокращения: по условию равенства определенному значению потенциального
ключа; на основе индексированного атрибута, по которому выполняется сокращение; на
основе хэшированного атрибута и т.д. Примеры таких процедур приведены ниже, в раз-
деле 18.7 (см. также [18.7], [18.12]).
С каждой процедурой связана параметризованная формула стоимости, позволяющая
оценить стоимость выполнения процедуры (т.е. уровень затрат, требуемых для ее выпол-
нения). Чаще всего стоимость определяется путем подсчета количества необходимых
дисковых операций ввода-вывода, но некоторые системы учитывают также время ис-
пользования процессора и другие факторы. Эти формулы стоимости применяются на
стадии 4 (см. следующий подраздел). В [18.7]—[18.12] обсуждаются и анализируются
формулы стоимости для различных процедур реализации при разных исходных предпо-
ложениях (см. также раздел 18.7).
Далее, используя сохраняемую в каталоге информацию о состоянии базы данных (су-
ществующие индексы, текущую кардинальность переменных отношения и т.п.) и сведения о взаимных зависимостях, упоминавшихся выше, оптимизатор выбирает одну или не-
сколько процедур-кандидатов для каждой низкоуровневой операции в запросе. Этот
процесс обычно называют выбором пути доступа (см. также [18.33]).
Примечание. Следует отметить, что в [18.33] термин выбор пути доступа используется
для ссылки на определенные в данной главе стадии 3 и 4, а не только на стадию 3. Дейст-
вительно, на практике очень трудно разграничить, где заканчивается одна стадия и начи-
нается другая; просто стадия 3 более или менее плавно переходит в стадию4.
Стадия 4. Генерация различных вариантов планов вычисления запроса и выбор плана с
минимальными затратами
На последней стадии процесса оптимизации создается набор потенциальных планов
запроса, после чего осуществляется выбор лучшего (т.е. наименее дорогостоящего) плана
выполнения запроса. Каждый план выполнения формируется как комбинация некото-
рого набора потенциальных процедур реализации, причем каждой низкоуровневой опе-
рации в запросе соответствует одна процедура. Отметим, что обычно для поступившего
запроса может существовать много планов выполнения запроса (возможно, даже слиш-
ком много). На практике, вероятно, не стоит генерировать все возможные планы запро-
са, так как одни из них могут быть комбинаторными версиями других планов выполне-
ния этого же запроса, и сам процесс выбора наиболее эффективного плана может стать
чрезмерно дорогостоящим. При выборе плана с наименьшей стоимостью рекомендуется
(возможно, даже требуется) руководствоваться некоторыми эвристическими правилами,
позволяющими ограничить количество анализируемых планов запросов разумными пре-
делами, но см. [18.53]. Практику ограничения количества запросов разумными пределами
иначе называют сокращением пространства поиска, поскольку ее можно рассматривать и
как уменьшение диапазона анализируемых оптимизатором вариантов {пространства по-
иска) до контролируемых пределов.
Несомненно, для выбора плана с наименьшей стоимостью необходим метод опреде-
ления стоимости любого возможного плана. По сути, стоимость плана — это просто сум-
ма стоимостей отдельных процедур, входящих в его состав. Поэтому задача оптимизатора
сводится к вычислению формул стоимости для каждой отдельной процедуры. Основная
проблема состоит в том, что формулы стоимости выполнения процедуры зависят от раз-
мера отношения (или отношений), которое обрабатывает эта процедура. Поскольку все
запросы, за исключением самых простых, требуют создания некоторых промежуточных
результатов выполнения (по меньшей мере, концептуально), оптимизатор должен быть
способен оценить размер этих промежуточных результатов и использовать полученные
значения при вычислении формул стоимости. К сожалению, размеры промежуточных
наборов данных сильно зависят от конкретных значений хранимых данных, поэтому
точная оценка стоимости может оказаться достаточно сложной задачей. В [18.2], [18.3]
обсуждаются некоторые подходы к решению этой проблемы и приводятся ссылки на
другие публикации.

Question 8

Optimizing the Database Design by Denormalizing

Answer 8

You implement normalization with a specific purpose: to maintain data integrity. However, in a real-life project, you typically have to bring back some data redundancy either for performance reasons or to maintain a history.
A fully normalized schema shows current state only. For example, in an invoicing application that is in a fully normalized design, you keep a customer’s address only in the Customers table. Suppose that a customer moves and you update that customer’s address with the new one. A few days later, the same customer reports that he accidentally lost some printed invoices during the move and asks you to print copies of lost invoices. It would be impossible to print exact copies of the invoices if you do not maintain some history about the customer’s address. You can solve this problem by maintaining a copy of customer address information on the invoice date in the Invoices table. Similarly, customers can change their name, so you also need to maintain a copy of customer names as part of the invoice data in the Invoices table.
During the normalization process, you decompose tables into more tables. The more tables you have, the more joins you have to perform in your queries, and joins have a negative impact on performance. To help, you can replicate a foreign key from the first child table to the second one. Take the invoicing system example again. Say you have an Employees parent table, and you add the EmployeeId column to the Customers table to serve as the foreign key because every customer has an account manager. Now, your typical queries must find invoices together with customer account manager data, requiring you to join three tables—Invoices, Customers, and Employees. However, if you replicate the EmployeeId column in the Invoices table, you can achieve the same goal and satisfy the same query by joining only the Invoices and Employees tables
The best way to boost performance in a normalized system is to use derived data. For example, before creating an invoice item, you must check whether a product is in stock. You can always calculate levels and states from events, but what if you had to aggregate all the events for the current year just to tell a customer the product he or she wants to buy is out of stock? The customer would probably never return. You can solve this problem by maintaining total quantity in stock in a column in the Products table and by maintaining a separate ProductsIn-Warehouses table that holds the quantity of products in stock in your warehouses (if you have multiple warehouses).
Finally, you might have many queries that aggregate sales across customers. In a fully normalized system, you would have to aggregate all invoice details for a single customer multiple times. You can greatly improve performance by maintaining the year-to-date sales summary in a column in the Customers table. Figure 2-3 shows ER diagrams of the invoicing database before normalization, and Figure 2-4 shows ER diagrams after denormalization.
Still, denormalization brings the danger of update anomalies back to the database. Therefore, you have to do it deliberately. You should document any denormalization thoroughly. To make sure your application correctly maintains denormalized data, you need to use transactions appropriately. A transaction is the smallest unit of work that must either complete entirely or not at all. For example, in the Invoices system, a transaction might mean an insertion to a table such as InvoiceDetails, which must be followed immediately by an update of the derived-level column TotalInStock in the Product table or a StockLevel column in the ProductsIn-Warehouses table, depending where you maintain the stock level information. If one of those actions fails, the entire transaction is rolled back to ensure data consistency. An even better choice for maintaining denormalized data, however, is to leave that task to the RDBMS. You can do this by introducing data manipulation language (DML) triggers. A RDBMS fires a trigger automatically as part of a transaction. In the invoices example, a DML trigger for insert, update, and delete on the InvoiceDetails table can maintain the TotalInStock column and the ProductsInWarehouses table. In addition, you should have procedures in place to rebuild the derived data from scratch. You can always rebuild this data from events tables in case of inconsistency between the sum of events and states.
IMPORTANT Maintain denormalized data in transactions
After a denormalization, you have to make sure to maintain the denormalized data in transactions. For example, you have to correct the stock level any time you sell a product in a single transaction.
For reports and analysis, a better practice than maintaining aggregate information in an OLTP database is to introduce a data warehouse, which is based on a somewhat denormalized multidimensional model and a Microsoft Online Analytical Processing (OLAP) system. An OLAP database management system typically takes care of the aggregations for you.

Normalization is the process of putting one fact in one appropriate place. This optimizes updates at the expense of retrievals. When a fact is stored in only one place, retrieving many different
but related facts usually requires going to many different places. This tends to slow the retrieval process. Updating is quicker, however, because the fact you’re updating exists in only one
It is generally recognized that all relational database designs should be based on a normalized logical data model. With a normalized data model, one fact is stored in one place, related facts
about a single entity are stored together, and every column of each entity refers non-transitively to only the unique identifier for that entity. Although an in-depth discussion of normalization is
beyond the scope of this article, brief definitions of the first three normal forms follow:
In first normal form, all entities must have a unique identifier, or key, that can be composed of one or more attributes. In addition, all attributes must be atomic and non-repeating.
(Atomic means that the attribute must not be composed of multiple attributes. For example, EMPNO should not be composed of social security number and last name because these are separate
attributes.)
In second normal form, all attributes that are not part of the key must depend on the entire key for that entity.
In third normal form, all attributes that are not part of the key must not depend on any other non-key attributes.
Frequently, however, performance needs dictate very quick retrieval capability for data stored in relational databases. To accomplish this, sometimes the decision is made to denormalize the
physical implementation. Denormalization is the process of putting one fact in numerous places. This speeds data retrieval at the expense of data modification.
It is not the intention of this article to promote the concept of denormalization. Of course, a normalized set of relational tables is the optimal environment and should be implemented for whenever
possible. Yet, in the real world, denormalization is sometimes necessary. Denormalization is not necessarily a bad decision if implemented wisely. You should always consider these issues before
denormalizing:
can the system achieve acceptable performance without denormalizing?
will the performance of the system after denormalizing still be unacceptable?
will the system be less reliable due to denormalization?
Frequently, however, performance needs dictate very quick retrieval capability for data stored in relational databases. To accomplish this, sometimes the decision is made to denormalize the
physical implementation. Denormalization is the process of putting one fact in numerous places. This speeds data retrieval at the expense of data modification.
It is not the intention of this article to promote the concept of denormalization. Of course, a normalized set of relational tables is the optimal environment and should be implemented for whenever
possible. Yet, in the real world, denormalization is sometimes necessary. Denormalization is not necessarily a bad decision if implemented wisely. You should always consider these issues before
denormalizing:
can the system achieve acceptable performance without denormalizing?
will the performance of the system after denormalizing still be unacceptable?
will the system be less reliable due to denormalization?
If the answer to any of these questions is “yes,” then you should avoid denormalization because any benefit that is accrued will not exceed the cost. If, after considering these issues, you
decide to denormalize be sure to adhere to the general guidelines that follow.
If enough DASD is available at your shop, create two sets of tables: one set fully normalized and another denormalized. Populate the denormalized versions by querying the data in the normalized
tables and loading or inserting it into the denormalized tables. Your application can access the denormalized tables in a read-only fashion and achieve performance gains. It is imperative that a
controlled and scheduled population function is maintained to keep the data in the denormalized and normalized tables synchronized.
If DASD is not available for two sets of tables, then maintain the denormalized tables programmatically. Be sure to update each denormalized table representing the same entity at the same time, or
alternately, to provide a rigorous schedule whereby tables will be synchronized. At any rate, all users should be informed of the implications of inconsistent data if it is deemed impossible to
avoid unsynchronized data.
When updating any column that is replicated in many different tables, always update it everywhere that it exists simultaneously, or as close to simultaneously as possible given the physical
constraints of your environment. If the denormalized tables are ever out of sync with the normalized tables be sure to inform end-users that batch reports and on-line queries may not contain sound
data; if at all possible, this should be avoided.
Finally, be sure to design the application so that it can be easily converted from using denormalized tables to using normalized tables.

The Reason for Denormalization
Only one valid reason exists for denormalizing a relational design – to enhance performance. However, there are several indicators which will help to identify systems and tables which are potential
denormalization candidates. These are:
Many critical queries and reports exist which rely upon data from more than one table. Often times these requests need to be processed in an on-line environment.
Repeating groups exist which need to be processed in a group instead of individually.
Many calculations need to be applied to one or many columns before queries can be successfully answered.
Tables need to be accessed in different ways by different users during the same timeframe.
Many large primary keys exist which are clumsy to query and consume a large amount of DASD when carried as foreign key columns in related tables.
Certain columns are queried a large percentage of the time. Consider 60% or greater to be a cautionary number flagging denormalization as an option.
Be aware that each new RDBMS release usually brings enhanced performance and improved access options that may reduce the need for denormalization. However, most of the popular RDBMS products on
occasion will require denormalized data structures. There are many different types of denormalized tables which can resolve the performance problems caused when accessing fully normalized data. The
following topics will detail the different types and give advice on when to implement each of the denormalization types.

Links:

https: //docs.microsoft.com/en-us/previous-versions/tn-archive/cc505841(v=technet.10)?redirectedfrom=MSDN
http: //tdan.com/denormalization-guidelines/4142

Question 9

Preferred using of key-value storages

Answer 9

It’s a truism that we should choose the right tool for the job. Everyone says that. And who can disagree? The problem is this is not helpful advice without being able to answer more specific questions like: What jobs are the tools good at? Will they work on jobs like mine? Is it worth the risk to try something new when all my people know something else and we have a deadline to meet? How can I make all the tools work together?
In the NoSQL space this kind of real-world data is still a bit vague. When asked, vendors tend to give very general answers like NoSQL is good for BigData or key-value access. What does that mean for for the developer in the trenches faced with the task of solving a specific problem and there are a dozen confusing choices and no obvious winner? Not a lot. It’s often hard to take that next step and imagine how their specific problems could be solved in a way that’s worth taking the trouble and risk.
Let’s change that. What problems are you using NoSQL to solve? Which product are you using? How is it helping you? Yes, this is part the research for my webinar on December 14th, but I’m a huge believer that people learn best by example, so if we can come up with real specific examples I think that will really help people visualize how they can make the best use of all these new product choices in their own systems.
Here’s a list of uses cases I came up with after some trolling of the interwebs. The sources are so varied I can’t attribute every one, I’ll put a list at the end of the post. Please feel free to add your own. I separated the use cases out for a few specific products simply because I had a lot of uses cases for them they were clearer out on their own. This is not meant as an endorsement of any sort. Here’s a master list of all the NoSQL products. If you would like to provide a specific set of use cases for a product I’d be more than happy to add that in.

General Use Cases
These are the general kinds of reasons people throw around for using NoSQL. Probably nothing all that surprising here.
Bigness. NoSQL is seen as a key part of a new data stack supporting: big data, big numbers of users, big numbers of computers, big supply chains, big science, and so on. When something becomes so massive that it must become massively distributed, NoSQL is there, though not all NoSQL systems are targeting big. Bigness can be across many different dimensions, not just using a lot of disk space.
Massive write performance. This is probably the canonical usage based on Google’s influence. High volume. Facebook needs to store 135 billion messages a month. Twitter, for example, has the problem of storing 7 TB/data per day with the prospect of this requirement doubling multiple times per year. This is the data is too big to fit on one node problem. At 80 MB/s it takes a day to store 7TB so writes need to be distributed over a cluster, which implies key-value access, MapReduce, replication, fault tolerance, consistency issues, and all the rest. For faster writes in-memory systems can be used.
Fast key-value access. This is probably the second most cited virtue of NoSQL in the general mind set. When latency is important it’s hard to beat hashing on a key and reading the value directly from memory or in as little as one disk seek. Not every NoSQL product is about fast access, some are more about reliability, for example. but what people have wanted for a long time was a better memcached and many NoSQL systems offer that.
Flexible schema and flexible datatypes. NoSQL products support a whole range of new data types, and this is a major area of innovation in NoSQL. We have: column-oriented, graph, advanced data structures, document-oriented, and key-value. Complex objects can be easily stored without a lot of mapping. Developers love avoiding complex schemas and ORM frameworks. Lack of structure allows for much more flexibility. We also have program and programmer friendly compatible datatypes likes JSON.
Schema migration. Schemalessness makes it easier to deal with schema migrations without so much worrying. Schemas are in a sense dynamic, because they are imposed by the application at run-time, so different parts of an application can have a different view of the schema.
Write availability. Do your writes need to succeed no mater what? Then we can get into partitioning, CAP, eventual consistency and all that jazz.
Easier maintainability, administration and operations. This is very product specific, but many NoSQL vendors are trying to gain adoption by making it easy for developers to adopt them. They are spending a lot of effort on ease of use, minimal administration, and automated operations. This can lead to lower operations costs as special code doesn’t have to be written to scale a system that was never intended to be used that way.
No single point of failure. Not every product is delivering on this, but we are seeing a definite convergence on relatively easy to configure and manage high availability with automatic load balancing and cluster sizing. A perfect cloud partner.
Generally available parallel computing. We are seeing MapReduce baked into products, which makes parallel computing something that will be a normal part of development in the future.
Programmer ease of use. Accessing your data should be easy. While the relational model is intuitive for end users, like accountants, it’s not very intuitive for developers. Programmers grok keys, values, JSON, Javascript stored procedures, HTTP, and so on. NoSQL is for programmers. This is a developer led coup. The response to a database problem can’t always be to hire a really knowledgeable DBA, get your schema right, denormalize a little, etc., programmers would prefer a system that they can make work for themselves. It shouldn’t be so hard to make a product perform. Money is part of the issue. If it costs a lot to scale a product then won’t you go with the cheaper product, that you control, that’s easier to use, and that’s easier to scale?
Use the right data model for the right problem. Different data models are used to solve different problems. Much effort has been put into, for example, wedging graph operations into a relational model, but it doesn’t work. Isn’t it better to solve a graph problem in a graph database? We are now seeing a general strategy of trying find the best fit between a problem and solution.
Avoid hitting the wall. Many projects hit some type of wall in their project. They’ve exhausted all options to make their system scale or perform properly and are wondering what next? It’s comforting to select a product and an approach that can jump over the wall by linearly scaling using incrementally added resources. At one time this wasn’t possible. It took custom built everything, but that’s changed. We are now seeing usable out-of-the-box products that a project can readily adopt.
Distributed systems support. Not everyone is worried about scale or performance over and above that which can be achieved by non-NoSQL systems. What they need is a distributed system that can span datacenters while handling failure scenarios without a hiccup. NoSQL systems, because they have focussed on scale, tend to exploit partitions, tend not use heavy strict consistency protocols, and so are well positioned to operate in distributed scenarios.
Tunable CAP tradeoffs. NoSQL systems are generally the only products with a “slider” for choosing where they want to land on the CAP spectrum. Relational databases pick strong consistency which means they can’t tolerate a partition failure. In the end this is a business decision and should be decided on a case by case basis. Does your app even care about consistency? Are a few drops OK? Does your app need strong or weak consistency? Is availability more important or is consistency? Will being down be more costly than being wrong? It’s nice to have products that give you a choice.

More Specific Use Cases
Managing large streams of non-transactional data: Apache logs, application logs, MySQL logs, clickstreams, etc.
Syncing online and offline data. This is a niche CouchDB has targeted.
Fast response times under all loads.
Avoiding heavy joins for when the query load for complex joins become too large for a RDBMS.
Soft real-time systems where low latency is critical. Games are one example.
Applications where a wide variety of different write, read, query, and consistency patterns need to be supported. There are systems optimized for 50% reads 50% writes, 95% writes, or 95% reads. Read-only applications needing extreme speed and resiliency, simple queries, and can tolerate slightly stale data. Applications requiring moderate performance, read/write access, simple queries, completely authoritative data. Read-only application which complex query requirements.
Load balance to accommodate data and usage concentrations and to help keep microprocessors busy.
Real-time inserts, updates, and queries.
Hierarchical data like threaded discussions and parts explosion.
Dynamic table creation.
Two tier applications where low latency data is made available through a fast NoSQL interface, but the data itself can be calculated and updated by high latency Hadoop apps or other low priority apps.
Sequential data reading. The right underlying data storage model needs to be selected. A B-tree may not be the best model for sequential reads.
Slicing off part of service that may need better performance/scalability onto it’s own system. For example, user logins may need to be high performance and this feature could use a dedicated service to meet those goals.
Caching. A high performance caching tier for web sites and other applications. Example is a cache for the Data Aggregation System used by the Large Hadron Collider.
Voting.
Real-time page view counters.
User registration, profile, and session data.
Document, catalog management and content management systems. These are facilitated by the ability to store complex documents has a whole rather than organized as relational tables. Similar logic applies to inventory, shopping carts, and other structured data types.
Archiving. Storing a large continual stream of data that is still accessible on-line. Document-oriented databases with a flexible schema that can handle schema changes over time.
Analytics. Use MapReduce, Hive, or Pig to perform analytical queries and scale-out systems that support high write loads.
Working with heterogenous types of data, for example, different media types at a generic level.
Embedded systems. They don’t want the overhead of SQL and servers, so they uses something simpler for storage.
A “market” game, where you own buildings in a town. You want the building list of someone to pop up quickly, so you partition on the owner column of the building table, so that the select is single-partitioned. But when someone buys the building of someone else you update the owner column along with price.
JPL is using SimpleDB to store rover plan attributes. References are kept to a full plan blob in S3.
Federal law enforcement agencies tracking Americans in real-time using credit cards, loyalty cards and travel reservations.
Fraud detection by comparing transactions to known patterns in real-time.
Helping diagnose the typology of tumors by integrating the history of every patient.
In-memory database for high update situations, like a web site that displays everyone’s “last active” time (for chat maybe). If users are performing some activity once every 30 sec, then you will be pretty much be at your limit with about 5000 simultaneous users.
Handling lower-frequency multi-partition queries using materialized views while continuing to process high-frequency streaming data.
Priority queues.
Running calculations on cached data, using a program friendly interface, without have to go through an ORM.
Unique a large dataset using simple key-value columns.
To keep querying fast, values can be rolled-up into different time slices.
Computing the intersection of two massive sets, where a join would be too slow.
A timeline ala Twitter.

Redis Use Cases
Redis is unique in the repertoire as it is a data structure server, with many fascinating use cases that people are excited to share.
Calculating whose friends are online using sets.
Memcached on steroids.
Distributed lock manager for process coordination.
Full text inverted index lookups.
Tag clouds.
Leaderboards. Sorted sets for maintaining high score tables.
Circular log buffers.
Database for university course availability information. If the set contains the course ID it has an open seat. Data is scraped and processed continuously and there are ~7200 courses.
Server for backed sessions. A random cookie value which is then associated with a larger chunk of serialized data on the server) are a very poor fit for relational databases. They are often created for every visitor, even those who stumble in from Google and then leave, never to return again. They then hang around for weeks taking up valuable database space. They are never queried by anything other than their primary key.
Fast, atomically incremented counters are a great fit for offering real-time statistics.
Polling the database every few seconds. Cheap in a key-value store. If you’re sharding your data you’ll need a central lookup service for quickly determining which shard is being used for a specific user’s data. A replicated Redis cluster is a great solution here - GitHub use exactly that to manage sharding their many repositories between different backend file servers.
Transient data. Any transient data used by your application is also a good fit for Redis. CSRF tokens (to prove a POST submission came from a form you served up, and not a form on a malicious third party site, need to be stored for a short while, as does handshake data for various security protocols.
Incredibly easy to set up and ridiculously fast (30,000 read or writes a second on a laptop with the default configuration)
Share state between processes. Run a long running batch job in one Python interpreter (say loading a few million lines of CSV in to a Redis key/value lookup table) and run another interpreter to play with the data that’s already been collected, even as the first process is streaming data in. You can quit and restart my interpreters without losing any data.
Create heat maps of the BNP’s membership list for the Guardian
Redis semantics map closely to Python native data types, you don’t have to think for more than a few seconds about how to represent data.
That’s a simple capped log implementation (similar to a MongoDB capped collection)—push items on to the tail of a ’log’ key and use ltrim to only retain the last X items. You could use this to keep track of what a system is doing right now without having to worry about storing ever increasing amounts of logging information.
An interesting example of an application built on Redis is Hurl, a tool for debugging HTTP requests built in 48 hours by Leah Culver and Chris Wanstrath.
It’s common to use MySQL as the backend for storing and retrieving what are essentially key/value pairs. I’ve seen this over-and-over when someone needs to maintain a bit of state, session data, counters, small lists, and so on. When MySQL isn’t able to keep up with the volume, we often turn to memcached as a write-thru cache. But there’s a bit of a mis-match at work here.
With sets, we can also keep track of ALL of the IDs that have been used for records in the system.
Quickly pick a random item from a set.
API limiting. This is a great fit for Redis as a rate limiting check needs to be made for every single API hit, which involves both reading and writing short-lived data.
A/B testing is another perfect task for Redis - it involves tracking user behaviour in real-time, making writes for every navigation action a user takes, storing short-lived persistent state and picking random items.
Implementing the inbox method with Redis is simple: each user gets a queue (a capped queue if you’re worried about memory running out) to work as their inbox and a set to keep track of the other users who are following them. Ashton Kutcher has over 5,000,000 followers on Twitter - at 100,000 writes a second it would take less than a minute to fan a message out to all of those inboxes.
Publish/subscribe is perfect for this broadcast updates (such as election results) to hundreds of thousands of simultaneously connected users. Blocking queue primitives mean message queues without polling.
Have workers periodically report their load average in to a sorted set.
Redistribute load. When you want to issue a job, grab the three least loaded workers from the sorted set and pick one of them at random (to avoid the thundering herd problem).
Multiple GIS indexes.
Recommendation engine based on relationships.
Web-of-things data flows.
Social graph representation.
Dynamic schemas so schemas don’t have to be designed up-front. Building the data model in code, on the fly by adding properties and relationships, dramatically simplifies code.
Reducing the impedance mismatch because the data model in the database can more closely match the data model in the application.

Links:

http: //highscalability.com/blog/2011/6/20/35-use-cases-for-choosing-your-next-nosql-database.html
http: //highscalability.com/blog/2010/12/6/what-the-heck-are-you-actually-using-nosql-for.html

Question 10

mongoDB: query language

Answer 10

Link:
https://docs.mongodb.com/manual/crud/

Question 11

mongoDB: data consistency

Answer 11

MongoDB Data Management
Auto-Sharding
MongoDB provides horizontal scale-out for databases on
low cost, commodity hardware or cloud infrastructure using
a technique called sharding, which is transparent to
applications. Sharding distributes data across multiple
physical partitions called shards. Sharding allows
MongoDB deployments to address the hardware
limitations of a single server, such as bottlenecks in RAM
or disk I/O, without adding complexity to the application.
MongoDB automatically balances the data in the sharded
cluster as the data grows or the size of the cluster
increases or decreases.
Unlike relational databases, sharding is automatic and built
into the database. Developers don’t face the complexity of
building sharding logic into their application code, which
then needs to be updated as shards are migrated.
Operations teams don’t need to deploy additional
clustering software to manage process and data
distribution.
Unlike other databases, multiple sharding policies are
available that enable developers and administrators to
distribute data across a cluster according to query patterns
or data locality. As a result, MongoDB delivers much higher
scalability across a diverse set of workloads:
• Range-based Sharding. Documents are partitioned
across shards according to the shard key value.
Documents with shard key values “close” to one another
are likely to be co-located on the same shard. This
approach is well suited for applications that need to
optimize rangebased queries.
• Hash-based Sharding. Documents are uniformly
distributed according to an MD5 hash of the shard key
value. Documents with shard key values “close” to one
another are unlikely to be co-located on the same
shard. This approach guarantees a uniform distribution
of writes across shards, but is less optimal for
range-based queries.
• Location-aware Sharding. Documents are partitioned
according to a user-specified configuration that
associates shard key ranges with specific shards and
hardware. Users can continuously refine the physical
location of documents for application requirements such
as locating data in specific data centers or on
multi-temperature storage (i.e. SSDs for the most
recent data, and HDDs for older data).
Tens of thousands of organizations use MongoDB to build
high-performance systems at scale. You can read more
about them on the MongoDB scaling page.

Query Router
Sharding is transparent to applications; whether there is
one or one hundred shards, the application code for
querying MongoDB is the same. Applications issue queries
to a query router that dispatches the query to the
appropriate shards.
For key-value queries that are based on the shard key, the
query router will dispatch the query to the shard that
manages the document with the requested key. When
using range-based sharding, queries that specify ranges on
the shard key are only dispatched to shards that contain
documents with values within the range. For queries that
don’t use the shard key, the query router will broadcast the
query to all shards and aggregate and sort the results as
appropriate. Multiple query routers can be used with a
MongoDB system, and the appropriate number is
determined based on performance and availability
requirements of the application.

Consistency & Durability
Transaction Model & Configurable Write
Availability
MongoDB is ACID compliant at the document level. One or
more fields may be written in a single operation, including
updates to multiple sub-documents and elements of an
array. The ACID guarantees provided by MongoDB ensures
complete isolation as a document is updated; any errors
cause the operation to roll back and clients receive a
consistent view of the document.
MongoDB also allows users to specify write availability in
the system using an option called the write concern. The
default write concern acknowledges writes from the
application, allowing the client to catch network exceptions
and duplicate key errors. Developers can use MongoDB’s
Write Concerns to configure operations to commit to the
application only after specific policies have been fulfilled -
for example only after the operation has been flushed to
the journal on disk. This is the same mode used by many
traditional relational databases to provide durability
guarantees. As a distributed system, MongoDB presents
additional flexibility in enabling users to achieve their
desired durability goals, such as writing to at least two
replicas in one data center and one replica in a second
data center. Each query can specify the appropriate write
concern, ranging from unacknowledged to
acknowledgement that writes have been committed to all
replicas.

Concurrency Control
MongoDB enforces concurrency control for multiple clients
accessing the database by coordinating multi-threaded
access to shared data structures and objects. The
granularity of concurrency control is dependent on the
storage engine configured for MongoDB. WiredTiger
enforces control at the document level while the MMAPv1
storage engine implements collection-level concurrency
control. For many applications, WiredTiger will provide
benefits in greater hardware utilization and more
predictable performance by supporting simultaneous write
access to multiple documents in a collection from multiple
sessions. Both storage engines support an unlimited
number of simultaneous readers on a document.
Review the documentation for more information on
concurrency control.

Journaling
MongoDB implements write-ahead journaling of operations
to enable fast crash recovery and durability in the storage
engine. In the case of a server crash, journal entries are
recovered automatically.
The behavior of the journal is dependent on the configured
storage engine:
• MMAPv1 journal commits are issued at least as often
as every 100ms by default. In addition to durability, the
journal also prevents corruption in the event of an
unclean system shutdown. By default, journaling is
enabled for MongoDB with MMAPv1. No production
deployment should run without the journal configured.
• The WiredTiger journal ensures that writes are persisted
to disk between checkpoints. WiredTiger uses
checkpoints to flush data to disk by default every 60
seconds or after 2GB of data has been written. Thus, by
default, WiredTiger can lose up to 60 seconds of writes
if running without journaling – though the risk of this
loss will typically be much less if using replication for
durability. The WiredTiger transaction log is not
necessary to keep the data files in a consistent state in
the event of an unclean shutdown, and so it is safe to
run without journaling enabled, though to ensure
availability the “replica safe” write concern should be
configured. An added feature of the WiredTiger storage
engine is the ability to compress the journal on disk,
reducing storage space.
For additional guarantees the administrator can configure
the journaled write concern for both storage engines,
whereby MongoDB acknowledges the write operation only
after committing the data to the journal.
Learn more about journaling from the documentation.

Availability
Replication
MongoDB maintains multiple copies of data called replica
sets using native replication. A replica set is a fully
self-healing shard that helps prevent database downtime.
Replica failover is fully automated, eliminating the need for
administrators to intervene manually.
A replica set consists of multiple replicas. At any given time
one member acts as the primary replica set member and
the other members act as secondary replica set members.
MongoDB is strongly consistent by default: reads and writes are issued to a primary copy of the data. If the
primary member fails for any reason (e.g., hardware failure,
network partition) one of the secondary members is
automatically elected to primary and begins to process all
writes.
The number of replicas in a MongoDB replica set is
configurable, and a larger number of replicas provides
increased data durability and protection against database
downtime (e.g., in case of multiple machine failures, rack
failures, data center failures, or network partitions). Up to
50 members can be provisioned per replica set.
To further increase durability, administrators can take
advantage of replica sets by configuring operations to write
to multiple replica members before returning to the
application – thereby providing functionality that is similar
to synchronous replication.
Applications can optionally read from secondary replicas,
where data is eventually consistent by default. Reads from
secondaries can be useful in scenarios where it is acceptable for data to be slightly out of date, such as some
reporting applications. Applications can also read from the
closest copy of the data as measured by ping distance
when geographic latency is more important than
consistency. For more on reading from secondaries see the
entry on Read Preference.
In addition to increased resilience and broader data
distribution, replica sets can also be configured with a
members performing specialized tasks:
• Hidden replica set members can be provisioned to
run applications such as analytics and reporting that
require isolation from regular operational workloads.
• Delayed replica set members can be deployed to
provide “historical” snapshots of data at different
intervals in time for use in recovery from certain errors,
such as “fat-finger” mistakes dropping databases or
collections.
Replica sets also provide operational flexibility by providing
a way to upgrade hardware and software without requiring
the database to go offline. This is an important feature as
these types of operations can account for as much as one
third of all downtime in traditional systems. For more on
replica sets, see the entry on Replication.

Question 12

mongoDB: joins in NoSQL DBs

Answer 12

One of the continuously debated items in context of NoSQL databases is the join operation. Let’s listen in a bit:

“joins suck”, “join within your application”, “lack of joins”: http://openmymind.net/2011/8/15/How-You-Should-Go-About-Learning-NoSQL/
“what’s missing … is a SQL-style join operation”: http://www.sarahmei.com/blog/2013/11/11/why-you-should-never-use-mongodb/
“doesn’t use SQL or JOINs, so it’s high-performance.”: http://www.mongodb-is-web-scale.com/ (on the lighter side)
and there can be many more variations found on the topic of joins on various levels of technical depth.

So, do we need joins in context of NoSQL databases? Do we do joins implemented by NoSQL databases? Are joins outdated concepts that we can live without in context of NoSQL databases? In this blog I try to rationalize the overarching question in principle. Some fact finding first:

(Database) Data Models and Database Management Systems
Data models, like the relational model, the document-model, the hierarchical model, key-value model, graph model, object-oriented model, XML model, etc., are implementations of data structures in a given database management system. Data models define possible data types and their construction rules for more complex types.

For example, the implementation of a relational model might restrict values in tables to be scalar. Another implementation might allow a table as a value, supporting NF2 relations. One system might support the document-model strictly following the JSON model, while others add additional data types in addition to what JSON defines. Some systems do support the notion of references, other so not. Each database implements a data model in any variation it likes to.

Schemata and Database Management Systems
A schema is a particular extension of a domain model, implemented in context of a data model. For example, a domain model might be suppliers, parts and their relationship. This can be implemented in a relational model, a document model or a graph model or any other supported data model.

There is no ‘best’ way of definition a schema. For the same domain, different schemata can be defined depending on the skill of the creator, the knowledge of query access patterns, the amount of restrictions that should be supervised by the database management system and other factors.

For example, in a document model, suppliers, parts and their relationships can be modeled as three separate documents, or in two documents (suppliers and their relationship to parts), or one document – and there are many more variations possible, of course.

Joins and Database Management Systems
Some database management systems implement the join operation in their query interface, some do not. For example, Oracle, MySQL and FoundationDB implement joins, MongoDB, Oracle NoSQL and Aerospike do not. So joins are not necessarily restricted to the relational data model.

Joins and Data Access Paths
With the fact finding under our belt, how many joins will you have to implement? In principle, this is a function of the required data access based on a specific schema. Different schemata of the same domain will require a different number of joins.

Let’s look at a few examples in the supplier – parts domain.

Example 1: No join required
The documents are structured like this:

{"supplier": "superQuality",
 "parts":[
     {"part_name": "part_lowQual"}, 
     {"part_name": "part_hiQual"}]
}
The query: “find the names of all parts for a supplier” does not require a join as the data is already structured so that each supplier contains the set of all parts it supplies.

Example 2: One join required
The documents are structured like this:

{“supplier”: “superQuality”,
“parts”: [1, 2]
}
{“part_name”: “part_lowQual”, “part_id”: 1}
{“part_name”: “part_hiQual”, “part_id”: 2}
The query: “find the identifiers and names of all parts for a supplier” requires a join as a supplier only has the identifiers of the parts it ships, not their names.

Example 3: Two joins required
The documents are structured like this:

{“supplier”: “superQuality”, “supplier_id”: “S_55”}
{“part_name”: “part_lowQual”, “part_id”: 1}
{“part_name”: “part_hiQual”, “part_id”: 2}
{“part_id”: 1, “supplier_id”: “S_55”}
The query: “find the identifiers and names of all parts for a supplier” requires two joins, one to find the objects for a supplier that relate the part identifier to the supplier identifier, and a second one to find the corresponding parts.

Analysis of Examples
The examples have shown empirically that the need for joins is not a function of the data model (document-oriented in this case), but a function of the data access, aka, the number of required data relationship traversals in context of a given schema. If the relationship to be traversed matches the way the data is structured as in Example 1, no join is necessary. As soon as the data is structured differently from the required traversal by the query, joins are necessary (Example 2 and 3).

So, as summary, it is fairly easy to avoid joins. If, and only if, you can structure your data (aka, build your schema) in such a way that it conforms structurally to the queries then you can avoid joins completely (Example 1). I am certain that there are special cases out there for which you can accomplish that, but in general, this is not possible. And, even if it is possible in production, as soon as analysts start analyzing the data sets, they will most likely query along different access paths.

Joins at Query Time vs. Joins at Insert/Update/Delete Time
Above examples clarified that joins are a function of the data access paths. Can joins at query time be avoided entirely by creating data access paths in a certain way?

Yes, it is possible, however, it is a basic trade-off between data query and data manipulation time: reducing the computational effort at run-time, and instead increasing it during insert / update / delete operations. In principle, joins at query time can be avoided if for each access path there is an equivalent data structure in place.

Example 4: Schema refactoring
The documents in this example look like:

{“supplier”: “superQuality”, “supplier_id”: “S_55”}
{“part_name”: “part_lowQual”, “part_id”: 1}
{“part_name”: “part_hiQual”, “part_id”: 2}
{“part_id”: 1, “supplier_id”: “S_55”}
{“shipper”: “fastShipper”, “shipper_id”: “SH_01”}
{“part_id”: 2, “shipper_id”: “SH_01”}
Supplier supply parts, however, shippers ship not any part, but only specific parts (maybe for safety reasons). There can be several queries against this document set:

Find all parts supplied by a supplier with a given name
Find all parts shipped by a shipper with a given name
Find all suppliers and shippers for a part with a given name
Each of these queries requires at least one join. The documents can be restructured easily to avoid joins altogether:

{“supplier”: “superQuality”, “supplier_id”: “S_55”,
“parts”: [
{“part_name”: “part_lowQual”, “part_id”: 1}
]}
{“shipper”: “fastShipper”, “shipper_id”: “SH_01”,
“parts”: [
{“part_name”: “part_hiQual”, “part_id”: 2}
]}
{“part_name”: “part_lowQual”, “part_id”: 1,
“suppliers”: [
{“supplier”: “superQuality”, “supplier_id”: “S_55”}
],
“shippers”: []}
{“part_name”: “part_hiQual”, “part_id”: 2,
“suppliers”: [],
“shippers”: [
{“shipper”: “fastShipper”, “shipper_id”: “SH_01”}
]}
The idea is clear: structure the data in such a way that a query can be satisfied with a simple selection. And, the consequence is clear, too: data is duplicated, possibly many times. Which means that an insert, update or delete has to know all the locations where to modify the data and has to modify the data consistently (and ideally within a single transaction).

As a side note, this is the situation that normalization tries to address by ensuring that each data item is only once in the database.

Of course, data duplication will have an impact on the size requirements of main memory an disk space. While there is a change in algorithm complexity, there is also a change in the storage and memory size requirements.

Pre-Joining Data
Pre-joining data allows to avoid joins at query time at the cost of duplicating data at data management time. Alternatively expressed, the implementation of duplication at management time is the cost of avoiding normalization combined with query-time joins.

Is there a way to quantify the effort? In principle, there are as many duplications necessary as joins are to be avoided. This is a rough estimate as many joins are the same except for selection and/or projection specifications. If all joins are abstracted to their join criteria (omitting projection and selection), then this is roughly the amount of duplication required.

The article written by Sarah Mei clearly shows the trade-off between data duplication and joins: http://www.sarahmei.com/blog/2013/11/11/why-you-should-never-use-mongodb/. She clearly describes many of the issues in context of a specific use case.

“Wait a minute, I don’t have joins and it works anyway!”
But, where are the joins? NoSQL databases that do not implement the join operator in their query interface are in use and production.

If not expressed as query, joins are found either in the application system logic or the interface logic, depending on the design. Most likely these are nested-loop joins or hash-based joins (less likely) or a series of selections with the application logic combining the intermediary query results into the final result data set.

And they are not joins on the complete data set either, but usually have some selection criteria. So the application system logic roughly corresponds to the optimized operator tree of a database query sub-system and in all actuality there might be many joins implemented that way throughout the application logic.

The joins are in fact implemented, just not by using a join operator on the database interface, but inside the application logic. This means that the database cannot optimize the execution, plus there are several queries coming from the application logic putting load on the database system.

And this opens up yet another trade-off: data duplication vs. application logic complexity. If the data is structured in such a way that joins are avoided (at the cost of duplication), then the application logic complexity will be reduced also (from algorithms implementing joins to algorithms issuing queries with selections/projections).

Of course, while the application logic complexity is reduced, the data management logic complexity increased as it has to manage duplicate data consistently across the database.

Summary: Are joins required? Yes. Are joins implemented? Yes.
In my mind there is no question that joins are in general needed and actually implemented today, even if the database does not support a join operator directly and even if there are opinions that joins are not needed. I don’t really understand why there is a discussion about this in the first place as the need for a join is a function of the data schema, not the data model.

The fact that a relational database has the capability of joins does not mean you must use it. And the fact that a NoSQL database does not support joins at their query interface does not mean joins are not needed.

At the heart an architecture and engineering decision has to be made (implicitly or explicitly) of how many joins are implemented through data duplication and how many joins are implemented through algorithms in the application logic layer (if there is not join operator available at the database query interface).

It’s that easy.

Link:
https://realprogrammer.wordpress.com/2014/04/30/document-oriented-nosql-databases-how-many-joins-will-you-have-to-implement/

Question 13

mongoDB: logical splitting data between documents

Answer 13

In the previous chapter, you learned how to install MongoDB on two commonly used
platforms (Windows and Linux), as well as how to extend the database with some
additional drivers. In this chapter, you will shift your attention from the operating system
and instead examine the general design of a MongoDB database. Specifically, you’ll learn
what collections are, what documents look like, how indexes work and what they do, and
finally, when and where to reference data instead of embedding it. We touched on some
of these concepts briefly in Chapter 1, but in this chapter, we’ll explore them in more
detail. Throughout this chapter, you will see code examples designed to give you a good
feeling for the concepts being discussed. Do not worry too much about the commands
you’ll be looking at, however, because they will be discussed extensively in Chapter 4.
Designing the Database
As you learned in the first two chapters, a MongoDB database is nonrelational and
schemaless. This means that a MongoDB database isn’t bound to any predefined
columns or datatypes as relational databases are (such as MySQL). The biggest benefit
of this implementation is that working with data is extremely flexible because there is no
predefined structure required in your documents.
To put it more simply: you are perfectly capable of having one collection that
contains hundreds or even thousands of documents that all carry a different structure—
without breaking any of the MongoDB databases rules.
One of the benefits of this flexible schemaless design is that you won’t be restricted
when programming in a dynamically typed language such as Python or PHP. Indeed,
it would be a severe limitation if your extremely flexible and dynamically capable
programming language couldn’t be used to its full potential because of the innate
limitations of your database.
Let’s take another glance at what the data design of a document in MongoDB looks
like, paying particular attention to how flexible data in MongoDB is compared to data in
a relational database. In MongoDB, a document is an item that contains the actual data, comparable to a row in SQL.
As you might have noticed when looking at this pair of documents, most of the fields
aren’t closely related to one another. Yes, they both have fields called Title and Type; but
apart from that similarity, the documents are completely different. Nevertheless, these
two documents are contained in a single collection called Media.
MongoDB is called a schemaless database, but that doesn’t mean MongoDB’s data
structure is completely devoid of schema. For example, you do define collections and
indexes in MongoDB (you will learn more about this later in the chapter). Nevertheless,
you do not need to predefine a structure for any of the documents you will be adding, as is
the case when working with MySQL, for example.
Simply stated, MongoDB is an extraordinarily dynamic database; the preceding
example would never work in a relational database, unless you also added each possible
field to your table. Doing so would be a waste of both space and performance, not to
mention highly disorganized.

Using Documents
Recall that a document consists of key-value pairs. For example, the pair “type” : “Book”
consists of a key named type, and its value, Book. Keys are written as strings, but the
values in them can vary tremendously. Values can be any of a rich set of datatypes,
such as arrays or even binary data. Remember: MongoDB stores its data in BSON format
(see Chapter 1 for more information on this topic).
Next, let’s look at all of the possible types of data you can add to a document, and
what you use them for:
• String: This commonly used datatype contains a string of text
(or any other kind of characters). This datatype is used mostly for
storing text values (for example, “Country” : “Japan”}.
• Integer (32b and 64b): This type is used to store a numerical value
(for example, { “Rank” : 1 } ). Note that there are no quotes
placed before or after the integer.
• Boolean: This datatype can be set to either TRUE or FALSE.
• Double: This datatype is used to store floating-point values.
• Min / Max keys: This datatype is used to compare a value against
the lowest and highest BSON elements, respectively.
• Arrays: This datatype is used to store arrays (for example,
[“Membrey, Peter”,”Plugge, Eelco”,”Hows, David”]).
• Timestamp: This datatype is used to store a timestamp. This can
be handy for recording when a document has been modified or
added.
• Object: This datatype is used for embedded documents.
• Null: This datatype is used for a Null value.
• Symbol: This datatype is used identically to a string; however, it’s
generally reserved for languages that use a specific symbol type.
• Date *: This datatype is used to store the current date or time in
Unix time format (POSIX time).
• Object ID *: This datatype is used to store the document’s ID.
• Binary data *: This datatype is used to store binary data.
• Regular expression *: This datatype is used for regular expressions.
All options are represented by specific characters provided in
alphabetical order. You will learn more about regular expressions
in Chapter 4.
• JavaScript Code *: This datatype is used for JavaScript code.
The asterisks mean that the last five datatypes (date, object ID, binary data, regex,
and JavaScript code) are non-JSON types; specifically, they are special datatypes that
BSON allows you to use. In Chapter 4, you will learn how to identify your datatypes by
using the $type operator.
In theory, this all probably sounds straightforward. However, you might wonder how
you go about actually designing the document, including what information to put in it.
Because a document can contain any type of data, you might think there is no need to
reference information from inside another document. In the next section, we’ll look at
the pros and cons of embedding information in a document compared to referencing that
information from another document.

Embedding vs. Referencing Information in Documents
You can choose either to embed information into a document or reference that
information from another document. Embedding information simply means that
you place a certain type of data (for example, an array containing more data) into the
document itself. Referencing information means that you create a reference to another
document that contains that specific data. Typically, you reference information when you
use a relational database. For example, assume you wanted to use a relational database
to keep track of your CDs, DVDs, and books. In this database, you might have one table
for your CD collection and another table that stores the track lists of your CDs. Thus, you
would probably need to query multiple tables to acquire a list of tracks from a specific CD.
With MongoDB (and other nonrelational databases), however, it would be much
easier to embed such information instead. After all, the documents are natively capable
of doing so. Adopting this approach keeps your database nice and tidy, ensures that all
related information is kept in one single document, and even works much faster because
the data is then co-located on the disk.