Базы данных Лекция 12 Пример общей организации СУБД. Физическое представление реляционных баз данных во внешней памяти. Индексные структуры 1

Базы данных Введение Лекция 12 В 1975–1979 г.г. в исследовательской лаборатории компании IBM разрабатывалась система управления реляционными базами данных System R. Именно System R практически доказала жизнеспособность реляционного подхода к управлению базами данных. Практически во всех более поздних реляционных СУБД в той или иной степени используются методы, примененные в System R. 2

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

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

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 При выполнении проекта System R преследовались следующие основные цели: обеспечить ненавигационный интерфейс высокого уровня пользователя с системой; обеспечить многообразие допустимых способов использования СУБД; поддерживать динамически изменяемую среду баз данных, в которой таблицы, индексы, представления, транзакции и другие объекты могут легко добавляться и уничтожаться без приостановки нормального функционирования системы; обеспечить возможность параллельной работы с одной базой данных многих пользователей; обеспечить средства восстановления согласованного состояния баз данных после разного рода сбоев аппаратуры или программного обеспечения; ограничивать доступ пользователей к базе данных по выборке и модификации на основе механизма авторизации. 5

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 Основой System R является «реляционный» язык SEQUEL (который достаточно быстро был переименован в SQL). Иногда его называют языком запросов или языком манипулирования данными, но на самом деле возможности SQL гораздо шире: SQL включает средства динамической компиляции запросов, на основе чего возможно построение диалоговых систем обработки запросов. Допускается динамическая параметризация статически откомпилированных запросов, в результате чего возможно построение эффективных диалоговых систем со стандартными наборами запросов. Средствами SQL определяются все доступные пользователю объекты баз данных: таблицы, индексы, представления. Имеются средства уничтожения любого такого объекта. Соответствующие операторы языка могут выполняться в любой момент, и возможность выполнения операции данным пользователем зависит от ранее предоставленных ему прав. 6

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 В System R под целостным состоянием базы данных понимается состояние, удовлетворяющее набору сохраняемых при базе данных предикатов целостности. Эти предикаты, называемые в System R утверждениями целостности (assertion), также задаются средствами языка SQL. Любой оператор языка выполняется в границах некоторой транзакции последовательности операторов языка, неделимой в смысле состояния базы данных. Неделимость означает, что все изменения базы данных, произведенные в пределах одной транзакции, либо целиком отображаются в состоянии базы данных, либо полностью в нем отсутствуют. Последняя возможность возникает при откате транзакции, который может произойти по инициативе пользователя (при выполнении соответствующего оператора SQL) или по инициативе системы. 7

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 Язык SQL System R содержит средство установки так называемых точек сохранения (savepoint). При инициируемом пользователем откате транзакции можно указать номер точки сохранения, выше которого откат не распространяется. Инициируемый системой откат транзакции производится до ближайшей точки сохранения, в которой условие, вызвавшее откат, уже отсутствует. Естественно, что для реального выполнения отката транзакции необходимо запоминать некоторую информацию о выполнении транзакции. В System R для этих и других целей используется специальный набор данных журнал, в который помещаются записи обо всех операциях всех транзакций, изменяющих состояние базы данных. При откате транзакции происходит процесс обратного выполнения транзакции (undo), в ходе которого в обратном порядке выполняются все изменения, запомненные в журнале. 8

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 В языке SQL System R имеется средство определения так называемых триггеров (trigger), позволяющих автоматически поддерживать целостность базы данных при модификациях её объектов. В SQL System R триггер это каталогизированная операция модификации, для которой задано условие её автоматического выполнения. Язык SQL содержит средства определения представлений. Представление это каталогизированный именованный запрос на выборку данных. Поскольку SQL это «реляционный» язык, результатом выполнения любого запроса на выборку является таблица, и поэтому концептуально можно относиться к любому представлению как к таблице. В языке допускается использование ранее определенных представлений практически везде, где допускается использование таблиц (с некоторыми ограничениями по поводу возможностей модификации через представления). 9

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 Авторизация доступа к базе данных также основана на средствах SQL. При создании любого объекта базы данных пользователь, выполняющий эту операцию, становится полновластным владельцем этого объекта, т. е. может выполнять по отношению к этому объекту любую допустимую операцию SQL. Далее этот пользователь может выполнить оператор SQL, означающий передачу всех его прав на этот объект (или их подмножества) любому другому пользователю. В частности, этому пользователю может быть передано право на передачу всех переданных ему прав (или их части) третьему пользователю и т. д. Одним из прав пользователя по отношению к объекту является право на изъятие у других пользователей всех или некоторых прав, которые ранее им были переданы. Эта операция распространяется транзитивно на всех дальнейших наследников этих прав. 10

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 По части обеспечения параллельной работы многих пользователей с одной базой данных, основной подход System R состоит в том, что пользователь не обязан знать о наличии других пользователей, конкурирующих с ним за доступ к базе данных, т. е. система ответственна за обеспечение изолированности пользователей с гарантией отсутствия их взаимного влияния в пределах транзакций. Из этого следует в интерфейсе пользователя с системой (т. е. в языке SQL) не должно быть средств регулирования взаимодействий с другими пользователями; система должна обеспечить автоматическую сериализацию набора транзакций, т. е. обеспечить режим выполнения этого набора транзакций, эквивалентный по конечному результату некоторому последовательному выполнению этих транзакций. Эта проблема решается в System R за счёт автоматического выполнения синхронизационных блокировок всех изменяемых объектов базы данных. 11

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 Одним из основных требований к СУБД вообще и к System R в частности является обеспечение надежности баз данных по отношению к различного рода сбоям. К таким сбоям могут относиться: программные ошибки прикладного и системного уровня сбои процессора поломки внешних носителей и т. д. Восстановление происходит путем обратного выполнения транзакции на основе информации о внесенных ею изменениях, запомненной в журнале. 12

