Введение
Основные понятия
Технологии распределенных и параллельных баз данных
Исследовательские проблемы
Заключение
Определения терминов
Литература

Введение

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

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

Параллельный компьютер или мультипроцессор сам по себе является распределенной системой, составленной из узлов (процессоров, компонентов памяти), соединенных быстрой сетью внутри общего корпуса. Технологии распределенных баз данных могут быть естественным образом пересмотрены и распространены на системы параллельных баз данных, т. е. баз данных на параллельных компьютерах [DeWitt and Gray, 1992, Valduriez, 1993]. Благодаря применяемому в системах этого типа параллелизму управления данными [Boral, 1988] пользователи получают серверы баз данных высокой производительности и высокой доступности за существенно меньшую цену, чем эквивалентные системы на основе мэйнфреймов [DeWitt and Gray, 1992, Valduriez, 1993].

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

Основные понятия

Распределенная база данных (DDB - distributed database) - это совокупность множества взаимосвязанных баз данных, распределенных в компьютерной сети. Система управления распределенной базой данных определяется как программная система, которая позволяет управлять базой данных таким образом, чтобы ее распределенность была прозрачна для пользователей [Ozsu and Valduriez, 1991a]. В этом определении следует уточнить два отличительных условия. Первое заключается в том, что система состоит из (возможно, пустого) множества узлов приема запросов (query site) и непустого множества узлов данных (data site). Узлы данных обладают средствами для хранения данных, а узлы приема запросов - нет; на них лишь выполняются программы, реализующие пользовательский интерфейс для доступа к данным, хранящимся в узлах данных. Второе условие заключается в том, что узлы логически представляют собой независимые компьютеры, на которых установлены собственные операционные системы (может быть, одинаковые на всех узлах, а возможно, и разные) и могут выполняться независимые приложения. Т. е. узлы - это компьютеры, связанные сетью, а не процессоры, составляющие многопроцессорную конфигурацию. Важнейший отличительный признак - слабосвязанный характер среды, где каждый узел имеет собственную операционную систему и функционирует независимо.

База данных физически распределяется по узлам данных при помощи фрагментации и репликации, или тиражирования, данных [Ceri et al., 1987]. Отношения, принадлежащие реляционной базе данных, могут быть фрагментированы на горизонтальные или вертикальные разделы. Горизонтальная фрагментация реализуется при помощи операции селекции, которая направляет каждый кортеж отношения в один из разделов, руководствуясь предикатом фрагментации. Например, для отношения Employee (Сотрудник) возможна фрагментация в соответствии с территориальным распределением рабочих мест сотрудников. При вертикальной фрагментации отношение делится на разделы при помощи операции проекции. Например, один раздел отношения Employee может содержать поля Номер_сотрудника, ФИО_сотрудника, Адрес_сотрудника, а другой - поля Номер_сотрудника, Оклад, Руководитель. За счет фрагментации данные приближаются к месту их наиболее интенсивного использования, что потенциально снижает затраты на пересылки; уменьшаются также размеры отношений, участвующих в пользовательских запросах.

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

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

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

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

Ниже перечислены идентифицирующие характеристики параллельных и распределенных СУБД.

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

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

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

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

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

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

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

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

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

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

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

Технологии распределенных и параллельных баз данных

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

Вопросы архитектуры

Существует множество альтернатив распределенной обработки. Наиболее популярна в настоящее время архитектура клиент-сервер [Orfali et al., 1994], когда множество машин-клиентов осуществляют доступ к одному серверу баз данных. В таких системах, которые можно определить как системы типа много-клиентов/один-сервер, проблемы управления базой данных решаются относительно просто, поскольку вся она хранится на одном сервере. Задачи, с которыми приходится здесь сталкиваться, - это управление буферами клиентов, кэширование данных и, возможно, блокировки. Управление данными реализуется централизованно на одном сервере.

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

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

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

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

Примерами систем параллельных баз данных являются продукты DBC (Teradata) и NonStop-SQL (Tandem), а также ряд прототипов, таких как BUBBA [Boral et al., 1990], EDS [EDS, 1990], GAMMA [DeWitt et al., 1990], GRACE [Fushimi et al., 1986], PRISMA [Apers et al., 1992] и ARBRE [Lorie et al., 1989].

