Принципы поддержки целостности в реляционной модели данных

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

Мы отметили, что только существенные или значимые изменения предметной области должны отслеживаться в информационной модели. Действительно, модель всегда представляет собой некоторое упрощение реального объекта, в модели мы отражаем только то, что нам важно для решения конкретного набора задач. Именно поэтому в информационной системе «Библиотека» мы, например, не отразили место хранения конкретных экземпляров книг, потому что мы не ставили задачу автоматической адресации библиотечных стеллажей. И в этом случае любое перемещение книг с одного места на другое не будет отражено в модели, это перемещение несущественно для наших задач. С другой стороны, процесс взятия книги читателем или возврат любой книги в библиотеку для нас важен, и мы должны его отслеживать в соответствии с изменениями в реальной предметной области. И с этой точки зрения наличие у экземпляра книги указателя на его отсутствие в библиотеке и одновременное отсутствие записи о конкретном номере читательского билета, за которым числится этот экземпляр книга, является противоречием, такого быть не должно. И в модели данных должны быть предусмотрены средства и методы, которые позволят нам обеспечивать динамическое отслеживание в базе данных согласованных действий, связанных с согласованным изменением информации. Именно этим вопросам и посвящена данная глава.

Горизонтальное представление

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

Например, у нас есть таблица «Сотрудник» (EMPLOYEE) с полями «Табельный номер» (T_NUM), «ФИО» (NAME), «должность»(POSITION), «оклад»(SALARY), «надбав-Ka»(PREMIUM), «отдел» (DEPARTMENT).

Для приложения, с которым работает начальник отдела продаж, будет создано представление

CREATE VIEW SAL_DEPT AS

SELECT * FROM EMPLOYEE WHERE DEPARTMENT= "Отдел продаж"

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

Часто представления базируются на многотабличных запросах. Такое использование позволяет упростить разработку пользовательского интерфейса, сохранив при этом корректность схемы базы данных. Для примера снова обратимся к базе данных «Библиотека» и создадим представление, которое содержит список читателей-должников с указанием книг/ которые у них на руках, и указанных в базе сроков сдачи этих книг. Такое представление может понадобиться для административного приложения, которое разрабатывается для директора библиотеки или его заместителя, они должны принимать административные меры для наказания нарушителей и возврата книг в библиотеку.

CREATE VIEW DEBTORS

ISBN,TITLE. NUM_READER.NAME.ADRES.HOME_PHON. WORK_PHON.DATA_OUT

AS

SELECT ISBN.TITLE.NUM_READER,NAME,ADRES.HOME_PHON. WORK_PHON,DATA_OUT

FROM BOOKS.EXEMPLAR.READERS

WHERE BOOKS.ISBN = EXEMPLAR.ISBN AND

EXEMPLAR.NUM_READER = READERS.NUM_READER AND

EXEMPLAR.PRESENT = FALSE AND

EXEMPLAR.DATA OUT < GetDate()

Общие понятия и определения целостности

Поддержка целостности в реляционной модели данных в ее классическом понимании включает в себя 3 аспекта.

Во-первых, это поддержка структурной целостности, которая трактуется как то, что реляционная СУБД должна допускать работу только с однородными структурами данных типа «реляционное отношение». При этом понятие «реляционного отношения» должно удовлетворять всем ограничениям, накладываемым на него в классической теории реляционной БД (отсутствие дубликатов кортежей, соответственно обязательное наличие первичного ключа, отсутствие понятия упорядоченности кортежей).

В дополнение к структурной целостности необходимо рассмотреть проблему неопределенных Null значений. Как уже указывалось раньше, неопределенное значение интерпретируется в реляционной модели как значение, неизвестное на данный момент времени. Это значение при появлении дополнительной информации в любой момент времени может быть заменено на некоторое конкретное значение. При сравнении неопределенных значений не действуют стандартные правила сравнения: одно неопределенное значение никогда не считается равным другому неопределенному значению. Для выявления равенства значения некоторого атрибута неопределенному применяют специальные стандартные предикаты:

<имя атрибута>IS NULL и <имя атрибута> IS NOT NULL.

Если в данном кортеже (в данной строке) указанный атрибут имеет неопределенное значение, то предикат IS NULL принимает значение TRUE (Истина), а предикат IS NOT NULL — FALSE (Ложь), в противном случае предикат IS NULL принимает значение FALSE, а предикат IS NOT NULL принимает значение TRUE.

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

Таблица 8.1. Таблица истинности для логических операций с неопределенными значениями ,

	А		В		Not A		A&B		A V В
	TRUE		TRUE		FA		TRUE		TRUE
	TRUE		FALSE		FALSE		FALSE		TRUE

<

В стандарте SQL2 появилась возможность

	А	B	Not A	A&B	A V В
	TRUE	Null	FALSE	Null	TRUE
	FALSE	TRUE	TRUE	FALSE	TRUE
	FALSE	FALSE	TRUE	FALSE	FALSE
	FALSE	Null	TRUE	FALSE	Null
	Null	TRUE	Null	Null	TRUE
	Null	FALSE	Null	FALSE	Null
	Null	Null	Null	Null	Null

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

Логическое выражение> IS {TRUE | FALSE | UNKNOWN}

Во-вторых, это поддержка языковой целостности, которая состоит в том, что реляционная СУБД должна обеспечивать языки описания и манипулирования данными не ниже стандарта SQL. He должны быть доступны иные низкоуровневые средства манипулирования данными, не соответствующие стандарту.

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

В-третьих, это поддержка ссылочной целостности (Declarative Referential Integrity, DRI), означает обеспечение одного из заданных принципов взаимосвязи между экземплярами кортежей взаимосвязанных отношений:

кортежи подчиненного отношения уничтожаются при удалении кортежа основного отношения, связанного с ними.

кортежи основного отношения модифицируются при удалении кортежа основного отношения, связанного с ними, при этом на месте ключа родительского отношения ставится неопределенное Null значение.

Ссылочная целостность обеспечивает поддержку непротиворечивого состояния БД в процессе модификации данных при выполнении операций добавления или удаления.

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

Структурная, языковая и ссылочная целостность определяют правила работы СУБД с реляционными структурами данных.

Требования поддержки этих трех видов

Требования поддержки этих трех видов целостности говорят о том, что каждая СУБД должна уметь это делать, а разработчики должны это учитывать при построении баз данных с использованием реляционной модели. И эти требования поддержки целостности достаточно абстрактны, они определяют допустимую форму представления и обработки информации в реляционных базах данных. Но с другой стороны, эти аспекты никак не касаются содержания базы данных. Для определения некоторых ограничений, которые связаны с содержанием базы данных, требуются другие методы. Именно эти методы и сведены в поддержку семантической целостности. Давайте рассмотрим конкретный пример. То, что мы можем построить схему базы данных или ее концептуальную модель только из совокупности нормализованных таблиц, определяет структурную целостность. И мы построили нашу схему библиотеки из пяти взаимосвязанных отношений. Но мы не можем с помощью перечисленных трех методов поддержки целостности обеспечить ряд правил, которые определены в нашей предметной области и должны в ней соблюдаться. К таким правилам могут быть отнесены следующие:

В библиотеке должны быть записаны читатели не моложе 17 лет.

В библиотеке присутствуют книги, изданные начиная с 1960 по текущий год.

Каждый читатель может держать на руках не более 5 книг.

4. Каждый читатель при регистрации в библиотеке должен дать телефон для связи: он может быть рабочим или домашним.

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

Семантическая поддержка может быть обеспечена двумя путями: декларативным и процедурным путем. Декларативный путь связан с наличием механизмов в рамках СУБД, обеспечивающих проверку и выполнение ряда декларативно заданных правил-ограничений, называемых чаще всего «бизнес-правилами» (Business Rules) или декларативными ограничениями целостности.

Выделяются следующие виды декларативных ограничений целостности:

Ограничения целостности атрибута: значение по умолчанию, задание обязательности или необязательности значений (Null), задание условий на значения атрибутов.

Задание значения по умолчанию означает,

Задание значения по умолчанию означает, что каждый раз при вводе новой строки в отношение, при отсутствии данных в указанном столбце этому атрибуту присваивается именно значение по умолчанию. Например, при вводе новых книг разумно в качестве значения по умолчанию для года издания задать значение текущего года. Например, для MS Access 97 это выражение будет иметь вид:

YEAR(NOW())

Здесь NOW() — функция, возвращающая значение текущей даты, YEAR(data) — функция, возвращающая значение года указанной в качестве параметра даты.

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

Для MS Access 97 это выражение будет выглядеть следующим образом:

Between 1960 AND YEAR(NOW())

В СУБД MS SQL Server7.0 значение по умолчанию записывается в качестве «бизнес-правила». В этом случае будет использоваться выражение, в котором явным образом должно быть указано имя соответствующего столбца, например:

YEAR_PUBL >= 1960 AND YEAR_PUBL <- YEAR(GETDATE())

Здесь GETDATE() — функция MS SQL Server7.0, возвращающая значение текущей даты, YEAR_PUBL — имя столбца, соответствующего году издания.

Ограничения целостности, задаваемые на уровне доменов, при поддержке доменной структуры. Эти ограничения удобны, если в базе данных присутствуют несколько столбцов разных отношений, которые принимают значения из одного и того же множества допустимых значений. Некоторые СУБД поддерживают подобную доменную структуру, то есть разрешают определять отдельно домены, задавать тип данных для каждого домена и задавать соответственно ограничения в виде бизнес-правил для доменов. А для атрибутов задается не примитивный первичный тип данных, а их принадлежность тому или другому домену. Иногда доменная структура выражена неявно и в ряде СУБД применяется специальная терминология для этого.

вместо понятия домена вводится

Так, например, в MS SQL Server 7. 0 вместо понятия домена вводится понятие типа данных, определенных пользователем, но смысл этого типа данных фактически эквивалентен смыслу домена. В этом случае действительно удобно задать ограничение на значение прямо на уровне домена, тогда оно автоматически будет выполняться для всех атрибутов, которые принимают значения из этого домена. А почему удобно задать это ограничение на уровне домена? А если мы зададим это ограничение для каждого атрибута, входящего в домен, разве наша система будет работать неправильно? Нет, конечно, она будет работать правильно, но представьте себе, что у вас в организации изменились правила работы, которые выражены в виде декларативных ограничений на значения. В нашем случае, например, мы будем комплектовать библиотеку более новыми книгами и теперь будем принимать в библиотеку книги, изданные не позднее 1980 года. А если это ограничение у нас задано не на один столбец, то нам надо просматривать все отношения и во всех отношениях менять старое правило на новое. Не легче ли заменить его один раз в домене, а все атрибуты, которые принимают значения из этого домена, будут автоматически работать по новому правилу.

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

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

Ограничения целостности, задаваемые на уровне отношения. Некоторые семантические правила невозможно преобразовать в выражения, которые будут применимы только к одному столбцу. В нашем примере с библиотекой мы не сможем выразить требование наличия по крайней мере одного телефонного номера для быстрой связи с читателем.

У нас под телефоны отведены