Базы данных Цели System R и их связь с общей организацией системы Лекция 12 Основными структурными компонентами System R являются: система управления реляционными данными (Relational Data System RDS), состоящая, по существу, из компилятора языка SQL и подсистемы поддержки откомпилированных операторов; система управления реляционной памятью (Relational Storage System RSS). RSS обеспечивает интерфейс довольно низкого, но достаточного для реализации SQL уровня для доступа к хранимым в базе данным. Синхронизация транзакций, журнализация изменений и восстановление баз данных после сбоев также относятся к числу функций RSS. Таким образом, система естественно разделяется на два уровня уровень управления памятью и синхронизацией, фактически, не зависящий от базового языка запросов системы, и языковый уровень (уровень SQL), на котором решается большинство проблем System R. 13

Базы данных Организация внешней памяти в базах данных System R Лекция 12 база данных System R располагается в одном или нескольких сегментах внешней памяти. Каждый сегмент состоит из страниц данных и страниц индексной информации. Размер страницы данных в сегменте может быть выбран равным либо 4, либо 32 килобайтам; размер страницы индексной информации равен 512 байтам. Кроме того, при работе RSS поддерживается дополнительный набор данных для ведения журнала. Для повышения надежности журнала (а это наиболее критичная информация; при её потере восстановление базы данных после сбоев невозможно) этот набор данных дублируется на двух внешних носителях. 14

Базы данных Страницы данных и идентификаторы кортежей Лекция 12 В каждой странице данных хранятся кортежи одной или нескольких таблиц. Фундаментальным понятием RSS является идентификатор кортежа (tuple identifier tid). Гарантируется неизменяемость tid'а во все время существования кортежа в базе данных независимо от перемещений кортежа внутри страницы и даже при перемещении кортежа в другую страницу. Потребность в перемещении кортежей возникает по той причине, что кортеж, занесенный в некоторую таблицу базы данных, вообще говоря, во время своего существования может увеличиваться в размерах (если к этой таблице добавляется новое поле, или если в ней имеется хотя бы одно поле, типом данных которого являются строки символов переменного размера). 15

Базы данных Страницы данных и идентификаторы кортежей Лекция 12 Реально tid представляет собой пару. При этом кортеж может реально располагаться в данной странице или в другой странице. 16