Подход, основанный на разделении памяти, заключается в том, что каждый процессор посредством быстрых линий связи (высокоскоростных шин или кросс-панельных коммутаторов) соединен со всеми модулями памяти и дисковыми устройствами. Существуют несколько типов следующих этому подходу мэйнфреймов: IBM3090, DPS8 (Bull), а также симметричные многопроцессорные системы типа Sequent и Encore. Две сильные стороны систем с разделяемой памятью - простота и хороший баланс загрузки. Три наиболее существенные проблемы, связанные с этим подходом, - стоимость, ограниченная расширяемость, невысокая надежность.

К системам параллельных баз данных с разделяемой памятью относятся XPRS [Stonebraker et al., 1988], DBS3 [Bergsten et al., 1991] и Volcano [Graefe, 1990], а также перенесенные на мультипроцессоры с разделяемой памятью наиболее известные промышленные СУБД. Первым примером такой системы была реализация СУБД DB2 на IBM3090 с шестью процессорами. Во всех известных на сегодня коммерческих продуктах (таких как Ingres и Oracle) используется только межзапросный (но не внутризапросный) параллелизм.

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

Примеры параллельных СУБД с разделяемыми дисками: продукт IMS/VS Data Sharing (IBM), а также продукты VAX DBMS и Rdb компании DEC. Реализация Oracle на компьютерах VAXcluster (DEC) и NCUBE также использует разделение дисков, поскольку этот подход требует минимальных расширений в ядре СУБД. Отметим, что во всех этих системах применяется только межзапросный параллелизм.

Обработка и оптимизация запросов

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

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

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

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

Исходной информацией для локализации данных служит алгебраическое выражение, полученное на этапе декомпозиции запроса. В этом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Сущность данного шага заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. При этом выявляются фрагменты, реально участвующие в запросе, а запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как указано выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации. Программа локализации для горизонтально/вертикально фрагментированного запроса есть объединение (union)/соединение (join) его фрагментов. Таким образом, на этапе локализации данных запрос заменяется программой локализации; фрагментный запрос затем упрощается и реструктурируется, пока не будет получено "хорошее" выражение. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и в шаге декомпозиции, окончательный "хороший" фрагментный запрос может быть еще далек от оптимального; данный процесс лишь исключает "плохие" алгебраические выражения.

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

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

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

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

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

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

Управление одновременным доступом

Если множество пользователей одновременно осуществляют доступ (на чтение и запись) к разделяемой базе данных, то для поддержания согласованного состояния данных необходимо обеспечить синхронизацию доступа. Синхронизация достигается путем применения алгоритмов управления одновременным доступом, гарантирующих критерии корректности, такие как сериализуемость. Доступы пользователей к данным инкапсулируются в рамках транзакций [Gray, 1981], которые на нижнем уровне оформляются как последовательности операций чтения и записи данных. Алгоритмы управления одновременным доступом обеспечивают свойство изолированности выполнения транзакций, которое заключается в том, что результат транзакции не может зависеть (т. е. изолирован) от других параллельно выполняемых транзакций.

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

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

  1. выполнение этого множества транзакций сериализуемо на каждом узле;
  2. упорядочение транзакций на всех узлах одинаково.

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

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

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

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

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

Протоколы обеспечения надежности

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

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

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

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

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

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

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

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

Двухфазовая фиксация (2PC - 2 Phase Commit) - простой и элегантный протокол, обеспечивающий атомарную фиксацию распределенной транзакции. Он расширяет реализацию локальной атомарной фиксации на случай распределенной транзакции за счет того, что каждый участвующий в ней узел, прежде чем зафиксировать транзакцию, подтверждает, что он готов сделать это. В результате на всех узлах транзакция заканчивается одинаково (либо фиксируется, либо прерывается). Если все узлы согласны зафиксировать транзакцию, то все относящиеся к ней действия реально выполняются; если один из узлов отказывается зафиксировать свою часть транзакции, то и все остальные узлы вынуждены прервать данную транзакцию. Таким образом, 2PC опирается на следующие фундаментальные правила.

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