У нас под телефоны отведены два столбца, это в некотором роде искусственно, но специально так сделано, чтобы показать вам другой тип ограничений. Каждый из атрибутов является в общем случае необязательным и может принимать неопределенные значения: не обязательно должен быть задан как рабочий, так и домашний телефон. Мы хотим потребовать, чтобы из двух по крайней мере один телефон был бы задан обязательно. Попробуем сформулировать это в терминологии неопределенных значений баз данных. Домашний телефон должен быть задан (NOT NULL) или рабочий телефон должен быть задан (NOT NULL). Для MS Access97 или для MS SQL Server97 соответствующее выражение будет выглядеть следующим образом:

HOME_PHON IS NOT NULL OR WORK_PHON IS NOT NULL

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

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

Ограничение стандарта SQL1 на обновление представлений

Несмотря на то, что для пользователей представления выглядят как реальные отношения, существует ряд ограничений на операции модификации данных, связанные с представлениями.

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

Согласно стандарту, представление можно обновлять только в том случае, когда его запрос соответствует следующим требованиям:

В запросе должен отсутствовать предикат DISTINCT, то есть повторяющиеся строки не должны исключаться из таблицы результатов запроса.

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

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

В предложении WHERE не должен стоять вложенный запрос; в нем могут присутствовать только простые условия поиска.

В запросе не должно присутствовать выражение группировки GROUP BY или HAVING.

Однако в ряде коммерческих СУБД эти требования смягчены и операции модификации разрешены для более широкого класса представлений.

Операторы DDL в языке SQL с заданием ограничений целостности

Декларативные ограничения целостности задаются на уровне операторов создания таблиц. В стандарте SQL оператор создания таблиц имеет следующий синтаксис:

определение таблицы>: :=CREATE TABLE <имя таблицы>

(<описание элемента таблицы> [{.<описание элемента таблицы>}...])

<описание элемента таблицы>::=<определение столбца>|

<определение ограничений таблицы>

определение столбца>::=<имя столбца> <тип данных>

[<значение по умолчанию>][<дополнительные ограничения столбца>...]

<значение по умолчанию>::=DEFAULT { <litera1> | USER | NULL }

дополнительные ограничения столбца>: :=NOT NULL

[ограничение уникальности столбца>]|

<ограничение по ссылкам столбца>|

CHECK (<условия проверки на допустимость>) ограничение уникальности столбца>::= UNIQUE

<ограничение по ссылкам столбца>: :=FOREIGN KEY спецификация ссылки> спецификация ссылки>::= REFERENCES <имя основной таблицы>

(<имя первичного ключа основной таблицы>)

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

При описании таблицы задается имя таблицы, которое является идентификатором в базовом языке СУБД и должно соответствовать требованиям именования объектов в данном языке.

Кроме имени таблицы в операторе указывается список элементов таблицы, каждый из которых служит либо для определения столбца, либо для определения ограничения целостности определяемой таблицы. Требуется наличие хотя бы одного определения столбца. То есть таблицу, которая не имеет ни одного столбца, определить нельзя. Количество столбцов в одной таблице не ограничено, но в конкретных СУБД обычно бывают ограничения на количество атрибутов. Так, например, в MS SQL Server 6.5 максимальное количество столбцов в таблице было 250, но уже в MS SQL Server 7.0 оно увеличено до 1024.

Оператор CREATE TABLE определяет так называемую базовую таблицу, то есть реальное хранилище данных.

Как видно, кроме обязательной части,

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

В разделе значения по умолчанию указывается значение, которое должно быть помещено в строку, заносимую в данную таблицу, если значение данного столбца явно не указано. В соответствии со стандартом языка SQL значение по умолчанию может быть указано в виде литеральной константы с типом, соответствующим типу столбца; путем задания ключевого слова USER, которому при выполнении оператора занесения строки соответствует символьная строка, содержащая имя текущего пользователя (в этом случае столбец должен иметь тип символьных строк); или путем задания ключевого слова NULL, означающего, что значением по умолчанию является неопределенное значение. Если значение столбца по умолчанию не специфицировано и в разделе ограничений целостности столбца указано NOT NULL (то есть наличие неопределенных значений запрещено), то попытка занести в таблицу строку с незаданным значением данного столбца приведет к ошибке.

Задание в разделе ограничений целостности столбца выражения NOT NULL приводит к неявному порождению проверочного ограничения целостности для всей таблицы "CHECK (С IS NOT NULL)" (где С — имя данного столбца). Если ограничение NOT NULL не указано и раздел умолчаний отсутствует, то неявно порождается раздел умолчаний DEFAULT NULL. Если указана спецификация уникальности, то порождается соответствующая спецификация уникальности для таблицы.

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

Если в. разделе ограничений целостности указано ограничение по ссылкам данного столбца, то порождается соответствующее определение ограничения по ссылкам для таблицы: FOREIGN КЕУ(<имя столбца>) <спецификация ссылки>, что означает, что значения данного столбца должны быть взяты из соответствующего столбца родительской таблицы.

в данном случае называется таблица,

Родительской таблицей в данном случае называется таблица, которая связана с данной таблицей связью «один-ко-многим» (1:М). При этом каждая строка родительской таблицы может быть связана с несколькими строками определяемой таблицы. Трансляция операторов SQL проводится в режиме интерпретации, поэтому важно, чтобы сначала была бы описана родительская таблица, а потом уже все подчиненные (дочерние) таблицы, связанные с ней. Иначе транслятор определит ссылку на неопределенный объект.

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

В главе 5 определены типы данных, которые допустимы по стандартам SQL. Попробуем написать простейший оператор создания таблицы BOOKS из базы данных «Библиотека».

При этом будем предполагать наличие следующих ограничений целостности:

Шифр книги — последовательность символов длиной не более 14, однозначно определяющая книгу, значит, это — фактически первичный ключ таблицы BOOKS.

Название книги — последовательность символов, не более 120. Обязательно должно быть задано.

Автор — последовательность символов, не более 30, может быть не задан.

Соавтор — последовательность символов, не более 30, может быть не задан.

Год издания — целое число, не менее 1960 и не более текущего года. По умолчанию ставится текущий год.

Издательство — последовательность символов, не более 20, может отсутствовать.

Количество страниц — целое число не менее 5 и не более 1000.

CREATE TABLE BOOKS

(

ISBN varchar(14) NOT NULL PRIMARY KEY,

TITLE varchar(120) NOT NULL.

AUTOR varchar (30) NULL.

COAUTOR varchar(30) NULL,

YEAR_PUBLsmallint DEFAULT Year(GetDate())

CHECK(YEAR_PUBL >= 1960 AND YEAR PUBL <= YEAR(GetDate())),

PUBLICH varchar(20) NULL.

Почему мы не задали обязательность

PAGES smalllnt CHECK(PAGES > = 5 AND PAGES <= 1000)

);

Почему мы не задали обязательность значения для количества страниц в книге? Потому что это является следствием проверочного ограничения, заданного на количество страниц, количество страниц всегда должно лежать в пределах от 5 до 1000, значит, оно не может быть незаданным и система это контролирует автоматически.

Теперь зададим описание таблицы «Читатели», которой соответствует отношение READERS:

Номер читательского билета — это целое число в пределах 32 000 и он уникально определяет читателя.

Имя, фамилия читателя — это последовательность символов, не более 30.

Адрес — это последовательность символов, не более 50.

Номера телефонов рабочего и домашнего — последовательность символов, не более 12.

Дата рождения — календарная дата. В библиотеку принимаются читатели не младше 17 лет.

CREATE TABLE READERS

(

READER_ID Smallint(4) PRIMARY KEY.

FIRST_NAME char(30) NOT NULL.

LAST_NAME char(30) NOT NULL.

ADRES char(50).

HOME_PHON char(12).

WORK_PHON chart 12),

BIRTH_DAYdate

CHECK(DateDiff(year. GetDate() ,BIRTH_DAY) >=17)

);

Здесь DateDiff (часть даты, начальная дата, конечная дата) — функция MS SQL Server 7.0, которая определяет разность между начальной и конечной датами, заданную в единицах, определенных первым параметром — часть даты. Мы задали в качестве параметра Year, что значит, что мы разность определяем в годах.

Теперь зададим операцию создания таблицы EXEMPLAR (экземпляры книги). В этой таблице первичным ключом является атрибут, задающий инвентарный номер экземпляра книги. В такой постановке мы полагаем, что при поступлении книг в библиотеку им просто присваиваются соответствующие порядковые номера. Для того чтобы не утруждать библиотекаря все время помнить, какой номер был последним, мы можем воспользоваться тем, что некоторые СУБД допускают специальный инкрементный тип данных, то есть такой, значения которого автоматически увеличиваются или уменьшаются на заданную величину при каждом новом вводе данных.

В СУБД MS Access такой

В СУБД MS Access такой тип данных называется «счетчик» (counter) и он всегда имеет начальное значение 1 и шаг, равный тоже 1, то есть при вводе каждого нового значения счетчик увеличивается на 1, значит, практически считает вновь введенные значения. В СУБД MS SQL Server 7.0 это свойство -IDENTITY, которое может быть присвоено ряду целочисленных типов данных. В отличие от «счетчика» свойство IDENTITY позволяет считать с любым шагом, положительным или отрицательным, но обязательно целым. Если мы не задаем дополнительных параметров этому свойству, то оно начинает работать как счетчик в MS Access, начиная с единицы и добавляя при каждом вводе тоже единицу.

Кроме того, таблица EXEMPLAR является подчиненной двум другим ранее определенным таблицам: BOOKS и READERS. При этом с таблицей BOOKS таблица EXEMPLAR связана обязательной связью, потому что не может быть ни одного экземпляра книги, который бы не был приписан конкретной книге. С таблицей READERS таблица EXEMPLAR связана необязательной связью, потому что не каждый экземпляр в данный момент находится на руках у читателя. Для моделирования этих связей при создании таблицы EXEMPLAR должны быть определены два внешних ключа (FOREIGN KEY). При этом атрибут, соответствующий шифру книги (мы его назовем так же, как и в родительской таблице — ISBN), является обязательным, то есть не может принимать неопределенных значений, а атрибут, который является внешним ключом для связи с таблице READERS, является необязательным и может принимать неопределенные значения.

Необязательными там являются два остальных атрибута: дата взятия и дата возврата книги, оба они имеют тип данных, соответствующей календарной дате. Атрибут, который содержит информацию о присутствии или отсутствии книги, имеет логический тип. Напишем оператор создания таблицы EXEMPLAR в синтаксисе MS SQL Server 7.0:

CREATE TABLE EXEMPLAR

(

EXEMPLAR_ID | NT IDENTITY PRIMARY KEY,

ISBN varchar(14) NOT NULL FOREIGN KEY references BOOKS(ISBN),

NULL FOREIGN KEY references READERS

READERJD Smallint(4) NULL FOREIGN KEY references READERS (READERJD).

DATA_IN date.

DATA_OUT date,

EXIST Logical,

);

Как мы уже знаем, не все декларативные ограничения могут быть заданы на уровне столбцов таблицы, часть ограничений может быть задана только на уровне всей таблицы. Например, если мы имеем в качестве первичного ключа не один атрибут, а последовательность атрибутов, то мы не можем определить ограничение типа PRIMARY KEY (первичный ключ) только на уровне всей таблицы.