Базы данных Страницы данных и идентификаторы кортежей Лекция 12 В каждой странице данных имеются две области: область хранения описателей кортежей; область хранения самих кортежей. Обе эти области являются динамическими, т. е. в странице данных заранее не резервируется место под описатели кортежей. Легко видеть, что выделение фиксированной части страницы данных под описатели кортежей (вмещающей, скажем, k описателей) потенциально привело бы к потери памяти в этой странице, поскольку при размещении в ней k кортежей очень маленького размера пропадало бы место в области хранения кортежей, а при размещении p

Базы данных Страницы данных и идентификаторы кортежей Лекция 12 Второй вариант хранения кортежей возникает в том случае, когда некоторый кортеж после своего создания был размещен системой в странице с номером N, а после обновления с увеличением размера перестал помещаться в этой странице, и система была вынуждена разместить его в странице с номером M. Тогда исходный tid этого кортежа не изменится, но его описатель в странице N будет содержать не координаты кортежа в данной странице, а новый tid, указывающий на реальное положение кортежа в странице M. Легко видеть, что применение такого подхода позволяет ограничиться максимум одним уровнем косвенности (если данный кортеж в какой-то момент времени перестанет помещаться в странице M, и система переместит его в страницу P, то достаточно будет изменить косвенную ссылку на этот кортеж в странице N, и его исходный tid не изменится). 18

Базы данных Страницы данных и идентификаторы кортежей Лекция 12 Поскольку допускается нахождение в одной странице данных кортежей разных таблиц, каждый кортеж должен, кроме содержательной части, включать служебную информацию, идентифицирующую таблицу, которой принадлежит данный кортеж. Кроме того, в System R допускается динамическое добавление полей к существующим таблицам. При этом реально происходит лишь модификация описателя таблицы в таблице-каталоге таблиц. В существующем кортеже таблицы новое поле возникает только при модификации этого кортежа, затрагивающей новое поле. Это позволяет избежать массовой перестройки хранимой таблицы при добавлении к ней новых полей, но, естественно, требует хранения при кортеже дополнительной служебной информации, определяющей реальное число полей в данном кортеже. 19

Базы данных Индексы и кластеризация таблиц Лекция 12 На основе наличия уникальных, обеспечивающих почти прямой доступ к кортежам и не изменяемых во время существования кортежей tid'ов в System R поддерживаются дополнительные управляющие структуры индексы. Каждый индекс определяется на одном или нескольких полях таблицы, значения которых составляют его ключ, и позволяет производить прямой поиск по ключу кортежей (их tid'ов) и последовательное сканирование таблицы по индексу, начиная с указанного ключа, в порядке возрастания или убывания значений ключа. Некоторые индексы при их создании могут обладать атрибутом уникальности. В таком индексе не допускаются дубликаты ключа. Это единственное средство SQL System R указания системе первичного ключа таблицы. 20

Базы данных Индексы и кластеризация таблиц Лекция 12 Для организации индексов в System R применяется техника B+-деревьев. Каждый индекс занимает отдельный набор страниц, номер корневой страницы запоминается в описателе индекса. Использование B+-деревьев позволяет достичь эффективности при прямом поиске, поскольку они из-за своей сильной ветвистости обладают небольшой глубиной. Кроме того, B+-деревья сохраняют порядок ключей в листовых блоках иерархии, что позволяет производить последовательное сканирование таблицы в порядке возрастания или убывания значений полей, на которых определен индекс. Фундаментальное свойство B+-деревьев автоматическая балансировка дерева допускает произведение лишь локальных модификаций индекса при переполнениях и опустошениях страниц индекса. 21

Базы данных Индексы и кластеризация таблиц Лекция 12 Наиболее важной особенностью физической организации баз данных в System R является возможность обеспечения кластеризации связанных кортежей одной или нескольких таблиц. Под кластеризацией кортежей понимается физически близкое расположение (в пределах одной страницы данных) логически связанных кортежей. Обеспечение соответствующей кластеризации позволяет добиться высокой эффективности системы при выполнении некоторого класса запросов. В окончательном варианте System R существует только одно средство определения условий кластеризации таблицы объявить до заполнения таблицы один (и только один) индекс, определенный на полях этой таблицы, кластеризованным. Тогда, если заполнение таблицы кортежами производится в порядке возрастания или убывания значений полей кластеризации (в зависимости от атрибутики индекса), система физически располагает кортежи в страницах данных в том же порядке. 22