В простейшем варианте работа 2PC выглядит следующим образом. На узле, где инициируется транзакция, создается процесс-координатор; на всех прочих затрагиваемых ею узлах создаются процессы-участники. Вначале координатор рассылает участникам сообщение "приготовиться", и каждый из них независимо решает, может ли транзакция завершиться на данном узле. Участники, которые готовы завершить транзакцию, посылают координатору сообщение "голосую за фиксацию". Участники, не имеющие возможности зафиксировать свою часть транзакции, возвращают сообщение "голосую за прерывание". Проголосовавший участник не может изменить свое решение. Координатор, собрав голоса участников, решает судьбу транзакции согласно правилам 2PC. Если он принимает решение зафиксировать транзакцию, то всем участникам рассылается сообщение "глобальная фиксация". Если решено прервать транзакцию, то участникам, проголосовавшим за ее фиксацию, посылается сообщение "глобальное прерывание". Заметим, что участникам, проголосовавшим за прерывание, сообщение посылать не нужно, поскольку они сами способны принять решение исходя из правил 2PC. Эта ситуация известна под названием опции одностороннего прерывания.

Протокол предполагает два "раунда" обмена сообщениями между координатором и участниками, отсюда название 2PC. Имеется несколько вариаций классического 2PC, таких как линейный 2PC и распределенный 2PC, не получивших широкого признания среди поставщиков распределенных СУБД. Две наиболее важные разновидности протокола - 2PC с предполагаемой фиксацией и 2PC с предполагаемым прерыванием [Mohan and Lindsay, 1983]. Эти протоколы направлены на снижение числа сообщений, которыми должны обменяться узлы, и числа операций ввода-вывода. Протокол с предполагаемым прерыванием вошел в стандарт X/Open XA и принят как часть стандарта ISO для открытой распределенной обработки.

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

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

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

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

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

Протоколы тиражирования

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

Если поддерживается прозрачность тиражирования, то транзакция будет выдавать операции чтения-записи, относящиеся к логическому элементу данных x. Задача протокола тиражирования - отобразить эти операции на множества операций над физическими копиями x (x1 , x2 ,..., xn). Типичный протокол тиражирования, обеспечивающий сериализуемость по критерию полной эквивалентности копий, известен под названием ROWA (Read-Once/Write-All - одно чтение, запись во все копии). Протокол ROWA отображает чтение x Read(x) на операцию чтения какой-либо из копий x Read(xi). Из какой именно копии будет производиться чтение, неважно - этот вопрос может решаться из соображений эффективности. Каждая операция записи в логический элемент данных x отображается на множество операций записи во все физические копии x.

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

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

Идея, согласно которой для завершения транзакции достаточно модифицировать некоторое подмножество копий, легла в основу механизма, названного голосованием на базе кворума и соответствующего протокола тиражирования. Алгоритм консенсуса большинства можно сформулировать в этих терминах следующим образом: каждой копии данных приписывается равный по весу голос, и транзакция, изменяющая логический элемент данных, может успешно завершиться, если она наберет большинство голосов. На той же идее основан и алгоритм голосования на базе кворума [Gifford, 1979], который также присваивает копиям данных (возможно, неодинаковые по весу) голоса. Каждая операция доступа должна в этом случае набрать необходимый кворум, соответственно, чтения (Vr) или записи (Vw). Если элемент данных имеет в сумме V голосов, то кворумы должны удовлетворять следующим требованиям.

1. Vr + Vw > V. Две транзакции не могут одновременно читать и модифицировать один и тот же элемент данных во избежание конфликта чтение-запись.

2. Vw > V/2. Две транзакции не могут одновременно производить запись одного и того же элемента данных во избежание конфликта запись-запись.

Проблема, присущая этому подходу, состоит в том, что транзакция должна набрать кворум даже для чтения. Из-за этого существенно и неоправданно замедляется доступ к базе данных на чтение. Был предложен альтернативный протокол голосования на базе кворума, где этот серьезный недостаток преодолевается [Abbadi et al., 1985]. Однако этот протокол исходит из совершенно нереалистичных предположений о свойствах коммуникационной системы. Базовые требования состоят в том, что всем узлам немедленно становится известно об отказах, приводящих к изменениям в топологии сети, и каждый узел располагает представлением той части сети, где содержатся узлы, с которыми он взаимодействует. В общем случае невозможно гарантировать выполнимость этих требований. Таким образом, протокол полной эквивалентности копий является ограничительным с точки зрения доступности системы, а протоколы, основанные на голосовании, слишком сложны, и с ними связаны высокие накладные расходы. Поэтому в современных промышленных распределенных СУБД ни один из этих методов не используется. Для практического применения были исследованы некоторые более гибкие технологии репликаций, где тип согласования копий находится под контролем пользователя. На основе этого принципа уже созданы или создаются несколько моделей серверов репликаций. К сожалению, в настоящее время не существует стройной теории, которая бы позволяла судить о согласованности тиражированной базы данных в условиях, когда применяются относительно нестрогие политики репликаций. Исследования в этой области находятся лишь в зачаточном состоянии.