Допустим, что мы считаем экземпляры книги не подряд, а отдельно для каждого издания, тогда таблица EXEMPLAR в качестве первичного ключа будет иметь набор из двух атрибутов: это шифр книги (ISBN) и порядковый номер экземпляра

данной книги (ID_EXEMPL), в этом случае оператор создания таблицы EXEMPLAR будет выглядеть следующим образом:

CREATE TABLE EXEMPLAR

(

ID_EXEMPLAR int NOT NULL.

ISBN varchar(14) NOT NULL FOREIGN KEY references BOOKS(ISBN),

READERJD Smallint(4) NULL FOREIGN KEY references READERS (READERJD),

DATA_IN date.

DATA_OUT date,

EXIST Logical.

PRIMARY KEY (ID_EXEMPLAR. ISBN)

);

Мы видим, что один и тот же атрибут ISBN, с одной стороны, является внешним ключом (FORIGN KEY), а с другой стороны, является частью первичного ключа (PRIMARY KEY). И ограничение типа первичный ключ (PRIMARY KEY) задается не на уровне одного атрибута, а на уровне всей таблицы, потому что оно содержит набор атрибутов.

То же самое можно сказать и о проверочных (CHECK) ограничениях, если условия проверки предполагают сравнения значений нескольких столбцов таблицы. Введем дополнительное ограничение для таблицы BOOKS, которое может быть сформулировано следующим образом: соавтор не может быть задан, если не задан автор. При описании книги допустимо не задавать ни автора, ни соавтора, или задать и автора и соавтора, или задать только автора. Однако задание соавтора в отсутствие задания автора считается ошибочным. В этом случае оператор создания таблицы BOOKS будет выглядеть следующим образом:

AUTOR IS NULL AND COAUTOR

CREATE TABLE BOOKS

(

ISBN varchar(14) NOT NULL PRIMARY KEY.

TITLE varchar(120) NOT NULL,

AUTOR varchar (30) NULL.

COAUTOR varchar(30) NULL.

YEARJHJBL small int DEFAULT Year(GetDate())

CHECK(YEARJ>UBL > 1960 AND YEAR_PUBL <= YEAR(GetDate())).

PUBLICH varchar(20) NULL.

PAGES smallint CHECK( PAGES >= 5 AND PAGES <= 1000).

CHECK (NOT ( AUTOR IS NULL AND COAUTOR IS NOT NULL))

);

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

ное имя ограничения, затем тип ограничения и его выражения. Для идентификации ограничений рекомендуют использовать систему именования, которая легко позволит определить при получении сообщения об ошибке, которое вырабатывает СУБД, какое ограничение нарушено. Обычно имя ограничения состоит из краткого названия типа ограничения, далее через символ подчеркивания идет имя атрибута или таблицы, в зависимости от того, к какому уровню относится ограничение, и, наконец, порядковый номер ограничения данного типа, если к одному объекту задается несколько ограничений одного типа.

Сокращенные обозначения ограничений состоят из одной или двух букв и могут быть следующими:

РК — для первичного ключа;

FK — для внешнего ключа;

CK — для проверочного ограничения;

U — для ограничения уникальности;

DF — для ограничения типа значение по умолчанию.

Приведем пример оператора создания таблицы BOOKS с именованными ограничениями:

CREATE TABLE BOOKS