Базы данных Индексы и кластеризация таблиц Лекция 12 В каждой странице данных кластеризованной таблицы оставляется некоторое резервное свободное пространство. При последующих вставках кортежей в такую таблицу система стремится поместить каждый кортеж в одну из страниц данных, в которых уже находятся кортежи этой таблицы с такими же (или близкими) значениями полей кластеризации. Очевидным преимуществом кластеризации таблицы является то, что при последовательном сканировании кластеризованной таблицы с использованием кластеризованного индекса потребуется ровно столько чтений страниц данных из внешней памяти, сколько страниц занимают кортежи этой таблицы. Следовательно, при правильно выбранных критериях кластеризации запросы, связанные с заданием условий на полях кластеризации можно выполнить почти оптимально. 23

Базы данных Индексы и кластеризация таблиц Лекция 12 В ранних версиях System R существовал еще один способ физического доступа к кортежам таблицы и, соответственно, еще один способ указания условия кластеризации с использованием так называемых связей (links). На уровне физического представления связь это физическая ссылка (tid) из одного кортежа на другой (не обязательно одной таблицы). В языке SEQUEL (до того момента, когда его стали называть SQL) существовали средства определения связей в иерархической манере: можно было объявить некоторую таблицу родительской по отношению к той же или другой таблице-потомку. При этом указывались поля родительской таблицы и таблицы-потомка, в соответствии со значениями которых образовывалась иерархия. Правила построения были очень простыми проводились связи от кортежа родительской таблицы ко всем кортежам таблицы-потомка с теми же значениями полей связывания. На самом деле, все кортежи таблицы-потомка с общим значением полей связывания образовывали кольцевой список, на который проводилась одна связь из соответствующего кортежа родительской таблицы. 24

Базы данных Списки Лекция 12 Кроме таблиц и индексов при работе System R во внешней памяти могут располагаться еще и временные объекты списки (list). Список это временная структура данных, создаваемая с целью оптимизации выполнения SQL-запроса, содержащая некоторые кортежи хранимой таблицы базы данных, не имеющая имени и, следовательно, не видимая на уровне интерфейса SQL. Кортежи списка могут быть упорядочены по возрастанию или убыванию полей соответствующей таблицы. Средства работы со списками имеются в интерфейсе RSS, но их, естественно, нет в SQL. Соответственно, эти средства используются только внутри системы при выполнении запросов. 25

Базы данных Интерфейс RSS Лекция 12 На уровне RSS отсутствует именование объектов базы данных, употребляемое на уровне SQL. Вместо имен объектов используются их уникальные идентификаторы, являющиеся прямыми или косвенными адресами внутренних описателей объектов во внешней памяти для постоянных объектов или в основной памяти для временных объектов. Замена имен объектов базы данных на их идентификаторы производится компилятором SQL на основе информации, черпаемой им из системных таблиц-каталогов. 26

Базы данных Интерфейс RSS Лекция 12 Можно выделить следующие группы операций: операции сканирования таблиц и списков; операции создания и уничтожения постоянных и временных объектов базы данных; операции модификации таблиц и списков; операция добавления поля к таблице; операции управления прохождением транзакций; операция явной синхронизации. 27

Базы данных Операции сканирования таблиц и списков Лекция 12 Операции группы сканирования позволяют последовательно, в порядке, определяемом типом сканирования, прочитать кортежи таблицы или списка, удовлетворяющие требуемым условиям. Группа включает операции OPEN, NEXT и CLOSE, означающие, соответственно, начало сканирования, требование чтения следующего кортежа, удовлетворяющего условиям, и конец сканирования. Для таблицы возможны два режима сканирования: прямое сканирование и сканирование через индекс. При прямом сканировании единственным параметром операции OPEN является идентификатор таблицы. При начале сканирования таблицы через индекс в число параметров операции OPEN входит идентификатор какого-либо индекса, определенного ранее на полях этой таблицы. Кроме того, можно указать диапазон сканирования в терминах значений поля (полей), составляющего ключ индекса. 28

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