Исследовательские проблемы

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

Размещение данных

В параллельной системе баз данных правильное размещение данных имеет решающее значение для обеспечения баланса загрузки. В идеале можно полностью избежать интерференции между одновременно выполняемыми параллельными операциями, если каждая из них будет работать с независимым множеством данных. Независимые множества данных получаются путем декластеризации (горизонтальной фрагментации) отношений на основе функции (хэш-функции или индексации по диапазону) от одного или более атрибутов и размещения фрагментов на разных дисках. Как и в случае горизонтальной фрагментации в распределенных базах данных, декластеризация полезна для достижения межзапросного параллелизма, когда независимые запросы работают с разными фрагментами, а также внутризапросного параллелизма, когда операции, относящиеся к одному запросу, выполняются одновременно над различными фрагментами. Декластеризация может проводиться по одному или по нескольким атрибутам. В последнем случае [Ghandeharizadeh et al., 1992] запрос точного сопоставления по нескольким атрибутам может выполняться на одном узле без взаимодействий с другими узлами. Выбор между хэшированием и индексацией по диапазону - это вопрос организации базы данных: хэширование требует меньше памяти, но поддерживает только запросы точного сопоставления, а индексация по диапазону поддерживает также запросы по диапазону. Декластеризация, которая вначале была предложена для систем без разделения ресурсов, оказалась полезной и для систем с разделяемой памятью, поскольку она способствует снижению конфликтности при доступе к памяти [Bergsten et al., 1991].

Полная декластеризация, когда каждое отношение должно быть обязательно фрагментировано по всем узлам системы, вызывает проблемы при работе с малыми отношениями, а также в системах с очень большим числом узлов. Более удачен подход переменной декластеризации, при котором каждое отношение распределяется между определенным числом узлов, которое является функцией от размера отношения и частоты доступа к нему [Copeland et al., 1988]. Этот подход может сочетаться с кластеризацией множеств отношений, что позволяет избежать избыточных коммуникаций при выполнении бинарных операций.

Когда используемые критерии размещения данных приводят к деградации баланса загрузки, необходимо произвести динамическую реорганизацию базы. Очень важно, чтобы реорганизацию можно было проводить в оперативном режиме (не прекращая текущей обработки транзакций), причем достаточно эффективно (применяя методы параллелизма). Существующие СУБД способны производить реорганизацию баз данных только статически [Shasha, 1992]. Статическая реорганизация проводится периодически и служит для изменения размещения данных либо в связи с увеличением размера базы данных, либо из-за изменения структуры спроса на доступ к данным. В отличие от статической, динамическая реорганизация базы данных не требует остановки работы системы и обеспечивает плавный переход к новому размещению данных. Существенно, чтобы реорганизация была прозрачна для скомпилированных программ, работающих в параллельной системе. В частности, она не должна приводить к необходимости перекомпиляции программ. Это значит, что скомпилированные программы должны быть инвариантны относительно размещения данных. Отсюда следует, что оптимизатору не должно быть известно фактическое местоположение дисков, на которых хранится то или иное отношение, а также узел, где будет выполняться конкретная операция. Множество узлов, где хранится отношение в момент выполнения операции, называется домашним множеством отношения. Множество узлов, на которых выполняется операция, называется домашним множеством операции. Оптимизатор тем не менее должен обладать некоторым абстрактным знанием о структуре домашнего множества (например "отношение R хэшировано на 20 узлах по атрибуту A"), а система поддержки времени выполнения проведет ассоциирование между абстрактным домашним множеством и фактическими узлами.

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