(

ISBN varchar(14) NOT NULL.

TITLE varchar(120) NOT NULL;

AUTOR varchar (30) NULL.

COAUTOR varchar(30) NULL.

YEAR_PUBL smallint NOT NULL.

PUBLICH varchar(20) NULL,

PAGES smallint NOT NULL.

CONSTRAINT PK_BOOKS PRIMARY KEY (ISBN).

CONSTRAINT OF_ YEAR_PUBL DEFAULT (Year(GetDate()).

CONSTRAINT CK_ YEAR_PUBL CHECK (YEAR_PUBL >- 1960 AND

YEAR_PUBL <= YEAR(GetDate())).

CONSTRANT CK_PAGES CHECK (PAGES > = 5 AND PAGES <= 1000).

AUTOR IS NULL AND COAUTOR

CONSTRAINT CK_BOOKS CHECK (NOT ( AUTOR IS NULL AND COAUTOR IS NOT NULL))

);

CREATE TABLE READERS

(

	READER_ID	Small int	PRIMARY KEY
	FIRST_NAME	char(30)	NOT NULL.
	LAST_NAME	char(30)	NOT NULL.
	ADRES	char(50).

HOME_PHON char(12).

WORK_PHON char(12).

BIRTH_DAY date CHECK( DateDiff(year, GetDate().BIRTH_DAY) >=17 ),

CONSTRAINT CK_READERS CHECK (HOME_PHON IS NOT NULL OR WORK_PHON IS NOT NULL) );

CREATE TABLE CATALOG

(

ID_CATALOG Smallint PRIMARY KEY,

KNOWELEDGE_AREA varchar(150)

);

CREATE TABLE EXEMPLAR

(

ID_EXEMPLAR Int NOT NULL,

ISBN varchar(14) NOT NULL FOREIGN KEY references BOOKS(ISBN),

READER_ID Smallint(4) NULL FOREIGN KEY references REABERS (READER_ID).

DATA_IN date.

DATA_OUT date.

EXIST Logical.

PRIMARY KEY (ID_EXEMPLAR, ISBN)

);

CREATE TABLE RELATION_1

(

ISBN varchar(14) NOT NULL

FOREIGN KEY references BOOKS(ISBN).

ID_CATALOG smallint NOT NULL

FOREIGN KEY references CATALOG(ID_CATALOG).

CONSTRAINT PK_RELATION_1

PRIMARY KEY (ISBN.ID_CATALOG) ).

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

В нашем примере с библиотекой порядок описания таблиц следующий:

дополнительная связующая таблица между книгами

Таблица BOOKS

Таблица READERS

Таблица CATALOG (системный каталог)

Таблица EXEMPLAR

Таблица RELATION_1 ( дополнительная связующая таблица между книгами и системным каталогом).

Набор операторов языка SQL принято называть не программой, а скриптом. Тогда скрипт, который добавит набор из 5 взаимосвязанных таблиц базы данных «Библиотека» в существующую базу данных, будет выглядеть следующим образом:

CREATE TABLE BOOKS

(

ISBN varchar(14) NOT NULL .

TITLE varchar(120) NOT NULL.

AUTOR varchar (30) NULL.

COAUTOR varchar(30) NULL.

YEAR_PUBL smallint NOT NULL.

PUBLICH varchar(20) NULL.

PAGES smallInt NOT NULL.

CONSTRAINT PK_BOOKS PRIMARY KEY (ISBN).

CONSTRAINT DF_ YEAR_PUBL DEFAULT (Year(GetDate()).

CONSTRAINT CK_ YEAR_PUBL CHECK (YEAR_PUBL >= 1960 AND

YEAR_PUBL <= YEAR(GetDate())).

CONSTRANT CK_PAGES CHECK (PAGES > = 5 AND PAGES <= 1000).

CONSTRAINT CK_BOOKS CHECK (NOT (AUTOR IS NULL AND COAUTOR IS NOT NULL)) CREATE TABLE READERS

(

READER_ID Small int PRIMARY KEY.

FIRST_NAME char(30) NOT NULL.

LAST_NAME char(30) NOT NULL.

ADRES char(50),

HOME_PHON char(12).

WORK_PHON char(12).

BIRTH_DAYdate СНЕCK DateDiff(year. GetDate().BIRTH_DAY) >=17 )

CONSTRAINT CK_READERS CHECK (HOME_PHON IS NOT NULL OR WORK_PHON IS NOT NULL)

);

CREATE TABLE CATALOG

(

ID_CATALOG Smallint PRIMARY KEY,

KNOWELEDGE_AREA varchar(l50)

);

CREATE TABLE EXEMPLAR

(

ID_EXEMPLAR int NOT NULL,

ISBN varchar(14) NOT NULL

FOREIGN KEY references BOOKS(ISBN).

READER_ID Smallint(4) NULL

FOREIGN KEY references READERS (READER_ID).

DATA_IN date,

DATA_OUT date.

EXIST Logical,

PRIMARY KEY (ID_EXEMPLAR. ISBN)

);

CREATE TABLE RELATION_1

(

ISBN varchar(14) NOT NULL

FOREIGN KEY references BOOKS(ISBN).

ID_CATALOG small int NOT NULL

FOREIGN KEY references CATALOG (ID_CATALOG),

CONSTRAINT PK_RELATION_1 PRIMARY KEY (ISBN.ID_CATALOG)

);

При написании скрипта мы добавили в оператор создания таблицы «Читатели» ограничение на уровне таблицы, которое связано с обязательным наличием хотя бы одного из двух телефонов.

Понятие представления операции создания представлений

Для описания внешних моделей в реляционной модели могут использоваться представления. Представление (View) — это SQL-запрос на выборку, который пользователь воспринимает как некоторое виртуальное отношение. Задание представлений входит в описание схемы БД в реляционных СУБД. Представления позволяют скрыть ненужные несущественные детали для разных пользователей, модифицировать реальные структуры данных в удобном для приложений виде и, наконец, разграничить права доступа к данным и тем самым повысить защиту данных от несанкционированного доступа.

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

Оператор определения представления имеет следующий вид:

<создание представлениям := CREATE VIEW <имя представления> [ (<список столбцов>)] AS <SQL-3anpoc>

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

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

Рассмотрим типичные виды представлений и их назначение.

Сгруппированные представления

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

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

CREATE VIEW RATE

DEPARTMENT. COUNT(*). SUM(SALARY). SUM(PREMIUM). MAX(SALARY). MIN(SALARY).

AVERAGE (SALARY). MAX(PREMIUM). MIN(PREMIUM), AVERAGE (PREMIUM) AS SELECT DEPARTMENT, COUNT(*). SUM(SALARY). SUM(PREMIUM). MAX(SALARY).

MIN(SALARY). AVERAGE (SALARY). MAX(PREMIUM). MIN(PREMIUM).

AVERAGE (PREMIUM) FROM EMPLOYEE GROUP BY DEPARTMENT

Средства изменения описания таблиц и средства удаления таблиц

В язык SQL добавлены средства изменения схемы таблиц. Что можно и что нельзя изменять в описании таблицы? В стандарте SQL2 добавлены достаточно широкие возможности по модификации уже существующих схем таблиц. Для модификации таблиц используется оператор ALTER TABLE, который позволяет выполнить следующие операции изменения для схемы таблицы:

добавить новый столбец в уже существующую и заполненную таблицу;

изменить значение по умолчанию для какого-либо столбца;

удалить столбец из существующей таблицы;

добавить или удалить первичный ключ таблицы;

добавить или удалить новый внешний ключ таблицы;

добавить или удалить условие уникальности;

добавить или удалить условие проверки для любого столбца или для таблицы в целом.

Синтаксис оператора ALTER TABLE:

<Изменить описание таблицы>::= ALTER TABLE <имя таблицы> { ADD определение столбца> |

ALTER <имя столбца> (SET DEFAULT <значение> DROP DEFAULT } |

DROP <имя столбца>{CASCADE | RESTRICT} |

ADD { <определение первичного ключа>| определение внешнего ключа> |

<условие уникальности данных> |

<условие проверки> } |

DROP CONSTRAINT имя условия { CASCADE | RESTRICT} }

Одним оператором ALTER TABLE можно провести только одно из перечисленных изменений, например, за один раз можно добавить один столбец. Если вам требуется добавить два столбца, то необходимо применить два оператора.

Давайте рассмотрим несколько примеров. Чаще всего применяется операция добавления столбца. Предложение определения нового столбца в операторе ALTER TABLE имеет точно такой же синтаксис, как и в операторе создания таблицы. Добавим столбец EDUCATION (образовние), содержащий символьный тип данных, с заданным перечнем значений («начальное», «среднее», «неоконченное высшее», «высшее»).

ALTER TABLE READERS

ADD EDUCATION varchar (30) DEFAULT NULL

CHECK (EDUCATION IS NULL OR

EDUCATION= "начальное" OR

EDUCATION= "среднее " OR EDUCATION= "неоконченное высшее" OR

В таблицу READERS будет добавлен

EDUCATION= "высшее" )

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

Добавим ограничение на соответствие между датами взятия и возврата книги в таблице EXEMPLAR. Действительно, если даты введены, то требуется, чтобы дата возврата книги была бы больше на срок выдачи книги. Считаем, что стандартным сроком являются 2 недели. Теперь сформулируем оператор изменения таблицы EXEMPLARE:

ALTER TABLE EXEMPLARE

ADD CONSTRAINT CK_ EXEMPLARE

CHECK ((DATA_IN IS NULL AND DATA_OUT IS NULL) OR

(DATA_OUT >= DATAJN +14) )

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

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

При изменении первичного ключа таблицы следует быть внимательными. Во-первых, у исходной таблицы могут быть подчиненные, при этом первичный ключ исходной таблицы является внешним ключом для подчиненных таблиц, и просто его удалить невозможно, СУБД контролирует ссылочную целостность и не позволит выполнить операцию удаления первичного ключа таблицы, если на него имеются ссылки. Следовательно, в этом случае порядок изменения первичного ключа должен быть таким, как на рис. 8.1:



Рис. 8.1. Алгоритм изменения первичного ключа таблицы

Чаще всего операция ALTER TABLE применяется в CASE-системах при автоматической генерации скриптов создания таблиц в базе данных. В этих системах универсальный алгоритм предполагает сначала создание всех таблиц, которые заданы в даталогической модели, и только после этого добавляются соответствующие связи. И это понятно — в отличие от человеческого разума искусственный интеллект CASE-системы будет испытывать затруднения в определении иерархических взаимосвязей таблиц базы данных, поэтому он предпочитает использовать универсальный алгоритм, в котором сначала все объекты определяются, а затем добавляются соответствующие свойства для атрибутов, которые являются внешними ключами с указанием требуемых ссылок.

В этом случае все операции

В этом случае все операции назначения внешних ключей будут считаться корректными, потому что все объекты были описаны заранее, и для такого алгоритма порядок создания таблиц безразличен. Далее приведен скрипт, который был получен при разработке схемы базы данных «Библиотека» в PowerDesignerG.l. По умолчанию для каждой таблицы создается индекс по первичному ключу, так что кроме знакомых операций создания и изменения таблиц мы увидим еще и операцию создания индексов (CREATE INDEX), после изучения физических моделей в базах данных мы еще вернемся к этой операции, а пока примем ее на веру. При создании даталогичекой модели в качестве СУБД был выбран сервер MS SQL Server 6.X, и для этого сервера скрипт был сгенерирован на встроенном языке этой СУБД, называмом TransactSQL. В нем операция USE <имя базы дан-ных> соответствует операции открытия базы данных, а команда до означает переход к выполнению следующей команды.

/* ================================ */

/* Database name: LIBRARY ' */ /* DBMS name: Microsoft SQL Server 6.x */

/* Created on: 06.10.00 18:56 */

/* ================================ */

/* Database name: LIBRARY */

/* ================================ */

use LIBRARY

go

/* ================================ */

/* Table: BOOKS */

/* ================================ */

create table BOOKS

(

	ISBN	varchar(14)	not null .
	TITLE	varchar(255)	not null .
	AUTOR	varchar(30)	null.
	COAUTOR	varchar(30)	null.
	PUBLICHER	varchar(30)	null.

WHERE_PUBLICH varchar(30) null,

YEAR_IZD smallint not null

constraint CKC_YEAR_IZD_BOOKS check

(

YEAR_PUBL >- 1969 AND YEAR_PUBL <= YEAR(GetDate())).

PAGES smallint not null

constraint CKC_PAGES_BOOKS check

(

PAGES between 5 and 1000).

constraint PK_BOOKS primary key (ISBN).

constraint CKT_BOOKS check

(

(AUTOR IS NOT NULL OR (AUTOR IS NULL AND COAUTOR IS NULL))) ) go

/* Table: READERS */

create table READERS

HOME_PHON IS NOT NULL OR

(

NUM_READER intnot null.

NAME varchar(30) not null.

BIRTH_DAY datetime not null

constraint CKC_BIRTH_DAY_READERS check

(

(DateDiffCyear. GetDate().BIRTH_DAY) >=17 )

),

SEX chard) not null

constraint CKC_SEX_READERS check

(

SEX in СМ'.'1'.'м'.'ж')).

HOME_PHON char(9) null.

WORK_PHON char(9) null,

constraint PK_READERS primary key (NUM_READER).

constraint CKT_READERS check

(

( HOME_PHON IS NOT NULL OR WORK_PHON IS NOT NULL))

)

go

/* Table: CATALOG */

/* ================================ */



create table CATALOG

( KW KOD smallint not null.

NAME_KW varchar(255) null, constraint PK_CATALOG primary key (KW_KOD)

)

go

/* ================================ */

/* Table: EXEMPLAR */

create table EXEMPLAR

(

	INVJUMER	int not	null.
	ISBN	varchar(14)	not null .
	NUM_READER	int	null.
	PRESENT	bit not	null.
	DATE_IN	datetime	null.
	DATE OUT	datetime	null.

constraint PK_EXEMPLAR primary key (INVJUMER) )

go

/* ================================ */

/* Index: RELATION_43_FK ' . */ /*

/* ================================ */

create index RELATION_43_FK on EXEMPLAR (ISBN) .

go

/* Index: RELATION_44_FK */

/* ================================ */

create index RELATION_44_FK on EXEMPLAR (NUM_READER) go

/* ================================ */

/* Table: RELATION_67 */

/* ================================ */

create table RELATION_67

(

ISBN varchar(14) not null, KW_KOD smallint not null, constraint

PK_RELATION_67 primary key (ISBN, KW_KOD)

)

go

/* ================================ */

/* Index: IOIINEONY_E_IAEANOE_CIAIEE_FK */

/* ================================ */

create index IOIINEONY_E_IAEANOE_CIAIEE_FK on RELATION_67 (ISBN) go

/* ================================ */

/* Index: I_AANOAAEAIA_A_EIEAAO_FK */

create index I_AANOAAEAIA_A_EIEAAO_FK on RELATION_67 (KW_KOD)

go

alter table EXEMPLAR

add constraint FK_EXEMPLAR_RELATION_BOOKS foreign key (ISBN)

add constraint FK_EXEMPLAR_RELATION_READERS foreign key

references BOOKS (ISBN)

go

alter table EXEMPLAR

add constraint FK_EXEMPLAR_RELATION_READERS foreign key (NUM_READER)

references READERS (NUM_READER) go alter table RELATION_67

add constraint FK_RELATION_IOIINEONY_BOOKS foreign key (ISBN)

references BOOKS (ISBN) go alter table RELATION_67

add constraint FK_RELATION_I_AANOAAE_CATALOG foreign key (KW_KOD)

references CATALOG (KW_KOD) go

В языке SQL присутствует и операция удаления таблиц. Синтаксис этой операции предельно прост:

<Удалить таблицу>::= DROP TABLE <имя таблицы> [CASCADE | RESTRICT]

Параметр CASCADE означает, что при удалении таблицы одновременно удаляются и все объекты, связанные с ней. С таблицей, кроме рассмотренных ранее ограничений, могут быть связаны также объекты типа триггеров и представления. Понятие представления будет рассмотрено в следующем подразделе, а триггеров мы коснемся в разделах, связанных с архитектурой клиент-сервер. Однако операция удаления объектов определяется еще правами пользователей, что связано с концепцией безопасности в базах данных. Это значит, что если вы не являетесь владельцем объекта, то вы можете не иметь прав на его удаление. И в этом случае синтаксически правильный оператор DROP TABLE не может быть выполнен системой в силу отсутствия прав на удаление связанных с удаляемой таблицей объектов. Кроме того, операция удаления таблицы не должна нарушать целостность базы данных, поэтому удалять таблицу, на которую имеются ссылки других таблиц, невозможно.

Например, в нашей схеме, связанной с библиотекой, мы не можем удалить ни таблицу BOOKS, ни таблицу READERS, ни таблицу CATALOG. У этих таблиц есть связь с подчиненными таблицами EXEMPLAR и RELATION_67. Поэтому если вы хотите удалить некоторый набор таблиц, то сначала необходимо грамотно построить последовательность их удаления, которая не нарушит базовых принципов поддержки целостности вашей схемы БД. В нашем примере последовательность операторов удаления таблиц может быть следующей:

DROP TABLE EXEMPLAR

DROP TABLE RELATION_67

DROP TABLE CATALOG

DROP TABLE READERS

DROP TABLE BOOKS

Средства определения схемы базы данных

В стандарте SQL1 задается спецификация оператора описания схемы базы данных, но не указывается способ создания собственно базы данных, поэтому в различных СУБД используются неодинаковые подходы к этому вопросу.

Например, в СУБД ORACLE база данных создается в ходе установки программного обеспечения собственно СУБД. Все таблицы пользователей помещаются в единую базу данных. Однако они могут быть разделены на группы, объединенные в подсхемы. Понятие подсхемы не стандартизировано в SQL и не используется в других СУБД.

В состав СУБД INGRES входит специальная системная утилита, имеющая имя CREATEDB, которая позволяет создавать новые базы данных. Права на использование этой утилиты имеет администратор сервера. Для удаления базы данных существует соответствующая утилита DESTROYDB.

В СУБД MS SQL Server существует специальный оператор CREATE DATABASE, который является частью языка определения данных, для удаления базы данных в языке определен оператор DROP DATABASE. Правами на создание баз данных наделяются администраторы баз данных, которых в общем случае может быть несколько. .Правами более высокого уровня обладает администратор сервера баз данных (SQL Server), который и может предоставить права администратора базы данных другим пользователям сервера. Администраторы баз данных могут удалить только свою базу данных. Приведем пример оператора создания схемы базы данных в MS SQL Server 7.0:

CREATE DATABASE databasename

[ON [PRIMARY][<спецификация файла>[... .n]][.«группа файлов> [,...n]]]

[ LOG ON { спецификация файла> [,...n]} ][ FOR LOAD | FOR ATTACH ] спецификация файла> : : = ( [ NAME = логическое имя файла,]FILENAME = 'физическое имя файла'

[. SIZE = размер][, MAXSIZE - { максимальный размер | UNLIMITED } ]

[. FILEGROWTH = инкремент увеличения файла] ) [,...п] <группа файлов>::= FILEGROUP имя группы файлов спецификация файла> [,...п]

Здесь

database_name — имя базы данных, идентификатор в системе;

ON — ключевое слово, которое означает, что далее будут заданы спецификации файлов, которые будут использованы для размещения базы данных;

ключевое слово, которое определяет первичное

PRIMARY — ключевое слово, которое определяет первичное файловое пространство, в котором будет размещена собственно база данных;

LOG ON — ключевое слово, которое задает спецификацию файлов, которые будут использованы для хранения журналов транзакций;

FOR LOAD — ключевое слово, которое определяет, что после создания базы данных будет произведена загрузка базы данных данными;

FOR ATTACH — предложение, которое определяет, что база данных для управления будет подсоединена к другому серверу.

Почти все параметры, кроме имени базы данных, являются необязательными, поэтому оператор создания простой базы данных «Библиотека» может выглядеть следующим образом:

CREATE DATABASE Library

Для изменения схемы базы данных в MS SQL Server 7.0 может быть использована команда:

ALTER DATABASE database

{ ADD FILE спецификация файлов> [,...n] [TO FILEGROUP filegroup_name]

| ADD LOG FILE спецификация файлов> [,...n]

| REMOVE FILE имя_файла

| ADD FILEGROUP имя_группы файлов

|REMOVE FILEGROUP имя группы_файлов

|MODIFY FILE <спецификация файлов>

(MODIFY FILEGROUP имя_группы_файлов имя_свойства_группы файлов}

Здесь свойства группы файлов определяет одно из допустимых ключевых слов:

READONLY — только для чтения;

READWRITE — для чтения и записи;

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

Как видно, при изменении схемы базы данных в нее могут быть добавлены (ADD) дополнительные файлы и файловые группы или удалены (REMOVE ) ранее определенные файлы или файловые группы. Назначение этих файлов нам будет более понятно после того, как мы познакомимся с физическими моделями и файловыми структурами, используемыми для хранения данных в базах данных.

Сейчас мы познакомимся с последней командой, которая предназначена для удаления базы данных. В MS SQL Server 7.0 это команда имеет следующий синтаксис:

DROP DATABASE databasename

После выполнения этой команды уничтожается вся база данных вместе с содержащимися в ней данными.

Вертикальное представление

Этот вид представления практически соответствует выполнению операции проектирования некоторого отношения на ряд столбцов. Он используется в основном для скрытия информации, которая не должна быть доступна в конкретной внешней модели.

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

CREATE VIEW TABEL AS

SELECT T_NUM.NAME. POSITION. DEPARTMENT FROM EMPLOYEE

Архитектура разделяемой памяти

По причинам объективно существующей разницы в скорости работы процессоров, оперативной памяти и устройств внешней памяти (эта разница в скорости существовала, существует и будет существовать всегда) буферизация страниц базы данных в оперативной памяти — единственный реальный способ достижения удовлетворительной эффективности СУБД.

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

Разделяемая память, управляемая СУБД, состоит из нескольких типов буферов:

Буферы страниц данных, которые содержат копии страниц данных, с которыми работает СУБД.

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

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

Информация в буферах взаимосвязана, и требуется эффективная система поддержки единой работы всех частей разделяемой памяти.

Если бы запись об изменении базы данных реально немедленно записывалась во внешнюю память, это привело бы к существенному замедлению работы системы.

Поэтому записи в журнал тоже буферизуются: при нормальной работе очередная страница выталкивается во внешнюю память журнала только при полном заполнении записями.

Но реальная ситуация является более сложной. Имеются два вида буферов — буфер журнала и буфер страниц оперативной памяти, которые содержат связанную информацию. И те и другие буферы могут выталкиваться во внешнюю память. Проблема состоит в выработке некоторой общей политики выталкивания, которая обеспечивала бы возможности восстановления состояния базы данных после сбоев.

Буфера не выделяются для каждого

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

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

На этом мы закончили рассмотрение физических моделей, применяемых в базах данных. Физические модели большей частью скрыты от пользователей. Однако в SQL существует команда создания индексных файлов. При этом по умолчанию стандартно создаются индексные файлы для первичных ключей, для вторичных ключей индексные файлы создаются дополнительной командой CREATE INDEX, которая имеет следующий формат:

CREATE [UNIQUE] INDEX <имя_индекса> ON <имя_таблицы>

( <имя_столбца>[<признак упорядочения>] |

[,<имя_столбца>[<признак упорядочения>]...])

<имя_индекса > - уникальный идентификатор в системе.

<Признак упорядочениям:={ASC | DESC}

Здесь ASC — признак упорядочения по возрастанию, DESC — признак упорядочения по убыванию значений соответствующего столбца в индексе. Индекс может быть удален командой DROP, которая имеет следующий формат:

DROP INDEX <имя индекса>

Файловые структуры, используемые для хранения информации в базах данных

В каждой СУБД по-разному организованы хранение и доступ к данным, однако существуют некоторые файловые структуры, которые имеют общепринятые способы организации и широко применяются практически во всех СУБД.

В системах баз данных файлы и файловые структуры, которые используются для хранения информации во внешней памяти, можно классифицировать следующим образом (см. рис. 9.1).

Рис. 9.1. Классификация файлов, используемых в системах баз данных

С точки зрения пользователя, файлом называется поименованная линейная последовательность записей, расположенных на внешних носителях. На рис. 9.2 представлена такая условная последовательность записей.

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

В соответствии с методами управления доступом различают устройства внешней памяти с произвольной адресацией (магнитные и оптические диски) и устройства с последовательной адресацией (магнитофоны, стримеры).

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

В устройствах с последовательным доступом для получения доступа к некоторому элементу требуется «перемотать (пройти)» все предшествующие ему элементы информации. На устройствах с последовательным доступом вся память рассматривается как линейная последовательность информационных элементов (см. рис. 9.3).

Рис. 9.2. Файл как линейная последовательность записей

Рис. 9.3. Модель хранения информации на устройстве последовательного доступа

Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа.

В этих файлах физический адрес

В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).

Каждая файловая система СУФ — система управления файлами поддерживает некоторую иерархическую файловую структуру, включающую чаще всего неограниченное количество уровней иерархии в представлении внешней памяти (см. рис. 9.4).

Для каждого файла в системе хранится следующая информация:

имя файла;

тип файла (например, расширение или другие характеристики);

размер записи;

количество занятых физических блоков;

базовый начальный адрес;

ссылка на сегмент расширения;

способ доступа (код защиты).



Рис. 9.4. Иерархическая организация файловой структуры хранения

Для файлов с постоянной длиной записи адрес размещения записи с номером К может быть вычислен по формуле:

ВА + (К - 1) * LZ + 1,

где ВА — базовый адрес, LZ — длина записи.

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

На устройствах последовательного доступа могут быть организованы файлы только последовательного доступа.

Файлы с переменной длиной записи всегда являются файлами последовательного доступа. Они могут быть организованы двумя способами:

Конец записи отличается специальным маркером.

	Запись 1	X	Запись 2	X	ЗаписьЗ	X

В начале каждой записи записывается ее длина.

	LZ1	Запись!	LZ2	Запись2	LZ3	ЗаписьЗ

Здесь LZN — длина N-й записи.

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

в базах данных необходим поиск

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

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

NZ = F(K),

где NZ — номер записи, К — значение ключа, F( ) — функция.

Функция F() при этом должна быть линейной, чтобы обеспечивать однозначное соответствие (см. рис. 9.5).



Рис. 9.5. Пример линейной функции пересчета значения ключа в номер записи

Однако далеко не всегда удастся построить взаимно-однозначное соответствие между значениями ключа и номерами записей.

Часто бывает, что значения ключей разбросаны по нескольким диапазонам (см. рис. 9.6).



Рис. 9.6. Допустимые значения ключа

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

Суть методов хэширования состоит в том, что мы берем значения ключа ( или некоторые его характеристики) и используем его для начала поиска, то есть мы вычисляем некоторую хэш-функцию h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно-однозначного соответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска (количество дополнительных шагов) для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функции (то есть один адрес). Подобные ситуации называются коллизиями. Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.

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

выбрать хэш-функцию;

выбрать метод разрешения коллизий.

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

Файлы с неплотным индексом, или индексно-последовательные файлы

Попробуем усовершенствовать способ хранения файла: будем хранить его в упорядоченном виде и применим алгоритм двоичного поиска для доступа к произвольной записи. Тогда время доступа к произвольной записи будет существенно меньше. Для нашего примера это будет:

Т = log2KBO = log212500 = 14 обращений к диску.

И это существенно меньше, чем 12 500 обращений при произвольном хранении записей файла. Однако и поддержание основного файла в упорядоченном виде также операция сложная.

Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:

	Значение ключа первом записи блока		Номер блока с этой записью

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

Рис. 9.8. Пример заполнения индексной и основной области при организации неплотного индекса

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

Сначала определим размер индексной записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно двух байт. Тогда длина индексной записи будет равна:

LI = LK + 2 = 14 + 2 - 14 байт.

Тогда количество индексных записей в одном блоке будет равно:

KIZB = LB/LI = 1024/14 = 73 индексные записи в одном блоке.

Определим количество индексных блоков, которое

Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей:

KIB = KBO/KZIB = 12500/73 = 172 блока.

Тогда время доступа по прежней формуле будет определяться:

Тпоиска = log2KIB + 1 = log2172 + 1=8+1=9 обращений к диску.

Мы видим, что при переходе к неплотному индексу время доступа уменьшилось практически в полтора раза. Поэтому можно признать, что организация неплотного индекса дает выигрыш в скорости доступа.

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

Здесь механизм включения новой записи принципиально отличен от ранее рассмотренного. Здесь новая запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется.

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

Тдобавлений = log2N +1 + 1 обращений.

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

Файлы с плотным индексом, или индексно-прямые файлы

Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:

	Значение ключа		Номер записи

Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.

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

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

Тn = log2N,

где N — число элементов.

Однако в нашем случае является существенным только число обращений к диску при поиске записи по заданному значению первичного ключа.

в индексной области, где применяется

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

На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Поэтому нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. Зачем нужна единица? После поиска номера записи в индексной области мы должны еще обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом:

Тn = log2Nбл.инд. + 1.

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

Длина записи файла (LZ) — 128 байт. Длина первичного ключа (LK) — 12 байт. Количество записей в файле (KZ) — 100000. Размер блока (LB) — 1024 байт.

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

LI = LK + 4 = 14 + 4 = 16 байт.

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

KIZB = LB/LI = 1024/16 = 64 индексных записи в одном блоке. Теперь определим необходимое количество индексных блоков: KIB = KZ/KZIB = 100000/64 = 1563 блока.

в большую сторону, потому что

Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью.

А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи:

Тпоиска = log2KIB + 1 = log21563 + 1 = 11 + 1 = 12 обращений к диску.

Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом.

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

Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле:

КВО = KZ/(LB/LZ) - 100000/(1024/128) - 12500 блоков.

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

Рассмотрим, как осуществляются операции добавления и удаления новых записей.

При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):