Базы данных Операции сканирования таблиц и списков Лекция 12 Операция NEXT выполняет чтение следующего кортежа указанного сканирования, удовлетворяющего условию данной операции. Условие представляет собой дизъюнктивную нормальную форму простых условий, накладываемых на значения указанных полей таблицы. Простое условие это условие вида номер-поля op константа, где op операция сравнения, >=, = или !=. Общее условие является параметром операции NEXT. Семантика операции NEXT следующая: начиная с текущей позиции сканирования выбираются кортежи таблицы в порядке, определяемом типом сканирования, до тех пор, пока не встретится кортеж, значения полей которого удовлетворяют указанному условию. Этот кортеж и является результатом операции. 30

Базы данных Операции сканирования таблиц и списков Лекция 12 Операция CLOSE может быть выполнена в данной транзакции по отношению к любому ранее открытому сканированию независимо от его состояния (т. е. независимо от того, достигнута ли при сканировании правая граница диапазона сканирования). Параметром операции является идентификатор сканирования, и её выполнение приводит к тому, что этот идентификатор становится недействительным (и, соответственно, уничтожаются служебные структуры памяти RSS, относящиеся к данному сканированию). 31

Базы данных Операции создания и уничтожения постоянных и временных объектов базы данных Лекция 12 Группа операций создания и уничтожения постоянных и временных объектов базы данных включает операции создания таблиц ( CREATE TABLE ), списков ( CREATE LIST ), индексов ( CREATE IMAGE ) и уничтожения любого из подобных объектов ( DROP TABLE, DROP LIST и DROP IMAGE ). Входным параметром операций создания таблиц и списков является спецификатор структуры объекта, т. е. число полей объекта и спецификаторы их типов. Кроме того, при спецификации полей таблицы указывается разрешение или запрещение наличия неопределенных значений полей в кортежах этой таблицы или списка. Неопределенные значения кодируются специальным образом. Любая операция сравнения константы данного типа с неопределенным значением по определению вырабатывает значение false, кроме операции сравнения на совпадение со специальной литеральной константой NULL. 32

Базы данных Операции создания и уничтожения постоянных и временных объектов базы данных Лекция 12 В результате выполнения этих операций заводится описатель в служебной таблице описателей таблиц или основной памяти (в зависимости от того, создается ли постоянный объект или временный), и вырабатывается идентификатор объекта, который служит входным параметром других операций, относящихся к соответствующему объекту (в частности, параметром операции OPEN при открытии сканирования объекта). Входными параметрами операции CREATE IMAGE являются идентификатор таблицы, для которой создается индекс, список номеров полей, значения которых составляют ключ индекса, и признаки упорядочения по возрастанию или убыванию для всех полей, составляющих ключ. Кроме того, может быть указан признак уникальности индекса, т. е. запрещения наличия в данном индексе ключей-дубликатов. 33

Базы данных Операции создания и уничтожения постоянных и временных объектов базы данных Лекция 12 Операции DROP TABLE, DROP LIST и DROP IMAGE могут быть выполнены в любой момент независимо от состояния объектов. Выполнение операции приводит к уничтожению соответствующего объекта и, вследствие этого, недействительности его идентификатора. Массовые операции над постоянными объектами ( CREATE IMAGE и DROP TABLE ) требуют дополнительных накладных расходов в связи с необходимостью обеспечения возможности откатов транзакции, для чего требуется выполнение массовых обратных действий. 34

Базы данных Операции модификации таблиц и списков Лекция 12 Группа операций модификации таблиц и списков включает операции вставки кортежа в таблицу или список ( INSERT ), удаления кортежа из таблицы ( DELETE ) и обновления кортежа в таблице ( UPDATE ). Параметрами операции вставки кортежа являются идентификатор таблицы или списка и набор значений полей кортежа. Среди значений полей могут быть литеральные неопределенные значения NULL. При занесении кортежа в таблицу производится коррекция всех индексов, определенных на этой таблице. Реально это выражается во вставке новой записи во все B-деревья индексов. В результате успешного выполнения операции вставки кортежа в таблицу вырабатывается идентификатор нового кортежа, который выдается в качестве результата операции и может быть в дальнейшем использован как прямой параметр операций удаления и модификации кортежей таблицы. При занесении кортежа в список значение идентификатора кортежа не вырабатывается. 35