Еще один фактор, усложняющий задачу размещения данных, - это тиражирование для обеспечения высокой готовности. Наивный подход здесь заключается в том, чтобы иметь две копии одних и тех же данных - первичную и дублирующую - на двух отдельных узлах. Но в случае отказа одного узла нагрузка на второй удвоится, что приведет к нарушению баланса загрузки. Для решения этой проблемы в последнее время было предложено несколько стратегий тиражирования для поддержания высокой готовности, сравнительный анализ которых приведен в [Hsiao and DeWitt, 1991]. Интересный подход, который можно назвать расслоением, применен в Teradata, где дублирующая копия декластеризуется между несколькими узлами. В случае отказа первичного узла его загрузка распределяется между узлами, содержащими дублирующую копию. Однако реконструкция первичной копии из фрагментов ее дубля может оказаться дорогостоящей операцией. Существенны также затраты, требуемые на поддержание согласованного состояния дублирующей копии в нормальном режиме. Более разумное решение, названное цепной (chained) декластеризацией, применено в Gamma, где первичная и дублирующая копии хранятся на двух соседних узлах. В режиме сбоя загрузка отказавшего узла распределяется между всеми остальными узлами, которые используют копии данных как первичного, так и вторичного узла. Поддержание согласованных копий в этом случае обходится дешевле. Открытым остается вопрос о процедуре размещения данных с учетом их тиражирования. Так же, как размещение фрагментов в распределенных базах данных, эта задача должна рассматриваться как одна из проблем оптимизации.

Проблемы сетевой масштабируемости

Исследовательское сообщество не располагает достаточно полным представлением о том, как связана производительность баз данных с разнообразными сетевыми архитектурами, которые развиваются вместе с современными распределенными СУБД. Возникает, в частности, вопрос о масштабируемости некоторых протоколов и алгоритмов в условиях, когда системы становятся географически распределенными [Stonebraker, 1989], или с расширением отдельных системных компонентов [Garcia-Molina and Lindsay, 1990]. Важное значение имеет проблема пригодности механизмов для распределенной обработки транзакций в распределенных системах на базе глобальных сетей (WAN). Как упоминалось выше, работа этих протоколов связана с высокими накладными расходами, и реализация их на медленной сети WAN сильно затруднена [Stonebraker, 1989].

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

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

Распределенная и параллельная обработка запросов

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

Стоимостная модель - центральное звено глобальной оптимизации запросов, поскольку она предоставляет необходимую абстракцию среды выполнения распределенной СУБД в терминах методов доступа, а также абстракцию о самой базе данных в терминах информации об ее физической схеме и соответствующей статистики. Стоимостная модель используется для предсказания затрат на реализацию альтернативных планов выполнения запроса. Со стоимостными моделями зачастую связан ряд серьезных ограничений, которые снижают эффективность оптимизации, направленной на улучшение общей пропускной способности системы. Полезными здесь могут быть работы по созданию расширенных алгоритмов оптимизации на основе параметризуемой стоимостной модели [Freytag, 1987], которую можно настраивать экспериментальным способом. Хотя языки запросов становятся все более развитыми (новые версии SQL), на стадии глобальной оптимизации применяется весьма ограниченное их подмножество; запросы формулируются в терминах языка SPJ (select-project-join - селекция-проекция-соединение) с конъюнктивными предикатами. Это важный класс запросов, для которого существуют развитые методы оптимизации. Разработаны, в частности, различные теории оптимального упорядочения соединений и полусоединений. В то же время имеются и другие важные классы запросов, для которых еще предстоит создать соответствующие методы оптимизации: запросы с дизъюнкциями, объединениями, фиксированными точками (fixpoint), агрегациями и сортировками. Многообещающий подход к этой проблеме заключается в отделении механизмов языкового распознавания от собственно оптимизации, которую можно доверить нескольким "экспертам оптимизации".

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

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

Критически важный вопрос, с точки зрения стратегии поиска, - это задача упорядочения соединений, которая является NP-полной для нескольких отношений [Ibaraki and Kameda, 1984]. Типичный подход к решению этой задачи - применение динамического программирования [Selinger et al., 1979], которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных. Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений. Однако уже для 5-7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomized strategy), которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации - применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов [Ioannidis and Wong, 1987, Swami and Gupta, 1988, Ioannidis and Kang, 1990].

Распределенная обработка транзакций

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

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

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

В дополнение к тиражированию и в связи с ним необходимо также исследовать более сложные модели транзакций, в частности такие, в которых возможно использование семантики приложения [Elmagarmid, 1992, Weihl, 1989].

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

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

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

Заключение

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