Рис. 9.7. Пример организации файла с плотным индексом

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

к диску, которое требуется при

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

Тдобавления = log2N + 1 + 1 + 1.

Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках па область переполнения.

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

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

Физические модели баз данных

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

Однако механизмы буферизации и управления файловыми структурами не приспособлены для решения задач собственно СУБД, эти механизмы разрабатывались просто для традиционной обработки файлов, и с ростом объемов хранимых данных они стали неэффективными для использования СУБД. Тогда постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением данных на внешних носителях самой СУБД. И пространство внешней памяти уже выходило из-под владения СУФ и управлялось непосредственно СУБД. При этом механизмы, применяемые в файловых системах, перешли во многом и в новые системы организации данных во внешней памяти, называемые чаще страничными системами хранения информации. Поэтому наш раздел, посвященный физическим моделям данных, мы начнем с обзора файлов и файловых структур, используемых для организации физических моделей, применяемых в базах данных, а в конце ознакомимся с механизмами организации данных во внешней памяти, использующими страничный принцип организации.

Индексные файлы

Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД, и не попадаться на рекламные крючки.

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

Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.

В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Эти файлы имеют еще дополнительные названия, которые напрямую связаны с методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами.

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

Инвертированные списки

До сих пор мы рассматривали структуры данных, которые использовались для ускорения доступа по первичному ключу. Однако достаточно часто в базах данных требуется проводить операции доступа по вторичным ключам. Напомним, что вторичным ключом является набор атрибутов, которому соответствует набор искомых записей. Это означает, что существует множество записей, имеющих одинаковые значения вторичного ключа. Например, в случае нашей БД «Библиотека» вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в один год.

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