Базы данных Операции модификации таблиц и списков Лекция 12 Операции удаления и модификации кортежей допускаются только для кортежей таблиц. Естественно, что для выполнения этих операций необходимо идентифицировать соответствующий кортеж. В интерфейсе RSS допускаются два способа такой идентификации: с помощью идентификатора кортежа (явная адресация) ; с использованием идентификатора открытого к этому времени сканирования. Единственным параметром операции DELETE является идентификатор кортежа или идентификатор сканирования. Параметры операции UPDATE включают, кроме этого, спецификацию изменяемых полей кортежа. При выполнении операции DELETE производится коррекция всех индексов, определенных на данной таблице. Операция UPDATE также может повлечь коррекцию индексов, если затрагивает поля, входящие в состав их ключей. 36

Базы данных Операции модификации таблиц и списков Лекция 12 Кроме «атомарных» операций сканирования и модификации таблиц и списков, интерфейс RSS включает одну «макрооперацию» BUILDLIST, позволяющую за одно обращение к RSS построить список, отсортированный в соответствии со значениями заданных полей. Эта операция включает сканирование заданной таблицы или списка, создание нового списка, в который включаются указанные поля выбираемых кортежей, и сортировку построенного списка в соответствии со значениями указанных полей. Идентификатор заново построенного отсортированного списка является ответным параметром операции. Параметрами операции BUILDLIST являются набор параметров для открытия сканирования, список номеров полей, составляющих кортежи нового списка, и список номеров полей, по которым нужно производить сортировку. Отдельным параметром является признак, в соответствии со значением которого в новом списке допускаются или не допускаются кортежи-дубликаты. 37

Базы данных Операция добавления поля к существующей таблице Лекция 12 Операция RSS добавления поля к существующей таблице позволяет в динамике изменять схему таблицы. Параметрами операции CHANGE являются идентификатор существующей таблицы и спецификация нового поля (его тип). При выполнении операции изменяется только описатель данной таблицы в служебной таблице описателей таблиц. До выполнения первой операции UPDATE, затрагивающей новое поле таблицы, реально ни в одном кортеже таблицы память под новое поле выделяться не будет. По умолчанию значения нового поля во всех кортежах таблицы, в которые ещё не производилось явное занесение значения, считаются неопределенными. Тем самым, ни для одного поля, динамически добавленного к существующей таблице, не может быть запрещено хранение неопределенных значений. 38

Базы данных Операции управления прохождением транзакций Лекция 12 Каждая операция RSS выполняется в пределах некоторой транзакции. Интерфейс RSS включает набор операций управления прохождением транзакции: начать транзакцию ( BEGIN TRANSACTION ); закончить транзакцию ( END TRANSACTION ); установить точку сохранения ( SAVE ) ; выполнить откат до указанной точки сохранения или до начала транзакции ( RESTORE ). При вызове любой операции функции RSS, кроме BEGIN TRANSACTION, должен указываться еще один параметр идентификатор транзакции. Этот идентификатор и вырабатывается при выполнении операции BEGIN TRANSACTION, которая сама входных параметров не требует. В любой точке транзакции до выполнения операции END TRANSACTION может быть выполнен откат данной транзакции, т. е. обратное выполнение всех изменений, произведенных в данной транзакции, и восстановление состояния позиций сканирования. 39

Базы данных Операции управления прохождением транзакций Лекция 12 Точка сохранения устанавливается с помощью операции SAVE. При выполнении этой операции запоминаются состояние сканов данной транзакции, открытых к моменту выполнения SAVE, и координаты последней записи об изменениях в базе данных в журнале, произведенной от имени данной транзакции. Ответным параметром операции SAVE является идентификатор точки сохранения. Этот идентификатор в дальнейшем может быть использован как аргумент операции RESTORE, при выполнении которой производится восстановление базы данных по журналу до того состояния, в котором находилась база данных к моменту установки указанной точки сохранения. Кроме того, по локальной информации в оперативной памяти, привязанной к транзакции, восстанавливается состояние её сканов. Откат к началу транзакции инициируется также вызовом операции RESTORE, но с указанием некоторого предопределенного идентификатора точки сохранения. 40