Мы не охватили ряд смежных вопросов. Две важные проблемы, не рассмотренные здесь, - это системы мультибаз данных (multidatabase system) и распределенные объектно-ориентированные базы данных. Многие информационные системы развиваются независимо, опираясь на собственные реализации СУБД. Позже, когда появляется необходимость "интегрировать" эти автономные и часто разнородные системы, возникают серьезные трудности. Системы, которые предоставляют доступ к подобным, независимо разработанным разнородным базам данных, называются мультибазами данных [Sheth and Larson, 1990].

Проникновение баз данных в такие области (проектирование, мультимедийные системы, геоинформационные системы, системы обработки графических образов), для которых реляционные СУБД изначально не предназначались, послужило стимулом для поиска новых моделей и архитектур баз данных. Среди наиболее серьезных кандидатов, претендующих на удовлетворение потребностей новых классов приложений, - объектно-ориентированные СУБД [Dogac et al., 1994]. Внедрение принципов распределенной обработки в эти СУБД стало источником целого ряда проблем, относящихся к области так называемого распределенного управления объектами [Ozsu et al., 1994]. Вопросы, связанные с мультибазами данных и распределенным управлением объектами, остались за рамками рассмотрения настоящей статьи.

Определения терминов

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

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

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

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

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

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

Атомарность. Свойство обработки транзакций, заключающееся в том, что либо выполняются все операции транзакции, либо не выполняется ни одна (принцип "все или ничего").

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

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

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

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

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

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

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

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

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

Межзапросный параллелизм. Параллельное выполнение нескольких запросов, относящихся к разным транзакциям.

Независимость данных. Устойчивость прикладных программ и запросов к изменениям в физической организации базы данных (независимость от физических данных) или в ее логической организации (независимость от логических данных) и обратная независимость.

Неустойчивая база данных. Часть базы данных, хранимая в буферах оперативной памяти.

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

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

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

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

Протокол ROWA (Read-Once/Write-All). Протокол управления тиражированием, который логическую операцию чтения отображает на операцию чтения любой физической копии, а логическую операцию записи - на множество операций записи во все физические копии элемента данных.

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

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

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

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

Стабильная база данных. Часть базы данных, хранимая во вторичной памяти.

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

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

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

Литература

[Abbadi et al., 1985] A. E. Abbadi, D. Skeen, and F. Cristian. An Efficient, Fault-Tolerant Protocol for Replicated Data Management. - Proc. 4th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, Portland, Oreg., March 1985, pp. 215-229.

[Apers et al., 1992] P. Apers, C. van den Berg, J. Flokstra, P. Grefen, M. Kersten, A. Wilschut. Prisma/DB: a Parallel Main-Memory Relational DBMS. - IEEE Trans. on Data and Knowledge Eng., 1992, 4(6), pp. 541-554.

[Bell and Grimson, 1992] D. Bell and J. Grimson. Distributed Database Systems. - Reading, MA: Addison-Wesley, 1993.

[Bergsten et al., 1991] B. Bergsten, M. Couprie, P. Valduriez. Prototyping DBS3, a Shared-Memory Parallel Database System. - Proc. Int. Conf. on Parallel and Distributed Information Systems, Miami, Florida, December 1991, pp. 226-234.

[Bernstein et al., 1987] P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. - Reading, MA: Addison-Wesley, 1987.

[Boral, 1988] H. Boral. Parallelism and Data Management. - Proc. 3rd Int. Conf. on Data and Knowledge Bases, Jerusalem, June 1988, pp. 362-373.

[Boral et al., 1990] H. Boral, W. Alexander, L. Clay, G. Copeland, S. Danforth, M. Franklin, B. Hart, M. Smith, and P. Valduriez. Prototyping Bubba: a Highly Parallel Database System. - IEEE Trans. on Knowledge and Data Engineering, March 1990, 2(1), pp. 4-24.

[Ceri and Pelagatti, 1984] S. Ceri and G. Pelagatti. Distributed Databases: Principles and Systems. - New York: McGrow-Hill, 1984.

[Ceri et al., 1987] S. Ceri, B. Pernici, and G. Wiederhold. Distributed Database Design Methdologies. - Proc. IEEE, May 1987, 75(5), pp. 533-546.

[Copeland et al., 1988] G. Copeland, W. Alexander, E. Bougherty, and T. Keller. Data Placement in Bubba. - Proc. ACM SIGMOD Int. Conf. on Management of Data, Chicago, May 1988, pp. 99-108.