Инвертированный список в общем случае — это двухуровневая индексная структура. Здесь на первом уровне находится файл или часть файла, в которой упо-рядочепно расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепочка блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа.

И наконец, на третьем уровне находится собственно основной файл.

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

На рис. 9.11 представлен пример инвертированного списка, составленного для вторичного ключа «Номе]) группы» в списке студентов некоторого учебного заведения.

Для более наглядного представления мы

Для более наглядного представления мы ограничили размер блока пятью записями (целыми числами).



Рис. 9.11. Построение инвертированного списка по номеру группы для списка студентов

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

Следует отметить, что организация вторичных списков действительно ускоряет поиск записей с заданным значением вторичного ключа. Но рассмотрим вопрос модификации основного файла.

При модификации основного файла происходит следующая последовательность действий:

Изменяется запись основного файла.

Исключается старая ссылка на предыдущее значение вторичного ключа.

Добавляется новая ссылка на новое значение вторичного ключа.

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

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

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

Модели физической организации данных при бесфайловой организации

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

Это и послужило причиной того, что СУБД взяли на себя непосредственное управление внешней памятью. При этом пространство внешней памяти предоставляется СУБД полностью для управления, а операционная среда не получает непосредственного доступа к этому пространству.

Физическая организация современных баз данных является наиболее закрытой, она определяется как коммерческая тайна для большинства поставщиков коммерческих СУБД. И здесь не существует никаких стандартов, поэтому в общем случае каждый поставщик создает свою уникальную структуру и пытается обосновать ее наилучшие качества по сравнению со своими конкурентами. Физическая организация является в настоящий момент наиболее динамичной частью СУБД. Стремительно расширяются возможность устройств внешней памяти, дешевеет оперативная память, увеличивается ее объем и поэтому изменяются сами принципы организации физических структур данных. И можно предположить, что и в дальнейшем эта часть современных СУБД будет постоянно меняться. Поэтому при рассмотрении моделей данных, используемых для физического хранения и обработки, мы коснемся только наиболее общих принципов и тенденций.

При распределении дискового пространства рассматриваются две схемы структуризации: физическая, которая определяет хранимые данные, и логическая, которая определяет некоторые логические структуры, связанные с концептуальной моделью данных (рис. 9.12).

Рис. 9.12. Классификация объектов при статичной организации физической модели данных

Определим некоторые понятия, используемые в указанной классификации.

Чанк (chank) — представляет собой часть диска, физическое пространство на диске, которое ассоциировано одному процессу (on line процессу обработки данных).

Чанком может быть назначено неструктурированное

Чанком может быть назначено неструктурированное устройство, часть этого устройства, блочно-ориентированное устройство или просто файл UNIX.

Чанк характеризуется маршрутным именем, смещением (от физического начала устройства до начальной точки на устройстве, которая используется как чанк), размером, заданным в Кбайтах или Мбайтах.

При использовании блочных устройств и файлов величина смещения считается равной нулю.

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

Экстент — это непрерывная область дисковой памяти.

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

Первый экстент задается при создании нового объекта типа таблица, его размер задается при создании. EXTENTSIZE — размер первого экстента, NEXT SIZE — размер каждого следующего экстента.

Минимальный размер экстента в каждой системе свой, но в большинстве случаев он равен 4 страницам, максимальный — 2 Гбайтам.

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

При динамическом заполнении БД данными применяется специальный механизм адаптивного определения размера экстентов.

Внутри экстента идет учет свободных станиц.

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

Механизм удвоения размера экстента: если число выделяемых экстентов для процесса растет в пропорции, кратной 16, то размер экстента удваивается каждые 16 экстентов.

Например, если размер текущего экстента 16 Кбайт, то после заполнения 16 экстентов данного размера размер следующего будет увеличен до 32 Кбайт.

Совокупность экстентов моделирует логическую единицу — таблицу-отношение (tblspace).

Экстенты состоят из четырех типов страниц: страницы данных, страницы индексов, битовые страницы и страницы blob-объектов.

это сокращение Binary Larg Object,

Blob — это сокращение Binary Larg Object, и соответствует оно неструктурированным данным. В ранних СУБД такие данные относились к типу Memo. В современных СУБД к этому типу относятся неструктурированные большие текстовые данные, картинки, просто наборы машинных кодов. Для СУБД важно знать, что этот объект надо хранить целиком, что размеры этих объектов от записи к записи могут резко отличаться и этот размер в общем случае неограничен.

Основной единицей осуществления операций обмена (ввода-вывода) является страница данных. Все данные хранятся постранично. При табличном хранении данные на одной странице являются однородными, то есть станица может хранить только данные или только индексы.

Все страницы данных имеют одинаковую структуру, представленную на рис. 9.13.

Слот — это 4-байтовое слово, 2 байта соответствуют смещению строки на странице и 2 байта — длина строки. Слоты характеризуют размещение строк данных на странице. На одной странице хранится не более 255 строк. В базе данных каждая строка имеет уникальный идентификатор в рамках всей базы данных, часто называемый RowID — номер строки, он имеет размер 4 байта и состоит из номера страницы и номера строки на странице. Под номер страницы отводится

3 байта, поэтому при такой идентификации возможна адресация к 16 777 215 страницам.





Рис. 9.13. Обобщенная структура страницы данных

При упорядочении строк на страницах не происходит физического перемещения строк, все манипуляции происходят со слотами.

При переполнении страниц создается специальный вид страниц, называемых страницами остатка. Строки, не уместившиеся на основной странице, связываются (линкуются) со своим продолжением на страницах остатка с помощью ссылок-указателей «вперед» (то есть на продолжение), которые содержат номер страницы и номер слота на странице.

Страницы индексов организованы в виде В-деревьев. Страницы blob предназначены для хранения слабоструктурнровашюй информации, содержащей тексты большого объема, графическую информацию, двоичные коды.

Эти данные рассматриваются как потоки

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

Битовые страницы служат для трассировки других типов страниц. В зависимости от трассируемых страниц битовые страницы строятся по 2-битовой или 4-битовой схеме. 4-битовые страницы служат для хранения сведений о столбцах типа Varchar, Byte, Text, для остальных типов данных используются 2-битовые страницы.

Битовая структура трассирует 32 страницы. Каждая битовая структура представлена двумя 4-байтными словами. Каждая i-я позиция описывает одну i-ю страницу. Сочетание разрядов в i-х позициях двух слов обозначает состояние данной страницы: ее тип и занятость.

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

Журнал транзакций служит для управления корректным выполнением транзакций.

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

Моделирование отношений «один-ко-многим» на файловых структурах

Отношение иерархии является типичным для баз данных, поэтому моделирование иерархических связей является типичным для физических моделей баз данных.

Для моделирования отношений 1:М (один-ко-многим) и М:М (многие-ко-мно-гим) на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов.

Моделирование отношения 1:М с использованием однонаправленных указателей

В этом случае связываются два файла, например F1 и F2, причем предполагается, что одна запись в файле F1 может быть связана с несколькими записями в файле F2. Условно это можно представить в виде, изображенном на рис. 9.10.

Рис. 9.10. Иерархическая связь между файлами

При этом файл F1 в этом комплексе условно называется «Основным», а файл F2 — «зависимым» или «подчиненным». Структура основного файла может быть условно представлена в виде трех областей.

«Основной файл» F1.

Ключ

Запись

Сcылка-указатeль на первую запись в «Подчиненном» файле, с которой начинается цепочка записей файла F2, связанных с данной записью файла F1

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

Таким образом, каждая запись «подчиненного файла» делится на две области: область указателя и область, содержащую собственно запись.

Структура записи «подчиненного» файла.

	Указатель на следующую запись в цепочке		Содержимое записи

В качестве примера рассмотрим связь между преподавателями и занятиями, которые эти преподаватели проводят. В файле F1 приведен список преподавателей, а в файле F2 — список занятий, которые они ведут.

	F1
	Номер записи		Ключ и остальная запись		Указатель
	1		Иванов И. Н. ...		1
	2		Петров А. А.		3
	3		Сидоров П. А.		2
	4		Яковлев В. В.

<

В этом случае содержимое двух

	F2
	Номер записи	Указатель на следующую запись в цепочке	Содержимое записи
	1	4	4306 Вычислительные сети
	2	-	4307 Контроль и диагностика
	3	6	4308 Вычислительные сети
	4	5	84305 Моделирование
	5	-	4309 Вычислительные сети
	6	-	84405 Техническая диагностика
	7	-

В этом случае содержимое двух взаимосвязанных файлов F1 и F2 может быть расшифровано следующим образом: первая запись в файле F1 связана с цепочкой записей файла F2, которая начинается с записи номер 1, следующая запись номер 4 и последняя запись в цепочке — запись номер 5. Последняя — потому что пятая запись не имеет ссылки на следующую запись в цепочке. Аналогично можно расшифровать и остальные связи. Если мы проведем интерпретацию данных связей на уровне предметной области, то можно утверждать, что преподаватель Иванов ведет предмет « Вычислительные сети» в группе 4306, «Моделирование» в группе 84305 и «Вычислительные сети» в группе 4309.

Аналогично могут быть расшифрованы и остальные взаимосвязанные записи.

Алгоритм нахождения нужных записей «подчиненного» файла

Шаг 1. Ищется запись в «основном» файле в соответствии с его организацией (с помощью функции хэширования, или с использованием индексов, или другим образом). Если требуемая запись найдена, то переходим к шагу 2, в противном случае выводим сообщение об отсутствии записи основного файла.