Базы данных Операции управления прохождением транзакций Лекция 12 При выполнении своих транзакций пользователи System R изолированы один от другого, т. е. не ощущают того, что система функционирует в многопользовательском режиме. Это достигается за счёт наличия в RSS механизма неявной синхронизации. До конца транзакции никакие изменения базы данных, произведенные в пределах этой транзакции, не могут быть использованы в других транзакциях. При выполнении операции END TRANSACTION происходит «фиксация» изменений, произведенных в данной транзакции, т. е. они становятся видимыми в других транзакциях. Реально это означает снятие синхронизационных блокировок с объектов базы данных, изменявшихся в транзакции. Из этого следует, что после выполнения END TRANSACTION невозможны индивидуальные откаты данной транзакции. 41

Базы данных Операция явной синхронизации Лекция 12 Операция LOCK позволяет установить явную синхронизационную блокировку указанной таблицы (параметром операции является идентификатор таблицы). Выполнение операции LOCK гарантирует, что никакая другая транзакция до конца данной не сможет изменить эту таблицу (вставить в неё новый кортеж, удалить или модифицировать существующий), если установлена блокировка в режиме чтения, или даже прочитать любой кортеж этой таблицы, если установлена монопольная блокировка. 42

Базы данных Общие принципы организации данных во внешней памяти в SQL-ориентированных СУБД Лекция 12 SQL-ориентированные СУБД обладают рядом особенностей, влияющих на организацию внешней памяти. Наиболее важными являются следующие особенности: Наличие двух уровней системы: уровня непосредственного управления данными во внешней памяти и языкового уровня; Поддержка таблиц-каталогов; Регулярность структур данных; Необходимость обеспечения возможности эффективного выполнения операторов языкового уровня как над одной таблицей, так и над несколькими таблицами; Поддержка избыточности хранения данных. 43

Базы данных Общие принципы организации данных во внешней памяти в SQL-ориентированных СУБД Лекция 12 Соответственно возникают следующие разновидности объектов во внешней памяти базы данных: строки таблиц основная часть базы данных, большей частью непосредственно видимая пользователям; управляющие структуры индексы, создаваемые по инициативе пользователя (администратора) или верхнего уровня системы из соображений повышения эффективности выполнения запросов и обычно автоматически поддерживаемые нижним уровнем системы; журнальная информация, поддерживаемая для удовлетворения потребности в надёжном хранении данных; служебная информация, поддерживаемая для удовлетворения внутренних потребностей нижнего уровня системы (например, информация о свободной памяти). 44

Базы данных Хранение таблиц Лекция 12 Существуют два принципиальных подхода к физическому хранению таблиц. покортежное хранение таблиц единицей физического хранения является кортеж; хранение таблицы по столбцам единицей хранения является столбец таблицы с исключенными дубликатами. 45

Базы данных Хранение таблиц Лекция 12 Организацию хранения кортежей по строкам можно в целом охарактеризовать следующим образом: каждый кортеж обладает уникальным идентификатором (tid), не изменяемым во все время существования кортежа и позволяющим выбрать кортеж в основную память не более чем за два обращения к внешней памяти. каждый кортеж хранится целиком в одной странице; в одной странице данных хранятся кортежи только одной таблицы; изменение схемы хранимой таблицы с добавлением нового поля не вызывает потребности в физической реорганизации таблицы; распространенным способом повышения эффективности СУБД является кластеризация таблицы по значениям одного или нескольких столбцов; иногда применяется схема декластеризованного хранения таблиц: кортежи с общим значением столбца декластеризации размещаются на разных дисковых устройствах, обмены с которыми можно выполнять параллельно. 46

Базы данных Индексы Лекция 12 Обычно индекс определяется для одной таблицы, и ключом является значение её поля (возможно, составного). Если ключом индекса является возможный ключ таблицы, то индекс должен обладать свойством уникальности, т. е. не содержать дубликатов ключа. На практике ситуация выглядит обычно противоположно: при объявлении первичного ключа таблицы автоматически заводится уникальный индекс, а единственным способом объявления возможного ключа, отличного от первичного, является явное создание уникального индекса. Это связано с тем, что для проверки сохранения свойства уникальности возможного ключа, так или иначе, требуется индексная поддержка. Поскольку при выполнении многих операций уровня SQL требуется сортировка кортежей таблиц в соответствии со значениями некоторых полей, полезным свойством индекса является обеспечение последовательного просмотра кортежей таблицы в заданном диапазоне значений ключа в порядке возрастания или убывания значений ключа. 47