[DeWitt et al., 1990] D.J. DeWitt, S. Ghandeharizadeh, D.A. Schneider, A. Bricker, H.-I. Hsiao, and R. Rasmussen. The GAMMA Database Machine Project. - IEEE Trans. on Knowledge and Data Eng, March 1990, 2(1), pp. 44-62.

[DeWitt and Gray, 1992] D. DeWitt and J. Gray. Parallel Database Systems: The Future of High-Performance Database Systems. -Communications of ACM, June 1992, 35(6), pp. 85-98. Русский перевод: Д. Девитт, Д. Грэй. Параллельные системы баз данных: будущее высоко эффективных систем баз данных. - СУБД N2, 1995.

[Dogac et al., 1994] A. Dogac, M.T. Ezsu, A. Biliris, and T. Sellis (eds.) Advances in Object-Oriented Database Systems. - Berlin: Springer-Verlag, 1994.

[EDS, 1990] European Declarative System (EDS) Database Group. EDS-Collaborating for a High-Performance Parallel Relational Database. - Proc. ESPRIT Conf, Brussel, November 1990.

[Elmagarmid, 1992] A.K. Elmagarmid (ed.). Transaction Models for Advanced Database Applications. - San Mateo, CA: Morgan Kaufmann, 1992.

[Freytag et al., 1993] J-C. Freytag, D. Maier, and G. Vossen. Query Processing for Advanced Database Systems. - San Mateo, CA: Morgan Kaufmann, 1993.

[Freytag, 1987] J-C. Freytag. A Rule-based View of Query Optimization. - Proc. ACM SIGMOD Conf. on Management of Data, San Francisco, 1987, pp 173-180.

[Fushimi et al., 1986] S. Fumishi, M. Kutsuregawa, and H. Tanaka. An Overview of the System Software of a Parallel Relational Database Machine GRACE. - Proc 12th Int. Conf. on Very Large Data Bases, Kyoto, August 1986, pp. 209-219.

[Garcia-Molina and Lindsay, 1990] H. Garsia-Molina and B. Lindsay. Research Directions for Distributed Databases. - IEEE Q. Bull. Database Eng., December 1990, 13(4), pp. 12-17.

[Ghandeharizadeh et al., 1992] S. Ghandeharizadeh, D. DeWitt, W. Quresh. A Performance Analysis of Alternative Multi-Attributed Declustering Strategies. - ACM SIGMOD Int. Conf. on Management of Data. San Diego, CA, June 1992, pp. 29-38.

[Gifford, 1979] D.K. Gifford. Weighted Voting for Replicated Data. -Proc. 7th ACM Symp. on Operating System Principles, Pacific Grove, CA, December 1979, pp. 150-159.

[Graefe, 1990] G. Graefe. Encapsulation of Parallelism in the Volcano Query Processing Systems. - Proc. ACM SIGMOD Int. Conf, Atlantic City, NJ, May 1990, pp. 102-111.

[Gray, 1981] J. Gray. The Transaction Concept: Virtues and Limitations. - Proc. 7th Int. Conf. on Very Large Data Bases, Cannes, France, September 1981, pp. 144-154.

[Gray, 1979] J.N. Gray. Notes on Data Base Operating Systems. In Operating Systems: An Advanced Course, R. Bayer, R.M. Graham, and G. Seegmuller (eds.). - New York: Springer-Verlag, 1979, pp. 393-481.

[Gray and Reuter, 1993] J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. - San Mateo, CA: Morgan Kaufmann, 1993.

[Hsiao and DeWitt, 1991] H.-I. Hsiao and D. DeWitt. A Performance Study of three High-Availability Data Replication Strategies. -Proc. Int. Conf. on Parallel and Distributed Information Systems, Miami, December 1991, pp. 18-28.

[Ibaraki and Kameda, 1984] T. Ibaraki and T. Kameda. On the Optimal Nesting Order for Computing N-Relation Joins. - ACM Trans. Database Syst., September 1984, 9(3), pp. 482-502.

[Ioannidis and Wong, 1987] Y. Ioannidis and E. Wong. Query Optimization by Simulated Annealing. - Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1987, pp. 9-22.

[Ioannidis and Kang, 1990] Y. Ioannidis and Y.C. Kang. Randomized Algorithms for Optimizing Large Join Queries. - Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1990, pp. 312-321.