Шаг 2. Анализируем указатель в основном файле если он пустой, то есть стоит прочерк, значит, для этой записи нет ни одной связанной с ней записи в «подчиненном файле», и выводим соответствующее сообщение, в противном случае переходим к шагу 3.

Шаг 3. По ссылке-указателю в найденной записи основного файла переходим прямым методом доступа по номеру записи на первую запись в цепочке «Подчиненного» файла. Переходим к шагу 4.

Шаг 4. Анализируем текущую запись на содержание если это искомая запись, то мы заканчиваем поиск, в противном случае переходим к шагу 5.

Анализируем указатель на следующую запись

Шаг 5. Анализируем указатель на следующую запись в цепочке если он пуст, то выводим сообщение, что искомая запись отсутствует, и прекращаем поиск, в противном случае по ссылке-указателю переходим на следующую запись в «подчиненном файле» и снова переходим к шагу 4.

Использование цепочек записей позволяет эффективно организовывать модификацию взаимосвязанных файлов.

Алгоритм удаления записи из цепочки «подчиненного» файла

Шаг 1. Ищется удаляемая запись в соответствии с ранее рассмотренным алгоритмом. Единственным отличием при этом является обязательное сохранение в специальной переменной номера предыдущей записи в цепочке, допустим, это переменная NP.

Шаг 2. Запоминаем в специальной переменной указатель на следующую запись в найденной записи, например, заносим его в переменную NS. Переходим к шагу 3.

Шаг 3. Помечаем специальным символом, например символом звездочка (*), найденную запись, то есть в позиции указателя на следующую запись в цепочке ставим символ «*» — это означает, что данная запись отсутствует, а место в файле свободно и может быть занято любой другой записью.

Шаг 4. Переходим к записи с номером, который хранится в NP, и заменяем в ней указатель на содержимое переменной NS.

Для того чтобы эффективно использовать дисковое пространство при включении новой записи в «подчиненный файл», ищется первое свободное место, т. е. запись, помеченная символом «*», и на ее место заносится новая запись, после этого производится модификация соответствующих указателей. При этом необходимо различать 3 случая:

Добавление записи на первое место в цепочке.

Добавление записи в конец цепочки.

Добавление записи на заданное место в цепочке.

Задание для самостоятельной работы

Разработать алгоритмы добавления записи для всех трех случаев

Однако часто бывает необходимо просматривать цепочку подчиненных записей в двух направлениях: прямом и обратном. В этом случае применяют двойные указатели.

один указатель равен номеру первой

В «основном файле» один указатель равен номеру первой записи в цепочке записей «подчиненного файла», а второй — номеру последней записи.

В «подчиненном файле» один указатель равен номеру следующей записи в цепочке, а другой — номеру предыдущей записи в цепочке. Для первой и последней записей в цепочке один из указателей пуст, то есть равен пробелу.

Для нашего примера это выглядит следующим образом:

F1
Номер записи	Ключ и остальная запись	Указатель на первую запись	Указатель на последнюю запись
1	Иванов И. Н. ....	1	5
2	Петров А. А.	3	6
3	Сидоров П. А.	2	2
4	Яковлев В. В.

F2
Номер записи	Указатель на предыдущую запись в цепочке	Указатель на следующую запись в цепочке	Содержимое записи
1	-	4	4306 Вычислительные сети
2	-	-	4307 Контроль и диагностика
3	-	6	4308 Вычислительные сети
4	1	5	84305 Моделирование
5	4	-	4309 Вычислительные сети
6	3	-	84405 Техническая диагностика
7		-

Один файл («подчиненный» или «основной») может быть связан с несколькими другими файлами, при этом для каждой связи моделируются свои указатели. Связь двух основных файлов F1 и F2 с одним связующим файлом F3 моделируется на

	F1
	Ключ	Содержимое записи	Указатель на файл А

	F2
	Ключ	Содержимое	Указатель па файл А

	F3
	Цепочки для файла F1	Содержимое записи	Цепочки для файла F2

Организация индексов в виде B-tree (В-деревьев)

Калькированный термин «В-дерево», в котором смешивается английский символ «В» и добавочное слово на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать.

Встретив как-то термин «B-дерево», я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином.

Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.

Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanced) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин «сбалансированное» от английского «balanced» — «сбалансированный, взвешенный» и дал название данному методу организации индекса.

Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.

На первом уровне число блоков равно числу блоков основной области, это нам известно, — оно равно 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс.

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

в одном блоке нам тоже

Количество индексных записей в одном блоке нам тоже известно, и оно равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока.

КIВ3 = KIB2/KZIB = 172/73 = 3 блока

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

И над третьим уровнем строим новый, и на нем будет всего один блок, в котором будет всего три записи. Поэтому число уровней в построенном дереве равно четырем, и соответственно количество обращений к диску для доступа к произвольной записи равно четырем (рис. 9.9). Это не максимально возможное число обращений, а всегда одно и то же, одинаковое для доступа к любой записи.

Тд= Rуравн. =4

1 уровень 12500 блоков

2 уровень 172 блоков

3 уровень 3 блоков

4 уровень 1 блоков



Рис. 9.9. Построенное В-дерево

Механизм добавления и удаления записи при организации индекса в виде В-дерева аналогичен механизму, применяемому в случае с неплотным индексом.

И наконец, последнее, что хотелось бы прояснить, — это наличие вторых названий для плотного и неплотного индексов.

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

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

Организация стратегии свободного замещения

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

После перемещения «незаконной» записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов. Механизмы удаления записей во многом аналогичны механизмам удаления в стратегии с областью переполнения. Однако еще раз кратко опишем их. Если удаляемая запись является первой записью в цепочке синонимов, то после удаления на ее место перемещается следующая (вторая) запись из цепочки синонимов и проводится соответствующая корректировка указателя третьей записи в цепочке синонимов, если таковая существует.

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

Стратегия разрешения коллизий с областью переполнения

Первая стратегия условно может быть названа стратегией с областью переполнения. При выборе этой стратегии область хранения разбивается на 2 части:

основную область;

область переполнения.

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

Основная область:

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

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

Рассмотрим теперь механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.

При поиске записи также сначала вычисляется значение ее хэш-функции и считывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись. Скорость поиска зависит от длины цепочки синонимов, поэтому качество хэш-функции определяется максимальной длиной цепочки синонимов. Хорошим результатом может считаться наличие не более 10 синонимов в цепочке.

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

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

MS SQL Server логическая

В версии 6.0 и 6. 5 MS SQL Server логическая структура хранения рассматривается в следующей иерархии [1]. Файлы операционной системы представляются как устройства для хранения БД (Device), устройства нумеруются. Сервер может управлять 256 устройствами. Главное устройство называется MASTER: на нем хранятся системные базы данных: Master, Model, Pubs, TempDb.

Устройство Master имеет номер 0 — ноль.

Каждое устройство разбивается не более чем на 16 777 216 виртуальных страниц по 2 Кбайта (Virtual page), максимальный размер устройства 32 Гбайт.

Первые 4 страницы устройства Master заняты под блок конфигурации (Confi,-guration block) — там хранятся все параметры конфигурации сервера. На устройствах размещаются конкретные базы. На каждом устройстве может быть размещено несколько баз, но и одна база может быть размещена на нескольких устройствах.

Каждая страница БД имеет свой уникальный номер. Физически используются 3 единицы хранения данных:

страница;

блок (extent) — 16Кб из 8 следующих друг за другом страниц;

единица размещения (Allocation Unit) — 512 Кб из 32 последовательных блоков (256 страниц).

При создании новой базы данных пространство для нее отводится единицами размещения. Минимальный объем базы данных для данной версии сервера равен 1 Мбайт, то есть составляет 2 единицы размещения.

Страницы бывают пяти типов:

страницы размещения (Allocation page);

страницы данных (Data page);

индексные страницы (Index page);

текстовые страницы (Text/image page);

статистические страницы (Distribution page).

Любая страница имеет заголовок, занимающий 32 байта. Заголовок содержит номер страницы, номера предыдущей и следующей страниц, идентификатор объекта — владельца страницы и сведения о свободном пространстве на странице. Как видно из заголовка, страницы связаны в двунаправленный список.

Первая страница каждой единицы размещения является страницей размещения. Таким образом, все страницы, кратные 256, начиная с 0 являются страницами размещения. Они хранят информацию, необходимую для управления размещением страниц внутри единицы размещения.

байтовых структуры, по одной на

Страница размещения содержит 32 16- байтовых структуры, по одной на каждый блок. Каждая структура содержит следующую информацию:

идентификатор объекта—владельца блока;

номер следующего блока в цепи;

номер предыдущего блока в цепи;

битовую карту распределения блока (Allocation bitmap);

битовую карту перераспределения блока (Deallocation bitmap);

идентификатор индекса (если таковой есть), размещенного на блоке;

статус.

Битовая карта распределения блока хранится в единственном байте, каждый бит которого соответствует одной странице блока. Если бит равен 1, то страница в данный момент содержит данные, если 0 — то страница свободна.

Карта перераспределения применяется для отслеживания страниц, которые освобождаются в течение транзакций. Реально страница помечается как пустая только после успешной фиксации (завершения) транзакции. Это делается, чтобы другие транзакции не обращались к странице до подтверждения того факта, что она освобождена.

Все страницы в блоке могут использоваться только одной таблицей или ее индексом. Это означает, что таблица может занимать минимально 1 блок — 16 Кбайт, даже если она содержит всего несколько строк.

Страницы данных используются для хранения собственно данных. Структурно страницу данных можно подразделить на три зоны: заголовок, строки данных и таблицу смещения (см. рис. 9.14).



Рис. 9.14. Структура страницы данных для MS SQL Server 6.5

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

Страницы данных, относящиеся к одной таблице, объединяются в двунаправленный список и организуют цепочки.

Данные хранятся на страницах в виде строк (кортежей). Каждая строка данных кроме собственно данных хранит дополнительную форматирующую информацию. Длина строки зависит от определения полей таблицы и конкретных данных в ней. Независимо от объявления, каждая строка имеет номер и поле с количеством полей переменной длины (к ним относятся также поля, допускающие

Оба эти поля имеют размер

неопределенные значения NULL). Оба эти поля имеют размер по одному байту, следовательно, количество строк на странице не превышает 256, а на количество полей также существует внешнее ограничение 250 полей в одной таблице. Структура строки таблицы приведена на рис. 9.15.



Рис. 9.15. Структура строки данных для MS SQL Server 6.5

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

Таблица смещений (Column offset table) состоит из:

таблицы подстройки смещений (Offset table adjust bytes) — но 1 дополнительному байту на каждое поле, смещение которого превышает 256 плюс 1 байт;

указателя на местоположение таблицы смещений;

указателя на местоположение полей переменной длины (1 байт на каждое поле).

Указатели занимают два последних байта в каждой структуре и поэтому они доступны для анализа.

Таблица смещения строк

Местоположение строки на странице определяется таблицей смешения строк (Row offset table). Таблица располагается в самом конце страницы и забирает дополнительно по 2 байта па каждую строку данных (см. рис. 9.16). Чтобы найти строку с заданным номером, SQL Server считывает из соответствующей ячейки смещение, которое и является адресом требуемой строки. Ячейка таблицы однозначно связана с определенным номером строки.