Базы данных Индексы Лекция 12 Одним из способов оптимизации выполнения эквисоединения таблиц является организация так называемых мультииндексов для нескольких таблиц, обладающих общими атрибутами. Любой из этих атрибутов (или их набор) может выступать в качестве ключа мультииндекса. Значению ключа сопоставляется набор кортежей всех связанных мультииндексом таблиц, значения выделенных атрибутов которых совпадают со значением ключа. Общей идеей любой организации индекса, поддерживающего прямой доступ по ключу и последовательный просмотр в порядке возрастания или убывания значений ключа является хранение упорядоченного списка значений ключа с привязкой к каждому значению ключа списка идентификаторов кортежей. Одна организация индекса отличается от другой, главным образом, в способе поиска ключа с заданным значением. 48

Базы данных B+-деревья Лекция 12 Наиболее популярным подходом к организации индексов в базах данных является использование техники B+-деревьев. Техника B- и B+-деревьев была предложена в начале 1970-х гг. Рудольфом Байером (Rudolf Bayer) и Эдом Маккрейтом (Ed McCreight). С точки зрения внешнего логического представления B-дерево это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева это свойство каждого узла дерева ссылаться на большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т. е. каждому узлу дерева соответствует блок внешней памяти (страница). В B+-дереве внутренние и листовые страницы обычно имеют разную структуру. 49

Базы данных B+-деревья Лекция 12 Типовая структура внутренней страницы B+-дерева: При этом выдерживаются следующие свойства: ключ 1 ключ 2... ключ m ; в странице дерева N m находятся ключи k со значениями ключ m k ключ m+1. Листовая страница обычно имеет следующую структуру: Листовая страница обладает следующими свойствами: ключ 1 < ключ 2

Базы данных B+-деревья Лекция 12 Поиск в B+-дереве это прохождение от корня к листу в соответствии с заданным значением ключа. Поскольку B+-деревья являются сильно ветвистыми и сбалансированными, для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной log n (m). Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск. Основной «изюминкой» B+-деревьев является автоматическое поддержание свойства сбалансированности. 51

Базы данных Хэширование Лекция 12 Альтернативным и достаточно популярным подходом к организации индексов является использование техники хэширования. Общей идеей методов хэширования является применение к значению ключа некоторой функции свёртки (хэш-функции), вырабатывающей значение меньшего размера. Значение хэш-функции затем используется для доступа к записи. Основным требованием к хэш-функции является равномерное распределение значение свёртки. При возникновении коллизий (одна и та же свёртка для нескольких значений ключа) образуются цепочки переполнения. Главным ограничением этого метода является фиксированный размер таблицы. Существуют следующие подходы: расширяемое хеширование; линейное хеширование. 52

Базы данных Журнальная информация Лекция 12 Журнал обычно представляет собой чисто последовательный файл с записями переменного размера, которые можно просматривать в прямом или обратном порядке. Обмены производятся стандартными порциями (страницами) с использованием буфера оперативной памяти. В грамотно организованных системах структура журнальных записей известна только компонентам СУБД, ответственным за журнализацию и восстановление. Поскольку содержимое журнала является критичным при восстановлении базы данных после сбоев, к ведению файла журнала предъявляются особые требования по части надёжности. В частности, обычно стремятся поддерживать две идентичные копии журнала на разных устройствах внешней памяти. 53

Базы данных Служебная информация Лекция 12 Для корректной работы подсистемы управления данными во внешней памяти необходимо поддерживать информацию, которая используется только этой подсистемой и не видна подсистеме языкового уровня. Набор структур служебной информации зависит от общей организации системы, но обычно требуется поддержание следующих служебных данных: Внутренние каталоги, описывающие физические свойства объектов базы данных; Описатели свободной и занятой памяти в страницах данных; Связывание страниц одной таблицы. 54