[Lorie et al., 1989] R. Lorie, J-J. Daudenarde, G. Hallmark, J. Stamos, H. Young. Adding Intra-Parallelism to an Existing DBMS: Early Experience. - IEEE Bull. on Database Engineering, March 1989, 12(1), pp. 2-8.

[Mohan and Lindsay, 1983] C. Mohan and B. Lindsay. Efficient Commit Protocols fpr the Tree of Processes Model of Distributed Transactions. - Proc. 2nd ACM SIGACT-SIGMOD Symp. on Priciples of Distributed Computing, 1983, pp. 76-88.

[Orfali et al., 1994] R. Orfali, D. Harkey and J. Edwards. Essential Client/Server Survival Guide. - New York: John Wiley, 1994.

[Ezsu, 1994] M.T. Ezsu. Transaction Models and Transaction Management in Object-Oriented Database Management Systems. (In Advances in Object-Oriented Database Systems. A. Dogac, M.T. Ezsu. , A. Biliris, and T. Sellis (eds). - Berlin: Springer-Verlag, 1994, pp. 147-183.)

[Ezsu. and Valduriez, 1991a] M.T. Ezsu. and P. Valduriez. Principles of Distributed Database Systems. - Englewood Cliffs, NJ: Prentice-Hall, 1991.

[Ezsu. and Valduriez, 1991b] M.T. Ezsu and P. Valduriez. Distributed Database Systems: Where Are We Now? - IEEE Computer, August 1991, 24(8), pp. 68-78.

[Ezsu et al., 1994] M.T. Ezsu, U. Dayal, and P. Valduriez (eds). Distributed Object Management. - San Mateo: Morgan Kaufmann, 1994.

[Selinger et al., 1979] P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price. Access Path Selection in a Relational Database Management System. - Proc. ACM SIGMOD Int. Conf. on Management of Data, Boston, Mass., May 1979, pp. 23-34.

[Shasha, 1992] D. Shasha. Database Tuning: a Principled Approach. - Englewood Cliffs, NJ: Prentice Hall, 1992.

[Sheth and Larson, 1990] A. Sheth and J. Larson. Federated Databases: Architectures and Integration. - ACM Comput. Surv., September 1990, 22(3), pp. 183-236.

[Stonebraker, 1989] M. Stonebraker. Future Trends in Database Systems. - IEEE Trans. Knowledge and Data Eng., March 1989, 1(1), pp. 33-44.

[Stonebraker et al., 1988] M. Stonebraker, R. Katz, D. Patterson, and J. Ousterhout. The Design of XPRS. - Proc. 14th Int. Conf. on Very Large Data Bases, Los Angeles, September 1988, pp. 318-330.

[Swami and Gupta, 1988] A. Swami and A. Gupta. Optimization of Large Join Queries. - Proc. of the ACM SIGMOD Int. Conf. on Management of Data, 1988, pp. 8-17.

[Valduriez, 1993] P. Valduries. Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases, April 1993, 1(2), pp. 137-165.

[Weihl, 1989] W. Weihl. Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Prog. Lang. Syst., April 1989, 11(2), pp. 249-281.

Комментарии к списку литературы

Сейчас есть два учебника по распределенным и параллельным базам данных - это наша книга [Ezsu and Valduriez, 1991a] и еще [Bell and Grimson, 1992]. Первой серьезной книгой по этой теме была [Ceri and Pelagatti, 1984], в настоящее время уже устаревшая. В статье [Ozsu and Valduriez, 1991b], которая во многом перекликается с упомянутой выше нашей книгой, обсуждаются многие открытые на сегодня проблемы распределенных баз данных. Упомянем также две блестящие статьи о параллельных системах баз данных [DeWitt and Gray, 1992, Valduriez, 1993].

Среди работ по более специфическим проблемам отметим книгу [Freytag et al., 1993], посвященную обработке запросов, где дается обзор результатов последних исследований. В работе [Elmagarmid, 1992] описан ряд новых моделей транзакций. [Gray and Reuter, 1993] содержит прекрасный обзор по проектированию менеджеров транзакций. Еще одна классическая книга, посвященная обработке транзакций, - [Bernstein et al., 1987]. В этих книгах освещены также вопросы надежности и управления одновременным доступом.

M. Tamer Ezsu
Department of Computing Science University of Alberta
Edmonton, Canada T6G 2H1
Patric Valduriez
INRIA, Rocquencourt
78153 LE Chesnay Cedex
France

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

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