Удаленные строки имеют нулевое смещение. Поэтому из примера на рис. 9.16 видно, что строки 1 и 4 удалены.

У этой модели есть недостаток. После удаления строки в таблице смещения все равно остается ссылка на нее, которая занимает 1 байт. Однако при добавлении новой строки SQL Server проверяет таблицу смещений и ищет нулевое смещение, и новой строке присваивается номер удаленной, а в соответствующую ячейку таблицы смещений заносится адрес новой строки.

В SQL Server 6.5 используется понятие кластерного индекса. В таблице, для которой создается кластерный индекс, данные хранятся строго упорядочение) по полю, для которого создан этот кластерный индекс. Это поле (или набор полей) является первичным ключом таблицы или обладает свойством уникальности.

с кластерным индексом вводится параметр,

При заполнении таблиц с кластерным индексом вводится параметр, соответствующий проценту заполнения страницы (fill-factor). Если страница заполнена, то данные заносятся на последнюю страницу в цепочке страниц, занятых этой таблицей.



Рис. 9.16. Пример заполнения таблицы смещения строк

Некластерный индекс хранится отдельно от данных.

Текстовые страницы предназначены для хранения данных типа Next или Image.

На одной текстовой странице хранятся только данные одной строки основной таблицы (см. рис. 9.17). В основной таблице в соответствующем месте хранится только ссылка на соответствующую текстовую страницу. Если неструктурированные данные не умещаются на одной странице, то они образуют цепочку взаимосвязанных страниц.



Рис. 9.17. Хранение текстовых данных

В новой версии сервера баз

В новой версии сервера баз данных фирма Microsoft реализовала абсолютно новый механизм хранения.

SQL Server 7.0 организует следующую иерархию хранения:

База данных — некоторый объем физического пространства, на котором размещаются данные, принадлежащие одной логической базе данных.

Файл. Каждая база данных содержит не менее двух файлов. Один из них отводится под журнал транзакций. И в отличие от версии 6.5 в новой версии журнал транзакций не может располагаться в одном файле с данными. И еще одно принципиальное отличие — в новой версии каждый файл может принадлежать только одной базе данных, у нас не может быть разделяемых файлов.

Страница. Файлы делятся на страницы размером по 8 Кбайт каждая. Логический номер страницы складывается из внутреннего номера базы данных, номера файла и номера страницы в файле. В рамках БД файлы нумеруются, начиная с 1, и так же нумеруются страницы в рамках файла.

Блоки (экстенты, extents). Пространство под объекты отводится блоками по 8 следующих друг за другом страниц. Блок является основной единицей отведения пространства. Поэтому при создании БД можно указывать размер файла с точностью до 64 Кбайт. Для суперкомпьютеров заложена возможность увеличения размера блоков до 128 страниц.

В отличие от версии 6.5 объекты БД не обязательно занимают целый блок. На начальном этапе заполнения объект может занимать внутри блока несколько страниц. Поэтому существуют два типа блоков:

Однородные (Uniform). Все страницы однородного блока принадлежат одному объекту БД.

Смешанные (Mixed). Разные страницы в блоке принадлежат разным объектам.

Когда объект создается, то обычно его первые страницы отводятся в смешанном блоке, по мере роста объекта он уже размещается в однородных блоках.

В SQL 7.0 существуют уже 7 типов страниц:

страница данных (Data page);

индексные страницы (Index page);

страницы журнала транзакций (Log page);

текстовые страницы (Text/image page);

карты распределения блоков (Global allocation map page);

Все страницы имеют заголовок размером

карты свободного пространства (Page free space page);

индексные карты размещения (Index allocation map page).

Все страницы имеют заголовок размером 96 байтов. В заголовке хранится общая информация, используемая ядром СУБД для работы со страницами. На странице в отличие от блока хранится однородная информация. Поэтому среди параметров страницы задаются:

номер страницы в формате <номер файла, номер страницы>;

идентификатор объекта, которому принадлежит страница;

номер индекса, которому принадлежит страница;

уровень внутри индексного дерева, которому принадлежит страница;

количество отведенных строк на странице, количество заполненных слотов;

общий объем свободного пространства на странице;

указатель на расположение свободного пространства после последней строки на странице;

минимальная длина строки на странице;

объем зарезервированного пространства.

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

Новыми в архитектуре дисковой памяти являются страницы размещения. В этих страницах хранятся сведения о размещении данных. SQL Server 7.0 использует три типа страниц размещения: карты распределения блоков, карты свободного пространства, индексные карты размещения. SQL Server 7.0 хранит информацию размещения на разных уровнях: на уровне блоков, на уровне страниц, на уровне объектов. Такой разносторонний мониторинг помогает СУБД оптимизировать работу в соответствии с требованиями конкретного запроса.

Карты распределения блоков

В данных картах хранится информация о распределении блоков. Карта распределения блоков состоит из стандартного заголовка и одного битового массива в 64 000 битов. Каждый бит характеризует один блок. Поэтому одна страница карты распределения описывает пространство в 64 000 блоков или 4 Гбайт данных.

Карты распределения блоков делятся на два типа:

Глобальная карта распределения (Global allocation map, GAM) хранит информацию об использовании блоков.

в 0, то блок занят

Если бит установлен в 0, то блок занят данными, если в 1 — то блок свободен.

Вторичная глобальная карта распределения (Secondary global allocation map, SGAM) хранит информацию о типе блоков. Если бит установлен в 1, то блок смешанный и минимум одна страница в нем свободна, в остальных случаях (блок свободен, блок смешанный, но свободных страниц нет, блок однородный) бит равен 0.

При отведении пространства сервер использует обе карты распределения.

Карты свободного пространства

Степень заполнения страниц в SQL 7.0 отслеживает специальный механизм — карты свободного пространства (Page free space page, PFS). Каждая PFS-страни-ца хранит информацию о 8000 страниц, по 1 байту на страницу. Каждый байт представляет собой битовую карту, которая сообщает о степени занятости страницы и о том, принадлежит ли она объекту.

Первые страницы файла БД всегда используются под карты распределения. Страница № 1 состоит из двух частей. После стандартного заголовка страницы следует заголовок файла, содержащий его описание, затем размешается блок PFS. Страницы PFS повторяются через каждые 8000 страниц, если размер файла

превосходит один блок. Страница № 2 — это GAM, страница № 3 — это SGAM. Карты распределения блоков повторяются через каждые 512 000 страниц. Кроме того, каждая девятая страница первичного файла — это загрузочная страница БД (database boot page), содержащая описание БД и параметры конфигурации.

Карты размещения

Для организации связи между блоками и расположенными на них объектами используются индексные карты размещения (Index Allocation Map, IАМ). Каждая таблица или индекс имеют одну или более страниц IАМ. В каждом файле, в котором размещаются таблица или индекс, существует минимум одна карта размещения для этой таблицы или индекса. Страницы IАМ размещаются про,-извольно внутри файла и отводятся по мере необходимости. IAM объединены друг с другом в цепочку двунаправленными ссылками. Указатель на первую карту размещения содержится в поле FirstIAM системной таблицы Sysindex.

Каждая IAM описывает некоторый диапазон

Каждая IAM описывает некоторый диапазон блоков и представляет собой битовую карту: если бит установлен в 1, то в данном блоке есть страницы, принадлежащие данному объекту, если в 0 — то нет.

Все страницы размещения не связаны напрямую с некоторым объектом БД, они соответствуют некоторой системной информации, поэтому параметр «идентификатор объекта» для всех этих страниц одинаков и равен 99.

Страницы данных

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

Прежде всего стоит отметить, что в отличие от SQL Server 6.5 в новой версии страницы данных не связаны друг с другом в цепочки. За связь между страницами и объектами отвечает новая специальная структура — карты размещения.

Кроме того, ранее данные на странице хранились непрерывно. При удалении строки данные внутри страницы перемещались так, чтобы не оставалось пустот. Однако такой подход затруднял строчные блокировки. И в новой версии данные на странице не обязательно хранятся непрерывно. Здесь допустимы пропуски. При удалении строки пустое пространство помечается и потом его может занять новая строка, но перемещения строк не происходит.

В SQL Server 7.0 теперь поддерживается классический термин слот (Slot), и это место размещения строки на странице. Если таблица не имеет кластеризованного индекса, то номер слота является идентификатором строки и не меняется, пока не будет удалена соответствующая строка. Если же таблица имеет кластеризованный индекс, то слоты располагаются в порядке, задаваемом индексом.

Строки данных

Строки данных претерпели существенное изменение. Отметим наиболее важные моменты.

Номера строки больше нет — строка идентифицируется номером слота, который ее определяет, либо значением кластерного ключа.

В версии 6.5 поля, допускающие NULL, хранятся точно так же, как поля переменной длины.

поля фиксированной длины всегда

В версии 7. 0 поля фиксированной длины всегда занимают свою полную длину, значение NULL задается специальным флагом. Это облегчает замену неопределенного значения на некоторое конкретное без перемещения строк на странице.

Фиксированные поля вместе с описателями хранятся до полей переменной длины, так же как и в 6.5.

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

Максимальное количество полей в строке 1024, в версии 6.5 только 256.

Текстовые страницы

В версии 7.0 изменены принципы хранения текстовых полей. Строки данных по-прежнему содержат 16-байтные указатели на текстовые данные. Однако хранение самих текстовых данных производится иначе.

Текстовая страница теперь может содержать несколько текстовых полей. Собственно данные хранятся в виде сбалансированного дерева (B-tree). Строка данных содержит указатель на корневую структуру (Root structure) размером 84 байта.

Данные длиной менее 64 байт хранятся в корневой структуре. Для данных до 32 Кбайт корневая структура (Root structure) может адресовать 4 блока данных (это не блоки страниц) до 8 Кбайт каждый. Блоки наращиваются до 8 Кбайт (реально на одной текстовой странице может быть размещено 8080 байт). Например, если первая порция данных составляет 4 Кбайта, то отводится один блок. Если в дальнейшем данные увеличиваются до 6 Кбайт, то первый блок увеличивается до 6 Кбайт, а второй блок имеет размер всего 2 Кбайта.

Если же длина текстового поля более 32 Кбайт, то строятся промежуточные узлы.

В версии 7.0 текстовая страница может содержать данные нескольких текстовых полей (рис. 9.18).

Страницы журнала транзакций

В отличие от версии 6.5 в новой версии под журнал транзакций отводится всегда отдельный файл. В предыдущей версии журнал транзакций являлся системной таблицей и хранился в системном сегменте LOG. Несмотря на настоятельные рекомендации располагать журнал транзакций и файлы базы данных на разных физических устройствах, СУБД автоматически не контролировала этот факт.В новой версии журнал транзакций всегда хранится в отдельном файле.



Рис. 9.18. Пример хранения текстовых данных на одной странице

Вопросы для самостоятельной работы

Сравнить обе стратегии и определить, какая из них будет наиболее перспективной и в каких случаях.

Разработать алгоритмы удаления записей для первой и второй стратегий. Показать, как определяются ссылки.

---

---