1626434812-e667f6b6e7e69d3a0798830a58e9075b (844135), страница 56
Текст из файла (страница 56)
Параллельные базы данных Блокирование может быть централизованным и распределенным, децентрализованным. При централизованном — одна таблица и один менеджер блокировок. Недостатки — один узел порождает ненадежность и узкое место, ограничивающее пропускную способность. Децентрализованное блокирование предполагает коммуникационные затраты. Альтернатива блокировкам — временные метки и оптимистичное управление одновременным доступом: считается, что все можно. После выполнения проверяется„было ли нарушение. Если да, то отбрасывание результатов и повтор.
10.2.4. Параллельное выполнение операций Действия над отношениями БД могут быть разделены на два типа: не требуюшие участия всех кортежей отношений (цпйзсап) и требуюшие участия всех кортежей (пыйвсап) ~75~. Например, соединение и проекиия — это гпц!иасап операции, так как каждый кортеж при их исполнении сравнивается с множеством кортежей. Однако селекция и операция агрегаиии — это цпгвсап операции, потому что обработка каждого кортежа не зависит от обработки других кортежей. Реализация операций, не требующих участия всех кортежей В селекции на горизонтально фрагментированном отношении принимают участие распределенныс по ВМ кортежи.
Параллельное исполнение селекиии заключается в чтении каждой ВМ своего резидентного множества кортежей и сравнения для каждого кортежа значения атрибута кортежа с требуемым значением. Если ВМ обнаруживает, что значение атрибута очередного кортежа удовлетворяет оператору селекиии, то она сохраняет кортеж (ссылку па кортеж). В параллельных системах операции агрегации обычно выполняются за две фазы. На первой фазе каждая ВМ вычисляет свое локальное значение. Кортежи считываются аналогично тому, как в операции селекции. На второй фазе глобальное значение вычисляется с использованием всех локальных значений и помещается либо в определенную ВМ, либо в управлявшую ЭВМ.
Для выполнения операции агрегации может быть сформирована структура межмодульных связей типа "дерево". В этом случае операция агрсгации выполняется следующим образом. На первом шаге листовые ВМ (т.е. не имевшие потомков) передают свои локально вычисленные значения операции агрегации ВМ-родителям. На последуюших шагах ВМ, принявшие сообщение от ВМ-потомков, вычисляют новое значение агрегации с учетом своих резидентных кортежей и передают его вверх по дереву ВМ-родителям. Этот процесс продолжается до тех пор, пока результат не достигнет корня дерева.
Число шагов Базы данных. Интеллектуальная обработка информации пересылки в таком алгоритме будет равно длине самой длинной ветви дерева. Иногда пользователь может пожелать вычислить какое-нибудь значение по категориям. Например, в БД населения страны пользователь может получить средний возраст населения каждого региона. В этом случае необходимо произвести перераспределение данных между ВМ так, чтобы в каждой ВМ находились данные, относящиеся к данной категории, затем в каждой ВМ вычисляется свое значение для резидентной категории.
Реализация операций, требующих участия всех кортежей Параллельные алгоритмы „осуществляющие ~по!бясап операции, могут быть разделены на основанные на трансляционной передаче отношений (Ьгоас1сак1) и основанные на блочной передаче отношений (Ьцс1се1). Первые требуют, чтобы каждая ВМ посылала фрагменты одного из отношений (в случае двухместного оператора) всем ВМ системы. Все ВМ принимают посланные сообщения (множества кортежей) и выполняют требуемые локальные вычисления с резидентными кортежами и с присланными в сообщениях кортежами, Алгоритмы, основанные на блочной передаче отношений, используют разбиение всех кортежей на блоки.
Каждому блоку соответствует диапазон значений атрибутов, и только кортежи, значения атрибутов которых лежат внутри данного диапазона, находятся в блоке. Блочный алгоритм включает в себя операции внутри блоков согласно значениям их атрибутов. Соединение по алгоритму, основанному на трансляционной передаче отношения Рассмотрим пример, поясняющий суть алгоритма, Выполним соединение двух отношений Р и Т на атрибуте В, ЩАВСО)=Р1АВС1 9 Т[В01, на системе из трех ВМ при фрагментации отношений„показанной на рис. 10.5. На рис.10.5 отношение Р показано как верхнее отношение. ВМ1 имеет 4 кортежа, два Р и два Т. ВМ2 тоже имеет 2 кортежа из Р и два кортежа из Т.
ВМЗ имеет только 3 кортежа Т. Отношение Р состоит из меньшего числа кортежей, следовательно, это меньшее отношение. Алгоритм соединения, основанный на трансляционной передаче отношений, выполняется следующим образом. Исходя из того, что Р— меньшее отношеиие, каждая ВМ посылает каждый кортеж Р во все другие ВМ. Таким образом, ВМ1 посыласт кортежи <1,6,4> и <4,9,2>„ВМ2 посылает кортежи <2,6,4> и <3,4,1>, и ВМЗ не посылает никаких кортежей.
Конец пересылки кортежей обозначается посылкой стандартного сообщения. Все ВМ отслеживают передачу данных и вычисляют локальное соединение из присланных кортежей и имеющихся в ВМ кортежей из Т. Рис. 10.6 показывает результат соединения. Глава 10. Параллельные базы данных Рис. 10.5. Исходная фрагментация отношений Рис. 10.6.
Результат соединения по алгоритму, основанному на трансляиионной передаче отношения Алгоритм, основанный на трансляционной передаче кортежей отношения, уменьшает объем передаваемых кортежей за счет избыточных сравнений, что потенциально обеспечивает загрузку всех ВМ. Для повышения загрузки всех ВМ работой в ~76~ предложена трехстадийная реализация соединения. Первая стадия реализует динамический алгоритм перераспределения данных и имеет целью равномерное распределение исходных кортежей по ВМ. При этом, с одной стороны, увеличивается время перераспределения данных, но, с другой Базы данных. Интеллектуальная обработка информации стороны (приблизительно на 35%), уменьшается общее время выполнения операции соединения. На второй стадии сжатия и копирования отношений копируется меньшее отношение К1. Цель этого шага — увеличить число кортежей из К1, записанных в каждой ВМ, до тех пор, пока нс исчерпается свободная память в ВМ, или до тех пор, пока К1 не будет полностью скопировано во все ВМ.
На третьей стадии происходит собственно выполнение операции. Соединение по алгоритму, основанному на блочной передаче отношений Реализация алгоритма, основанного на блочной передаче отношений, начинается с определения максимально возможного диапазона соединяемых атрибутов. Этот диапазон состоит из действительно используемых в кортежах значений атрибутов и необязательно должен быть равен домену соединяемого(- мых) атрибута(тов). Например.
диапазон значений атрибута В соединяемых отношений Т и Р, приведенных на рис. 10.5, состоит из значений от 1 до 9 и обозначается как ацг-гап(К.В)=11..91. Однако дот(В) может заключать в себе более широкий диапазон, скажем, множество натуральных чисел. Более узкая граница а11г-гап(К.В) — это пересечение ацг-гап(Р.В)=14,91 и айг-гап(Т.В)=(1,71, называется максимальный диапазон атрибута  — айг-гап(В)=(4,71. А11г-гап(К.В) вычисляется один раз и разбивается на непересекающиеся поддиапазоны атрибутов, которые присваиваются (назначаются) каждой ВМ.
Разбивка диапазона между ВМ выполняется либо статически, либо динамически, При статическом разбиении ВМ загружены работой неравномерно всякий раз, когда значения атрибутов распределсны неравномерно. Динамическое разбиение диапазона исключает эффект асимметричного распределения кортежей. Это даст возможность при операции соединения загрузить ВМ работой примерно одинаково.
Однако все дшгамичсские загрузочно-балансировочные алгоритмы, динамические выборки приводят к увеличению времени обработки за счет пересылки кортежей. Пример, приведенный ниже, использует статическое разбиение. В ВМ1 помещаются кортежи со значением атрибута В= (4,51. В ВМ2 соответственно передаются кортежи со значением атрибута В = б, и ВМЗ получает кортежи со значением атрибута В = 7 соответственно. Все кортежи в обоих отношениях перераспределяются по ВМ в соответствии с назначенным ВМ значением атрибута В Когда перераспределение закончено, все ВМ вычисляют локальное соединение кортежей Р и Т.
Рис. 10.7 иллюстрирует распределение кортежсй по ВМ в результате работы операции соединения по алгоритму, основанному на блочной передаче отношений. Если сравнить с рис. 10.6, то видно, что получилось то же отношение, однако кортежи распределены по ВМ по другому. Глава 10. Параллельные базы данных Рис. 1О.7. Результат соединения по аягоритлп, основанному на блочной передаче отношений Сравнительный анализ алгоритмоа реализации соединения Реализация операции соединение с применением алгоритмов, основанных на трансляционной передаче кортежей, по сравнению с алгоритмами, использующими блочные передачи отношений, уменьшает число требуемых пересылок за счет избыточных сравнений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
