Введение в СУБД

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

1. Общая схема обработки запроса

Можно представить, что обработка поступившего в систему запроса состоит из фаз, изображенных на рисунке 1.

Рисунок 1.
Фазы обработки запроса.

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

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

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

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

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

2. Синтаксическая оптимизация запросов

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

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

2.1. Простые логические преобразования запросов

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

Канонические представления могут быть различными для предикатов разных типов. Если предикат включает только одно имя поля, то его каноническое представление может, например, иметь вид имя поля op константное арифметическое выражение (эта форма предиката - простой предикат селекции - очень полезна при выполнении следующего этапа оптимизации). Если начальное представление предиката имеет вид (a+5)*A op 36 (малыми буквами обозначены имена объемлющих переменных, а большими - имена полей отношений), то каноническим представлением такого предиката может быть A op 36/(a+5). Если предикат включает в точности два имени поля разных отношений (или двух разных вхождений одного отношения), то его каноническое представление может иметь вид имя поля op арифметическое выражение, где арифметическое выражение в правой части включает только константы и второе имя поля (это тоже форма, полезная для выполнения следующего шага оптимизации, - предикат соединения; особенно важен случай эквисоединения, когда op - это равенство). Если в начальном представлении предикат имеет вид 5*A a*B op b, то его каноническое представление - A op (b+a*B)/5.

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

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

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

При приведении логического условия к каноническому представлению можно производить поиск общих предикатов (они могут существовать изначально, могут появиться после приведения предикатов к каноническому виду или в процессе нормализации логического условия) и упрощать логическое выражение за счет, например, выявления конъюнкции взаимно противоречащих предикатов. Фрагмент логического выражения ...(A>5)AND(A<5)... можно заменить на ...FALSE... Возможны и более "умные" упрощения. Например, фрагмент логического выражения ...(A>B)AND(B=5)... можно заменить на ...(A>5)AND(B=5)... Такие упрощения могут оказаться существенными для дальнейшей обработки запроса: в запросе с логическим условием первого вида предполагалось соединение отношений; после преобразования запрос уже не требует соединения.

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

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

(A JOIN B) WHERE restriction-on-A

AND restriction-on-B

эквивалентно выражению

(A WHERE restriction-on-A) JOIN

(B WHERE restriction-on-B).

Здесь JOIN обозначает реляционный оператор естественного соединения отношений; A WHERE restriction - оператор ограничения отношения A в соответствии с предикатом restriction.

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

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

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

2.3. Приведение запросов с вложенными подзапросами к запросам с соединениями

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

Ниже R_i обозначает i-е отношение базы данных; C_k - k-е поле (столбец) отношения.

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

1. Простые предикаты. Это предикаты вида R_i.C_k op X, где X - константа или список констант, и op - оператор скалярного сравнения (=, <>, >, >=, <, <=) или оператор проверки вхождения в множество (IS IN, IS NOT IN).

2. Предикаты с вложенными подзапросами. Это предикаты вида R_i.C_k op Q, где Q - блок запроса, а op может быть таким же, как для простых предикатов. Предикат может также иметь вид Q op R_i.C_k. В этом случае оператор принадлежности к множеству заменяется на CONTAINS или DOES NOT CONTAIN. Эти две формы симметричны. Достаточно рассматривать только одну.

3. Предикаты соединения. Это предикаты вида R_i.C_k op R_j.Cn, где R_i ґ R_j и op - оператор скалярного сравнения.

4. Предикаты деления. Это предикаты вида Q_i op Q_j, где Q_i и Q_j - блоки запросов, а op может быть оператором скалярного сравнения или оператором проверки вхождения в множество.

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

Каноническим представлением запроса на n отношениях называется запрос, содержащий n-1 предикат соединения и не содержащий предикатов с вложенными подзапросами. Фактически, каноническая форма - это алгебраическое представление запроса.

Ниже приводятся два примера канонических форм запросов с предикатами разного типа. Соответствующая техника существует и для других видов предикатов.

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN

SELECT Rj.Cm FROM Rj WHERE Ri.Cn = Rj.Cp

эквивалентно

SELECT Ri.Ck FROM Ri, Rj WHERE

Ri.Ch = Rj.Cm AND Ri.Cn = Rj.Cp

