1626434812-e667f6b6e7e69d3a0798830a58e9075b (844135), страница 55
Текст из файла (страница 55)
Системы с разделяемой дисковой памятью имеют структуру, показанную на рис 10.2. Разделяемый логический общедоступный диск обычно реализуется из нескольких устройств дисковой памяти, подсоединенных к локальной сети, к которой подключены также вычислительные модули (ВМ). Дис- Глава 1О. Параллельные базы данных ковая память может использоваться для хранения, например, системной контрольной точки. Рис. 70.2.
Сл1руктура систем с разделяемой дисковой памятью В системах с распределенной памятью, структура которых показана на рис 10.3, каждый ВМ снабжается собственной локальной дисковой памятью. Рис. 1О.З. Структура систем с распределенной палытью, в которых отсутствуют разделяемые ресурсы па.ыяти Подобные системы представляют собой сеть автономных компьютеров, взаимодействие между которыми выполняется посредством обмена сообщениями. Приведенные логические структуры являются предельными вариантами. Возможно использование комбинированных структур, в которых часть памяти распределена, а часть разделяется группами процессоров.
Базы данных. Интеллектуальная обработка информации 10.1.3. Интерфейс между базой данных и вычислительной системой Приведенные логические структуры систем представляют собой уровень интерфейса между вышележащими уровнями программных средств СУБД и нижележащим уровнем аппаратуры. Логическая структура закладывается в СУБД в механизм распределения данных по устройствам памяти и в алгоритмы оптимизации выполнения запросов к хранимым в базе данным. Например, чаще всего применяются две модели реляционных баз данных. В одной модели память имеет двухуровневую организацию и состоит из электронной оперативной памяти и дисковой внешней памяти, В другой модели память одноуровневая и только оперативная 1741.
Первая модель отражает объективное состояние возможностей устройств хранения данных в начале 90-х годов, вторая— современное состояние в области массово-параллельных систем, состоящих из тысяч ВМ, каждая из которых имеет от 0.1 до 2 Гбайт оперативной памяти. В последнем случае общий объем оперативной памяти может достигать нескольких терабайт, Кроме приведенных выше логических структур, могут использоваться и другие, например, буквально соответствующие аппаратным средствам како~олибо типа компьютерной системы.
Важно, чтобы эти структуры имели параметрическое описание, закладываемое в алгоритмы оптимизации выполнения запросов СУБД. При этом следует разделять случаи использования одного и того же алгоритма с различными значениями параметров и применения различных алгоритмов. Это касается, например, неприемлемости крайней точки зрения, при которой две вышеприведенные модели с одноуровневой и двухуровневой памятью не различимы при указании нулевого значения параметра, задающего объем дисковой памяти. 10.2.
Реализации операций реляционных баз данных на параллельных системах с интерфейсом передачи сообщений 10.2.1. Основные распараллеливаемые операции Основные определения операций реляционных баз данных приведем в том виде, как они представлены в 175~. Пусть Г=(АО, А1,..., Ап1, где АО,..., Ап — множества. Отношение Р на множестве à — это подмножество декартова произведения доя(АО)'Чош(А1)* ... Моя(Ап), где йнп(А~) — это домен (множество значений) А). ЦАО А! А2 ... Ал~ представляет Р на множестве (АО, А1, А2, ..., Ап) и называется схемой Р. В Глава 30.
Параллельные базы дакиых 1ЧАО А1 А2 ... Ап) каждый столбец А1 называется атрибутом К и обозначается как К.А). Каждая строка К называется кортежем и обозначается как <а0,а1,а2, ..., ап>, где а1 принадлежит бот(А)). Значение атрибута А) кортежа 1с, принадлежащего й., обозначается как ЦАЯ. Для иллюстрации изложенного рассмотрим показанные на рис. 10.4 реляционные отношения, содержащие сведения о служащих предприятия. Рис.
10.4. Прииер реляцаолных отношений Отношение ЕН% имеет три атрибута — ЕНЮ,Номер, ЕНЮ.Рост и ЕНЮ.Вес, а отношение ЕА имеет только два атрибута — ЕА.Номер и ЕА.Возраст, Каждое отношение состоит из 6 кортежей. Четыре операции реляционной алгебры, на которых в основном базируется параллельная работа с базами данных, — это селекция, проекция, соединение и агрегация.
Эти три операции формально определяются следующим образом: 1. Селекция — это выбор из отношения ЦХУМ~ подмножества кортежей, удовлетворяющих заданному условию, и определяется как: Бе1 (8.) = ( Е~ХУХ1 У В,В = Ь 1, где  — атрибут К. В=Ь Пример операции селекция: вывести список служащих ростом 175. Бе1 ( ЕНЮ)= ЕН%К Рост=175 Результат: Номер Рост Вес 101 175 95 303 175 80 801 175 87 Базы данных. Интеллектуальная обработка информации 2. Проекци» вЂ” выбор части атрибутов отношения (К[ХУД~), исключая повторения, определяется как: Рг (К)=( К.В), где  — множество атрибутов К. В Пример операции проекция: перечислить все веса сотрудников. Рг (ЕН%)= ЕНЖ Вес Результат: Вес 95 65 80 87 3. Соединение- сравнение на совпадение значений двух атрибутов (столбцов) разных отношений (таблиц) и построение отношения из строк соединяемых отношений„для которых сравниваемые значения атрибутов одинаковы.
Соединение (ю1п) двух отношений ЦХУУ1 и 8[ЧФХ1 обозначается как ЩХКЦ Э 8[ЧИХ1 и определяется как: т[ХЮЧВ~= ЩХКЦ Е 8РЛЧХ1=(Хитрит.Х=КХ а т.х=к.хаКХ=у ), ~.~ =у КХ=у Если не существует общих атрибутов, то соединение К и 8 — это декартово произведение К и 8. Пример операции соединение: найти вес и возраст сотрудников, имеющих рост 175. ЕН%[Номер, Рост, Вес1 ® ЕА[Номер, Возраст1= ЕН%. Рост=175 Результат: Номер Вес Рост Возраст 101 95 175 31 303 80 175 34 801 87 175 55 4, Операции агрегации — обозначаются а88Г(Х)(К) и вычисляют глобальные функции агрегации на атрибуте Х отношения К. Пример функции агрега- гуг Глава 10.
Параллельные базы данных ции 1(х): суммирование аапяигл(Х), максимальный элемент а~двах(Х), минимальный элемент адрп1п(Х), среднее аядтпеап(Х). Например, общий вес служащих определяется как ааритп (ЕН%.Вес)(ЕН%) = 472. В вычислительных системах с передачей сообщений кортежи каждого отношения в базе данных распределяются между дисковыми запоминающими устройствами, подсоединенными к каждому вычислительному модулю (ВМ), ВМ состоит из процессора и памяти, подсоединенных либо к локальным дисковым устройствам, либо к разделяемому массиву дисковых устройств. Распределение кортежей по ВМ позволяет просматривать большие отношения параллельно. 10.2.2. Виды параллельной обработки в базах данных Данные распределяются по ВМ при помощи фрагментации и тиражирования «репликации).
Фрагментация бывает горизонтальной, вертикальной и горизонтально-вертикальной. Горизонтальная фрагментация выполняется операцией селекции, распределяющей кортежи в соответствии с предикатом селекции. Вертикальная фрагментация реализуется с применением операции проекции, направляющей разделы кортежей в соответствующие ВМ. Фрагменты данных могут тиражироваться (копироваться) для минимизации времени доступа к данным за счет пересылки данных между вычислительными модулями и хранения многих копий фрагментов данных. Схема разбиения данных значительно влияет на время реализации операций.
Если ситуация требует, чтобы в каждом разбиении были юртежи, значения атрибутов которых лежат в определенном диапазоне, тогда может быть использовано горизонтальное разбиение. Горизонтальное разбиение отношений увеличивает объем данных, которые могут быть обработаны без взаимодействия процессов. Если ситуация требует, чтобы в каждом разбиении было толью неюторое подмножество атрибутов кортежей, тоща может быль использовано вертикальное разбиение. Вертикальное разбиение отношений уменьшает объем резидентных данных и делает ненужным проектирование требуемых атрибутов в первоначальном отношении. Если использовано вертикальное разбиение, необходимы дополнительные соединения для достижения значений нерезидентных атрибутов.
Результатом дополнительного соединения является взаимодействие ВМ и увеличение времспи вычислений. 10.2.3. Основные свойства параллельных и распределенных БД Как распределенная, так и параллельная базы данных — это совокупность баз данных, распределенных по компьютерной сети и способных выступить 298 Базы данных. Интеллектуальнан обработка информации как интегрированное целое, прозрачное для пользователей. Прозрачность— невидимость для пользователя фрагментации данных, то есть язык запросов к распределенной или параллельной базе не отличается от языка запросов к последовательной.
Сейчас общепринятым языком запросов служит Я~1 ~7~. Прикладные программы на 8(Я., написанные для однопроцессорных систем, можно выполнять параллелыю на системах с распределенной памятью. Практика показывает, что прн исполнении прикладных программ, написанных на стандартном Бгн', без переделки программ в системах Тегай1а н Тапдсв достигается почти линейные ускорение ~631. В СУБД распределенных и параллельных баз данных выделяют следующие виды параллелизма: межзапросный, при котором выполняется множество запросов разных транзакций; внутризапросный, выполняющий несколько операций, относящихся к одному запросу; внутриоперационный, при котором выполняются параллельно части одной операции.
Между системами управления, распределенными и параллельными базами данных есть много общего при наличии существенного различия, состоящего в том, что в параллельной базе данных применяются все три вида параллелизма, а в распределенной базе — только два первых. Распределенные СУБД, ориентированные на сети персональных ЭВМ и рабочих станций, способны обеспечивать эффективное распределение исполнения транзакций по компьютерам. При выполнении запроса должна быть использована информация о распределении данных. Распределенные (фрагментированные) отношения реконструируются путем обращения операций. использованных при фрагментации. К операциям реляционной алгебры добавляются операторы приема и посылки сообщений.
Среди возможных вариантов реализации совокупности операций запросов необходимо выбрать самый дешевый, например, требующий наименьшего времени выполнения. Очень важно оптимизировать порядок выполнения соединений (~о~п), так как при их реализации идет просмотр и сравнение атрибутов всех кортежей отношений. Рационально выбранный порядок исполнения может дать несколько порядков ускорения выполнения. Корректность совмещенного выполнения совокупности транзакций обеспечивается блокированием доступа к изменяемым данным посредством синхропримитивов, Обычно используется двухфазовое блокирование: ни одна блокировка от имени какой-либо транзакции не должна устанавливаться, пока не будет снята ранее установленная блокировка, Гпава 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
