Параллельные базы данных

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

?тура без разделяемых ресурсов (shared-nothing) и архитектура с разделяемой памятью (shared-memory). Промежуточную позицию занимает архитектура с разделяемыми дисками (shared-disk).

Примерами систем параллельных баз данных являются продукты DBC (Teradata) и NonStop-SQL (Tandem), а также ряд прототипов, таких как BUBBA, EDS, GAMMA, GRACE, PRISMA и ARBRE.

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

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

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

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

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

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

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

Внутриоперационный (intra-operation) параллелизм достигается за счет выполнения операции сразу на нескольких узлах многопроцессорной машины. Для этого необходимо предварительное разбиение операндов, т.е. их горизонтальная фрагментация по узлам. Способ разделения базового отношения относится к области физического проектирования базы данных. Обычно разделение производится путем применения некоторой хэш-функции к тому атрибуту отношения, который будет часто являться атрибутом соединения. Набор узлов, в которых хранится отношение, называется домашним набором (home). Домашним набором узлов операции (home of an operation) называется набор узлов, в которых она выполняется; оно должно совпадать с домашним набором узлов ее операндов, чтобы операция имела доступ к своим операндам. Это значит, что для бинарных операций, таких как соединения, может потребоваться переразделение (repartitioning) одного из операндов. В некоторых случаях оптимизатор, возможно, сочтет целесообразным провести переразделение обоих операндов. Для реализации внутриоперационного параллелизма в параллельных СУБД применимы некоторые методы, разработанные для распределенных баз данных.

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

 

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

 

Если несколько пользователей одновременно (concurrently) осуществляет доступ (на чтение и запись) к совместно используемой базе данных, то для поддержки согласованного состояния данных требуется синхронизовать доступ. Синхронизация достигается путем применения алгоритмов управления одновременным доступом (concurrency control algorithm), гарантирующих следование критериям корректности, таким как сериализуемость. Доступ пользователей к данным инкапсулируются в рамках транзакций, которые на нижнем уровне выглядят как последовательности операций чтения и записи данных. Алгоритмы управления одновременным доступом обеспечивают соблюдение свойства изолированности выполнения транзакций, которое заключается в том, что воздействия одной транза?/p>