SELECT Ri.Ck FROM Ri WHERE

Ri.Ch =SELECT AVG (Rj.Cm) FROM Rj WHERE

Rj.Cn = Ri.Cp

эквивалентно

SELECT Ri.Ck FROM Ri, Rt WHERE

Ri.Ch = Rt.Cm AND Ri.Cp = Rt.Cn, где

Rt (Cp, Cn) = SELECT Rj.Cp, AVG (Rj.Cn) FROM Rj

GROUP BY Rj.Cp

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

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

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

3. Семантическая оптимизация запросов

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

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

3.1. Преобразования запросов на основе семантической информации

В качестве начальных примеров преобразований запросов на основе семантической информации рассмотрим подходы известных СУБД System R и INGRES к обеспечению работы с базами данных через представления. Эти преобразования не были ориентированы на оптимизацию запросов, но имеют к ней непосредственное отношение.

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

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

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

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

DEFINE VIEW V (C2) AS

SELECT C1 FROM R WHERE C1 > 6.

Запрос формулируется следующим образом:

SELECT C2 FROM V WHERE C2 < 6.

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

SELECT C1 FROM R WHERE C1 < 6 AND C1 >6.

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

SELECT C1 FROM R WHERE FALSE,

из чего следовало бы, что результат запроса пуст.

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

Другим примером преобразований запросов, имеющих непосредственное отношение к оптимизации, являются преобразования запросов на модификацию базы данных для удовлетворения существующих в базе данных ограничений целостности. Этот подход впервые был применен в СУБД INGRES, но используется и в других системах, например А в System R.

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

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

Пусть база данных, характеризующая структуру организации, состоит из отношений EMP и DEPT. В отношении EMP регистрируются служащие организации. Схема этого отношения EMP (EMP#, EMPNAME, DEPT#); поле EMP# содержит уникальный номер служащего, поле EMPNAME - имя служащего, а DEPT# - номер отдела организации, в котором работает данный сотрудник. Отношение DEPT хранит информацию об отделах и имеет схему DEPT (DEPT#, EMPCOUNT), где в поле EMPCOUNT хранится общее число сотрудников данного отдела. Пусть задано ограничение целостности

ASSERT B IMMEDIATE ON EMP: EMP.DEPT# = 6.

Это ограничение означает запрещение занесения, удаления и модификации кортежей в отношении EMP со значением поля DEPT#, отличным от 6. Пусть обрабатывается запрос на удаление кортежа

DELETE EMP WHERE EMPNAME = "Brown".

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

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

DELETE EMP WHERE EMPNAME = "Brown" AND DEPT# = 6.

При выполнении такого запроса не понадобятся дополнительные вызовы проверок ограничений целостности второго типа, поскольку они все уже включены в логическое условие выполнения операции удаления. Кроме того, оптимизатор получает большую свободу в выборе способа выполнения запроса. Например, если отделы малочисленны и для отношения EMP поддерживается индекс на поле DEPT#, то, возможно, наиболее оптимальным способом выполнения запроса будет сканирование отношения через индекс по DEPT# с условием DEPT# = 6 с удалением всякого выбираемого таким образом кортежа со значением поля EMPNAME, равным "Brown". Тем самым преобразующие запрос действия, не направленные специально на оптимизацию, могут способствовать более эффективному выполнению запроса. Эффективность выполнения запроса удается повысить за счет использования знаний, независимо хранящихся в базе данных.

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

3.2. Использование семантической информации при оптимизации запросов

Семантическая оптимизация основана на наличии в базе данных семантической информации, которую необязательно использовать при обработке запроса, но применение которой может привести к его более оптимальному выполнению. Если семантическая оптимизация имеет дело только со знаниями, представленными в виде ограничений целостности базы данных, то при семантической оптимизации производится множество преобразованных внутренних представлений запроса; при каждом преобразовании используется некоторый поднабор ограничений целостности. Если, например, в базе данных определены два ограничения целостности A и B с логическими условиями F1 и F2 и обрабатывается запрос с условием выборки F, то в ходе семантической оптимизации будут получены внутренние представления, эквивалентные запросам с условиями F, F AND F1, F AND F2 и F AND F1 AND F2.

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

Для разумного применения семантической оптимизации удобно представлять ограничения целостности базы данных в импликативной форме. Тогда можно добиться более осмысленного порядка преобразований. Пусть, например, в нашей базе данных о структуре организации отношение EPM расширено полями STATUS и SALARY. Значения поля STATUS характеризуют должность служащего, а поле SALARY - его оклад. Может быть наложено ограничение целостности, выражающееся в том, что оклад, превышающий 40000, допустим только для начальников отделов:

ASSERT A ON EMP:

IF SALARY > 40.000 THEN STATUS = "Manager".

Предположим, что обрабатывается запрос

SELECT EMPNAME, STATUS FROM EMP

WHERE SALARY = 20.000.

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

SELECT EMPNAME, STATUS FROM EMP

WHERE SALARY > 40.000

правило преобразования применимо и приводит к семантически эквивалентному запросу

SELECT EMPNAME, STATUS FROM EMP

WHERE STATUS = "Manager",

выполнение которого может быть более эффективным.

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

4. Выбор и оценка альтернативных планов выполнения запросов

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

Процедурным представлением или планом выполнения запроса называется такое его представление, в котором детализирован порядок выполнения операций доступа к базе данных физического уровня. Как правило, в реляционных СУБД выделяется подсистема управления данными на физическом уровне. В System R такая подсистема называется RSS (Relational Storage System) и обеспечивает простой интерфейс, позволяющий последовательно просматривать кортежи отношений, удовлетворяющие заданным условиям на значения полей, с использованием индексов или простым сканированием страниц базы данных. Кроме того, RSS позволяет производить отсортированные временные файлы и заносить, удалять и модифицировать индивидуальные кортежи. Аналогичные подсистемы явно или неявно выделяются во всех подобных СУБД.

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

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

4.1. Генерация планов

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

SELECT EMPNAME FROM EMP WHERE

DEPT# = 6 AND SALARY > 15.000

может выполняться последовательным сканированием отношения EMP с выбором кортежей с DEPT# = 6 и SALARY > 15.000; сканированием отношения через индекс I1, определенный на поле DEPT#, с условием доступа к индексу DEPT# = 6 и условием выборки кортежа SA ARY > 15.000; наконец, сканированием отношения через индекс I2, определенным на поле SALARY, с условием доступа к индексу SALARY > 15.000 и условием выборки кортежа DEPT# = 6.

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

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

SELECT R1.C1, R2.C2, R3.C3 FROM R1, R2, R3

WHERE R1.C4 = R2.C5 AND R2.C5 = R3.C6.

Тогда, если в плане запроса выбирается порядок выполнения соединений сначала R1 с R2, а затем полученного временного отношения - с R3, и при этом для выполнения первого соединения выбирается метод сортировок со слиянием, то временное отношение будет заведомо отсортировано по C5, и одна сортировка не потребуется, если и второе соединение будет выполняться тем же методом.

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

4.2. Оценка стоимости плана запроса

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

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

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

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

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

Из этого следует важность показателя предиката ограничения, характеризующего долю кортежей отношения, которые удовлетворяют данному предикату, и называемого степенью селективности предиката. Степени селективности простых предикатов вида R.C op const, где R.C задает имя поля отношения базы данных, op - операция сравнения (=, <>, >, <, >=, <=), а const - константа, являются основой для оценок стоимости планов запроса. Точность оценок степеней селективности определяет точность общих оценок и правильность выбора оптимального плана запроса.

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

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

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

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

В каталогах базы данных для каждого отношения R сохраняется число кортежей в данном отношении (T) и число блоков внешней памяти, в которых располагаются кортежи отношения (N); для каждого поля C отношения хранятся число различных значений этого поля (CD), минимальное хранимое значение этого поля (CMin) и максимальное значение (CMax).

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

Тогда

SEL (R.C = const) = CD / (CMax - CMin)

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

SEL (R.C > const) = (CMax - const) / (CMax - CMin)

и т. д.

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

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

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

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

4.3. Более точные оценки

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

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

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

При традиционном подходе область значений поля разбивается на N интервалов равного размера, и для каждого интервала подсчитывается число значений полей из кортежей данного отношения, попадающих в интервал. Предположим, что EMP расширено еще одним полем AGE - возраст сотрудника. Пусть всего в организации работает 100 сотрудников в возрасте от 10 до 60 лет. Тогда гистограмма, изображающая распределение значений поля AGE, может иметь вид, показанный ниже на рисунке 2. Гистограмма построена исходя из разбиения диапазона значений поля AGE на 10 интервалов.

Рисунок 2.
Распределение значений поля AGE в отношении EMP.

Рассмотрим, как можно оценивать селективность простых предикатов, задаваемых на поле AGE, с использованием такой гистограммы. Пусть в интервал значений AGE S_i попадает K_iзначений. Тогда SEL (EMP.AGE = const), если значение константы попадает в интервал значений S_i, можно оценить следующим образом: 0 ґ SEL (EMP.AGE) ґ K_i/T (T - общее число кортежей в отношении EMP). Отсюда средняя оценка степени селективности предиката - K_i/(2* T). Например, SEL (AGE = 29) оценивается в 40/200 = 0.2, а SEL (AGE = 16) оценивается в 5/200 = 0.025. Это, конечно, существенно более точные оценки, чем те, которые можно получить, исходя из предположений о равномерности распределений. Но не так хорошо обстоят дела с оценками селективности простых предикатов с неравенствами.

Скажем, пусть требуется оценить степень селективности предиката EMP.AGE < const. Если значение константы попадает в интервал S_i, и SUM_i - суммарное количество значений AGE, попадающих в интервалы S₁, S₂, .., S_i, то

SUM_i-1/T ґ SEL (AGE < const) = SUM_i / T.

Тогда средняя оценка степени селективности (SUM_i-1 + SUM_i) / (2* T) и ошибка оценки могут достигать половины веса подобласти, в которую попадает значение константы предиката. Самое неприятное, что ошибка оценки зависит от значения константы, и тем больше, чем больше значений поля содержится в соответствующем интервале гистограммы. Например, SEL (AGE < 29) оценивается как 46/100 ґ SEL (AGE < 29) ґ 86/100, откуда оценка степени селективности (46 + 86)/200 = 0.66; при этом ошибка оценки может достигать 0.2. В то же время SEL (AGE < 49) оценивается существенно более точно.

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

Рисунок 3.
Псевдогистограмма распределения значений поля AGE. Интервалы выбраны так, что в каждый из них попадает одинаковое число значений.

Область значений поля AGE отношения EMP разбита на 10 интервалов таким образом, что в каждый интервал попадает ровно по 10 значений поля AGE. Интервалы имеют разные размеры. Граничные значения интервалов показаны над вертикальными линиями. В псевдогистограмме допустимы интервалы, правая и левая граница которых совпадают, например интервал (28, 28). Он образовался по причине наличия в отношении EMP большого (большего десяти) числа кортежей со значением AGE = 28.

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

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

Подход основывается на статистике Колмогорова, из которой применительно к случаю реляционных баз данных следует, что если из отношения выбирается образец из 1064 кортежей, и b - доля кортежей в образце со значениями поля C < V, то с достоверностью 99 доля кортежей во всем отношении со значениями поля C < V находится в интервале [b-0.05, b+0.05]. При уменьшении мощности образца достоверность, естественно, уменьшается.

Глава 12. Традиционные социальные методы в компьютерных технологиях, или СУБД в архитектуре клиент-сервер

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

1. Открытые системы

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

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

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

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

Технологии и стандарты открытых систем обеспечивают реальную и проверенную практикой возможность производства системных и прикладных программных средств со свойствами мобильности (portability) и интероперабельности (interoperability). Свойство мобильности означает сравнительную простоту переноса программной системы в широком спектре аппаратно-программных средств, соответствующих стандартам. Интероперабельность означает упрощение комплексирования новых программных систем на основе использования готовых компонентов со стандартными интерфейсами.

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

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

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

2. Клиенты и серверы локальных сетей

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

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

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

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

Примерами серверов могут служить:

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

Сервер локальной сети предоставляет ресурсы (услуги) рабочим станциям и/или другим серверам.

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

3. Системная архитектура клиент-сервер

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

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

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

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

Общим решением проблемы мобильности систем, основанных на архитектуре клиент-сервер, является опора на программные пакеты, реализующие протоколы удаленного вызова процедур (RPC - Remote Procedure Call). При использовании таких средств обращение к сервису в удаленном узле выглядит как обычный вызов процедуры. Механизм RPC, в котором, естественно, содержится вся информация о специфике аппаратуры локальной сети и сетевых протоколов, переводит вызов в последовательность сетевых взаимодействий. Тем самым специфика сетевой среды и протоколов скрыта от прикладного программиста.

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

Если система реализована на основе стандартного пакета RPC, она может быть легко перенесена в любую открытую среду.

4. Серверы баз данных

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

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

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

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

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

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

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

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

4.2. Преимущества протоколов удаленного вызова процедур

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

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

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

4.3. Типичное разделение функций между клиентами и серверами

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

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

4.4. Требования к аппаратным возможностям и базовому программному обеспечению клиентов и серверов

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

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

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

Глава 13. Мы не одни в этом мире, или Распределенные базы данных

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

При этом должны обеспечиваться:

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

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

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

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

Мы ограничимся рассмотрением проблем однородных распределенных СУБД на примере System R*.

2. Распределенная система управления базами данных System R*

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

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

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

Простота использования системы достигается за счет того, что пользователи System R* (разработчики прикладных программ и конечные пользователи) остаются в среде языка SQL, т. е. могут продолжать работать в тех же внешних условиях, что и в System R (и SQL/DS и DB2). Возможность применения SQL основывается на обеспечении System R* прозрачности местоположения данных. Система автоматически обнаруживает текущее местоположение упоминаемых в запросе пользователя объектов данных; одна и та же прикладная программа, включающая операторы SQL, может быть выполнена в разных узлах сети. При этом в каждом узле сети на этапе компиляции запроса выбирается наиболее оптимальный план выполнения запроса в соответствии с расположением данных в распределенной системе.

Обеспечению автономности узлов сети в System R* уделяется очень большое внимание. Каждая локальная база данных администрируется независимо от других. Возможны автономное подключение новых пользователей, смена версии автономной части системы и т. д. Система спроектирована таким образом, что в ней не требуются централизованные службы именования объектов или обнаружения тупиков. В индивидуальных узлах не требуется наличие глобального знания об операциях, выполняющихся в других узлах сети; работа с доступными базами данных может продолжаться при выходе из строя отдельных узлов сети или линий связи.

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

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

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

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

Для задания горизонтального разделения отношений в SQL была введена конструкция вида

DISTRIBUTE TABLE 
HORIZONTALLY INTO
WHERE 
IN SEGMENT 
.
.
WHERE 
IN SEGMENT

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

Вертикальное разделение производилось с помощью оператора

DISTRIBUTE TABLE 
VERTICALLY INTO
WHERE 
IN SEGMENT 
.
.
WHERE 
IN SEGMENT

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

Горизонтальное и вертикальное разделение отношений реально не применяются в Sys-tem R*, хотя очевидно, что выполнение собственно оператора DISTRIBUTE никаких технических трудностей не вызывает. Трудности возникают при обеспечении согласованности разделов. Кроме того, разделенные отношения очень трудно использовать. В соответствии с идеологией системы учет разделов отношения в разных узлах сети должен производить оптимизатор, т. е. количество потенциально возможных планов выполнения запросов, которые должны оцениваться оптимизатором, еще более возрастает. При том, что в распределенной системе число возможных планов и так очень велико, и оптимизатор работает на пределе сложности, разумным образом использовать разделенные отношения невозможно. Разработчики оптимизатора System R* не были в состоянии учитывать разделенность отношений. Поэтому было бессмысленно вводить в систему разделенные отношения. Для задания требования поддержки копий отношения в нескольких узлах сети предлагалось ввести новую конструкцию SQL

DISTRIBUTE TABLE 
REPLICATED INTO
IN SEGMENT 
.
.
IN SEGMENT

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

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

Создание мгновенного снимка состояния баз данных в соответствии с заданным запросом на выборку должно было производиться при помощи новой конструкции SQL

DEFINE SNAPSHOT 
()
AS 
REFRESHED EVERY

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

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

REFRESH SNAPSHOT .

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

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

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

Далее мы рассмотрим аспекты проекта System R*, которые нашли отражение в ее реализации и являются, на наш взгляд, наиболее интересными: средства именования объектов и организацию распределенного каталога баз данных; подход к распределенным компиляции и выполнению запросов; особенности использования представлений; средства оптимизации запросов; специфика управления транзакциями; средства синхронизации и распределенный алгоритм обнаружения синхронизационных тупиков.

2.1. Именование объектов и организация распределенного каталога

Напомним прежде всего, что полное имя отношения (базового или представления) в System R имеет вид

имя-пользователя.имя-отношения,

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

В System R* используется развитие этого подхода. Системное имя отношения включает четыре компонента: идентификатор пользователя-создателя отношения; идентификатор узла сети, в котором выполнялась операция создания отношения; локальное имя отношения, присвоенное ему при создании; идентификатор узла, в котором отношение располагалось непосредственно после своего создания (напомним, что отношение может перемещаться из одного узла в другой при выполнении операции MIGRATE).

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

Для определения синонимов SQL расширен оператором вида

DEFINE SYNONYM 
AS .

При выполнении такого оператора в локальный каталог заносится соответствующая информация.

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

Концепция распределенного каталога Sys-tem R* основана на наличии у каждого объекта распределенной базы данных уникального системного имени. Принято следующее соглашение: информация о размещении любого объекта базы данных (идентификатор текущего узла, в котором размещен объект) сохраняется в локальном каталоге того узла, в котором объект располагался непосредственно после создания (родового узла).

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

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

2.2. Распределенная компиляция запросов

Как мы уже отмечали, запросы на языке SQL до своего реального выполнения подвергаются компиляции. Как и в случае System R, компиляция запроса может производиться на стадии прекомпиляции прикладной программы, написанной на традиционном языке программирования (PL/1, Cobol, ассемблер) с включением операторов SQL, или в динамике выполнения транзакции при выполнении предложения PREPARE. С точки зрения пользователей, процесс компиляции в System R* приводит к тем же результатам, что и в System R: для каждого предложения SQL образуется программа в машинных кодах (секция модуля доступа), вызовы которой помещаются в текст исходной прикладной программы.

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

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

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

2. В главном узле генерируется глобальный план выполнения запроса, в котором учитывается лишь порядок взаимодействий узлов при реальном выполнении запроса. Для выработки глобального плана используется расширение техники оптимизации, применяемой в System R. Глобальный план отображается в преобразованном соответствующим образом дереве запроса.

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

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

2.3. Управление транзакциями и синхронизация

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

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

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

По отношению к особенностям реализации двухфазного протокола завершения транзакции в System R* заметим еще следующее. В качестве координатора выступает транзакция, выполняющаяся в главном узле, т. е. та, по инициативе которой возникли дополнительные транзакции. Тем самым наличие центрального координирующего узла не требуется, что соответствует требованию автономности узлов. Для откатов транзакций используется базовый механизм точек сохранения System R. Наконец, классический протокол двухфазного завершения оптимизирован, чтобы сократить число необходимых сообщений.

Как и в System R, согласованность состояния баз данных при параллельном выполнении нескольких транзакций в System R* обеспечивается на основе механизма синхронизационных захватов объектов базы данных при соблюдении двухфазного протокола захватов. Напомним, что это означает разбиение каждой транзакции, с точки зрения синхронизации, на две фазы - рабочую фазу, на которой захваты только устанавливаются, и фазу завершения, когда все захваты объектов базы данных, произведенные данной транзакцией, снимаются. Синхронизация производится в точности так же, как и в System R: каждая транзакция-участник обращается к локальной базе данных через RSS своего узла. Основной новой проблемой является проблема возможных распределенных тупиков, которые могут возникнуть между несколькими распределенными транзакциями, выполняющимися параллельно. (Тупики между транзакциями-участниками одной распределенной транзакции невозможны, поскольку все участники получают один общий идентификатор транзакции и не конфликтуют по синхронизации.) Для обнаружения распределенных синхронизационных тупиков в System R* применяется оригинальный распределенный алгоритм, не нарушающий требования автономности узлов сети и минимизирующий число передаваемых по сети сообщений и необходимую процессорную обработку.

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

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

3. Интегрированные или федеративные системы и мультибазы данных

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

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

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

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

Продолжение в следующем номере.

^*) Продолжение. Начало в СУБД # 1, 2, 3, 4, 1995; # 1, 2, 3, 1996.