Погода в Санкт-Петербурге | Pogoda78.ru
Вариант решения домашнего задания №4 задача 1
Вариант решения домашнего задания №4 задача 1
а) Пусть требуется осуществить левое внешнее соединение отношений R и S. В результат этой операции должны войти все соединенные кортежи, образованные в результате естественного соединения отношений, а также кортежи вида (t, NULL) для всех кортежей t отношения R, которые не соединяются ни с одним из кортежей отношения S.
В зависимости от того, какое из отношений имеет меньший размер, могут использоваться два различных алгоритма.
1) Пусть R(X,Y) помещается в доступное пространство оперативной памяти.
Для функционирования алгоритма требуется создать в оперативной памяти хэш- структуру по атрибуту соединения Y для хранения отношения R. Если М – число доступных буферов оперативной памяти, то хэш- структура может состоять из М-1 сегмента.
Главной проблемой в этом случае является проблема определения, что кортеж отношения R не был соединен ни с одним кортежем отношения S. Здесь возможно использовать несколько вариантов.
Хэш- структура должна содержать расширенные кортежи отношения R ( к кортежу добавляется еще один атрибут – значение булевского типа, которое сигнализирует о факте соединения данного кортежа хотя бы с одним из кортежей отношения S). Вместо атрибута можно использовать один бит в заголовке записи, если для него есть место.
Пусть M-1 – четное число. Тогда можно положить, что кортеж может находиться в двух сегментах (например, с номерами h(Y) и M-2-h(Y)). Если кортеж еще не был соединен ни с одним из кортежей отношения S, то он должен быть помещен в сегмент с номером h(Y). При первом соединении этого кортежа с каким-либо кортежем отношения S он должен быть перенесен в сегмент с номером M-2-h(Y).
Читаем последовательно блоки отношения R, формируя в оперативной памяти хэш- структуру по атрибуту соединения Y, создавая M-1 сегментов (либо М-2 для II варианта определения факта соединения кортежей, если М- четно). В случае первого варианта в заголовок кортежей заносится 0.
Считываем последовательно в один буфер оперативной памяти по одному блоку отношения S. Для каждого кортежа q отношения S, загруженного в блок:
Находим с помощью хэш- структуры все кортежи отношения R, которые должны быть соединены с кортежем q. В случае первого варианта все такие кортежи находятся в одном сегменте. В случае второго варианта кортежи, которые можно соединить с кортежем q, могут находиться в каждом из двух сегментов с номерами h(Y) и M-2-h(Y).
Для каждого найденного в хэш- структуре кортежа t формируем кортеж соединения и записываем его в буфер вывода. В случае первого варианта атрибут кортежа t или бит в заголовке кортежа устанавливается в 1, что означает соединение этого кортежа с кортежем отношения S. В случае второго варианта те кортежи отношения R, которые были найдены в сегменте с номером h(Y) должны быть перенесены в сегмент с номером M-2-h(Y).
После просмотра всех блоков отношения S требуется просмотреть всю хэш- структуру на предмет нахождения всех кортежей отношения R, которые не были соединены ни с одним из кортежей отношения S. В случае первого варианта нужно просмотреть все сегменты, копируя в буфер вывода кортежи (X, Y, NULL) для тех кортежей t отношения R, бит в заголовке кортежа (или соответствующий атрибут) которого равен 0. В случае же второго варианта кортеж (X, Y, NULL) копируется в буфер вывода для тех кортежей t отношения R, которые находятся в сегменте с номером h(Y) (Y- значение атрибута соединения кортежа t).
2) Пусть теперь S(Y, Z) помещается в доступное пространство оперативной памяти. Тогда алгоритм левого внешнего соединения будет значительно проще.
1. Читаем последовательно блоки отношения S, формируя в оперативной памяти хэш- структуру по атрибуту соединения Y, создавая M-1 сегментов.
Считываем последовательно в один буфер оперативной памяти по одному блоку отношения R. Для каждого кортежа t отношения R, загруженного в блок:
Находим с помощью хэш- структуры все кортежи отношения S, которые должны быть соединены с кортежем t. Формируем для них кортеж соединения и записываем его в буфер вывода.
Если для кортежа t не было найдено ни одного кортежа отношения S, соединяющегося с ним, формируем кортеж (X,Y, NULL) и переносим его в буфер вывода.
б) Требуется осуществить полусоединение отношений R(X,Y) и S(Y,Z). Результатом такой операции является множество тех кортежей отношения R, которые соединяются хотя бы с одним из кортежей отношения S.
Пусть отношение R помещается в доступном пространстве оперативной памяти (М буферов). Тогда алгоритм выполнения полусоединения отношений R и S будет следующим:
1. Последовательно читаются блоки отношения R, формируется в оперативной памяти хэш- структура по атрибуту соединения Y, занимающая M-1 буферов оперативной памяти и состоящая из М-1 сегмента.
2. Считываем последовательно блоки отношения S. Для каждого кортежа q блока ищем кортежи отношения R, которые могли бы соединиться с кортежем q. Каждый найденный в хэш-структуре кортеж t отношения R записывается в буфер вывода и удаляется из хэш-структуры (чтобы в результирующем множестве не было дубликатов).
Пусть отношение S помещается в доступном пространстве оперативной памяти. Тогда алгоритм выполнения полусоединения отношений R и S будет следующим:
1.Считываются последовательно блоки отношения S, формируется в оперативной памяти хэш- структура по атрибуту соединения Y, состоящая из М-1 сегмента.
2. Считываются последовательно блоки отношения R. Для каждого кортежа t отношения R ищутся кортежи отношения S в хэш- структуре, которые могли бы быть соединены с кортежем t. Если найден хотя бы один такой кортеж, t записывается в буфер вывода. В противном случае, t игнорируется.
Требуется провести гибридное хэш- соединение отношений R и S при следующих исходных данных:
B(R)=1700, B(S)=500, M=101.
Отношения хэшируются на k сегментов. Меньшим из отношений является отношение S, следовательно, требуется хранить в оперативной памяти именно m сегментов хэш- структуры отношения S. В этом случае k-m сегментов должны иметь в оперативной памяти по одному буферу для их формирования. Один буфер следует оставить для последовательной подкачки блоков отношений. Оценка размера сегмента отношения S составляет . Тогда ограничение на размер оперативной памяти имеет следующий вид: . Экономия по сравнению с обычным хэш –соединением при этом (оценка с округлениями) составляет .
Пусть m=1. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 6. Для более точной оценки требуется проверить это ограничение на реальном размере сегмента, т.е. k должно удовлетворять неравенству . k=6 неравенству удовлетворяет.
Размер сегмента отношения S = блока.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 84(1 сегмент целиком в оперативной памяти)+5(для остальных сегментов)+1(для последовательной подкачки блоков отношений) = 90 буферов.
Пусть m=2. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 11. Однако при данном k нарушается более точное ограничение . Поэтому k=12.
Размер сегмента отношения S = блока.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 2*42(2 сегмента целиком в оперативной памяти)+10(для остальных сегментов)+1(для подкачки блоков отношений) = 95 буферов.
Пусть m=3. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 18. Это значение k удовлетворяет неравенству, построенному для реального размера сегмента .
Размер сегмента отношения S = блоков.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 3*28(3 сегмента целиком в оперативной памяти)+15(для остальных сегментов)+1(для подкачки блоков отношений) = 100 буферов.
В данном случае уже можно остановить перебор, поскольку неиспользованным остается всего один буфер, что, в принципе, приемлемое незадействованное пространство.
Число операций ввода/вывода = операции ввода/вывода.
Среднее время работы алгоритма = 32,4* 5 862 = 189 928,8 мс = 3,165 мин.
а) Поиск всех книг с ценой 100 рублей ( ).
Вариант 1. Отношение Book кластеризовано, индекс не используется. Тогда число операций ввода/вывода = B(Book) = 250.
Вариант 2. Отношение Book некластеризованное, индекс не используется. Тогда число операций ввода/вывода = T(Book) = 2 500.
Вариант 3. Использование индекса. Так как этот индекс должен быть построен по атрибуту Price, индекс является вторичным, так что весьма маловероятно, что он может быть кластеризованным. Следовательно, число операций ввода/вывода = .
б) Производится естественное соединение отношений Order и Customer.
1. Пусть используется однопроходной алгоритм соединения отношений Order и Customer.
Требуется выполнить B(Order)+B(Customer) = 2 500+700 = 3 200 операций ввода/вывода.
Требование к размеру M доступного пространства оперативной памяти – меньшее из отношений должно помещаться в M -1 буфер оперативной памяти.
2. Пусть используется двухпроходной алгоритм соединения отношений Order и Customer, основанный на хэшировании.
Хэшируем отношение Customer в M-1 сегментов хэш- структуры по атрибуту соединения CustID. Один сегмент будет иметь длину = 700/(М-1) блоков. Записываем хэш- структуру на диск.
Хэшируем отношение Order в M-1 сегментов хэш- структуры по атрибуту соединения CustID. Один сегмент будет иметь длину = 2 500/(М-1) блоков. Записываем хэш- структуру на диск.
Соединяем соответствующие по номерам сегменты хэш-структур двух отношений. Для проведения соединения сегментов требуется, чтобы меньший из них помещался в М-1 буфер оперативной памяти, так как один буфер используется для последовательного просмотра блоков сегмента другого отношения. В нашем случае получим, что
Таким образом, получим, что . Наименьшее положительное целое число, удовлетворяющее данному неравенству 28.
Следовательно, для проведения такого алгоритма требуется как минимум 28 буферов оперативной памяти.
Всего потребуется провести 3(B(Order)+B(Customer))=3*(2 500+700)=9 600 операций ввода/вывода.
Пусть используется двухпроходной алгоритм соединения отношений Order и Customer, основанный на сортировке.
Первоначально требуется создать отсортированные подсписки соединяющихся отношений каждый длиной M блоков.
Количество списков отношения Customer = .
Количество списков отношения Order = .
На втором проходе алгоритма потребуется использовать по одному буферу оперативной памяти под каждый из сформированных подсписков. Игнорируя буфер вывода, получим, что . Немного ослабив неравенство (без учета округлений), получим, что размер памяти должен удовлетворять неравенству . Минимальное целое число, удовлетворяющее этому неравенству, M=57.
Количество операций ввода/вывода для соединения с сортировкой = =9 600 операций ввода/вывода.
Пусть используется двухпроходной алгоритм, основанный на сортировке. Известно, что отношение Customer уже отсортировано, т.е. выполнять работу по его сортировке не требуется. Первый проход при этом будет заключаться в формировании отсортированных подсписков кортежей отношения Order, каждый из которых будет иметь размер в M блоков. Таким образом, на втором проходе получим списков отношения Order и 1 список отношения (само отношение) Customer. Общее число списков не должно превышать M. Огрубив условие (устранив из условия округление), получим, что требуется, чтобы выполнялось неравенство . Наименьшее целое M, удовлетворяющее этому неравенству, M=51.
При выполнении алгоритма требуется всего один раз считывать отношение Customer, блоки же отношения Order должны подвергаться трем операциям ввода/вывода, как в при обычном алгоритме, основанном на сортировке.
Количество операций ввода/вывода = 3B(Order)+B(Customer)=7500+700= 8 200.
Исследуем теперь работу алгоритма, основанного на использовании индекса отношения Order по атрибуту CustID. Для работы этого алгоритма требуется только 2 буфера оперативной памяти – первый используется для последовательной подкачки блоков отношения Customer, второй – для подкачки блоков отношения Order, в которых находятся кортежи, найденные с помощью индекса.
Количество кортежей отношения Order, которые соединяются с заданным кортежем отношения Customer = . Поскольку отношение Order имеет в качестве ключевого атрибута OrderID, то в худшем случае можно ожидать, что эти 5 кортежей будут попадать в различные блоки отношения Order, т.е. для каждого кортежа отношения Customer потребуется прочитать 5 блоков отношения Order.
Таким образом, количество операций ввода/вывода составляет = 700 + 10 000*5 = 50 700.
Решение задач «Индивидуальное домашнее задание № 4»,
Математика
Выполнить в ворде "Индивидуальное домашнее задание № 4" Вариант 1 на стр 105 и оформить по образцу на стр 125-132. подробно!
Закажите подобную или любую другую работу недорого
Вы работаете с экспертами напрямую,
не переплачивая посредникам, поэтому
наши цены в 2-3 раза ниже 
Последние размещенные задания
Срок сдачи к 20 дек.
Решить 2 задачи на массивы в С
Решение задач, Информатика и программирование
Срок сдачи к 15 дек.
Проблема этногенеза восточных славян
Срок сдачи к 13 дек.
Влияние внешней среды на успешность деятельности организации
Курсовая, Теория управления
Срок сдачи к 19 дек.
Составить презентацию на 12-14. Небольшая презентация.
Презентация, юридическая психология
Срок сдачи к 12 дек.
Решить три задачи по статистике
Решение задач, Статистика
Срок сдачи к 11 дек.
На барабан диаметром 1 мнамотано в один ряд 50 витков медной проволоки.
Решение задач, Геометрия
Срок сдачи к 10 дек.
Написать Предметно аналитическую справку с использованием gretl
Срок сдачи к 13 дек.
Оформить как в примере
Решение задач, теоретическая механика
Срок сдачи к 15 дек.
Отчет по практике, земельно-имущественные отношения, земельное право
Срок сдачи к 14 дек.
Решить контрольную по римскому праву
Контрольная, римское право
Срок сдачи к 15 дек.
решить задачу желательно сегодня
Решение задач, Физика
Срок сдачи к 10 дек.
Лабораторная работа № 6. циклические операторы в среде программирования matlab
Лабораторная, Математические методы
Срок сдачи к 18 дек.
Ответы на билеты
Ответы на билеты, русский язык и культура речи
Срок сдачи к 13 дек.
Реферат по предмету «Физкультура»
Срок сдачи к 16 дек.
Срок сдачи к 11 дек.
Практическая работа 1
Решение задач, Экология
Срок сдачи к 13 дек.
Лабораторная работа №5. основы программирования в matlab
Лабораторная, Математика Matlab
Срок сдачи к 16 дек.
обратились к нам
за последний год
работают с нашим сервисом
заданий и консультаций
заданий и консультаций
выполнено и сдано
за прошедший год
Сайт бесплатно разошлёт задание экспертам.
А эксперты предложат цены. Это удобнее, чем
искать кого-то в Интернете 
Отклик экспертов с первых минут
С нами работают более 15 000 проверенных экспертов с высшим образованием. Вы можете выбрать исполнителя уже через 15 минут после публикации заказа. Срок исполнения — от 1 часа
Цены ниже в 2-3 раза
Вы работаете с экспертами напрямую, поэтому цены
ниже, чем в агентствах
Доработки и консультации
– бесплатны
Доработки и консультации в рамках задания бесплатны
и выполняются в максимально короткие сроки
Гарантия возврата денег
Если эксперт не справится — мы вернем 100% стоимости
На связи 7 дней в неделю
Вы всегда можете к нам обратиться — и в выходные,
и в праздники
Эксперт получил деньги за заказ, а работу не выполнил?
Только не у нас!
Деньги хранятся на вашем балансе во время работы
над заданием и гарантийного срока
Гарантия возврата денег
В случае, если что-то пойдет не так, мы гарантируем
возврат полной уплаченой суммы
С вами будут работать лучшие эксперты.
Они знают и понимают, как важно доводить
работу до конца 
С нами с 2017
года
Помог студентам: 11 307 Сдано работ: 11 307
Рейтинг: 86 201
Среднее 4,94 из 5
С нами с 2018
года
Помог студентам: 7 810 Сдано работ: 7 810
Рейтинг: 72 310
Среднее 4,87 из 5
С нами с 2019
года
Помог студентам: 2 500 Сдано работ: 2 500
Рейтинг: 27 657
Среднее 4,84 из 5
С нами с 2018
года
Помог студентам: 2 180 Сдано работ: 2 180
Рейтинг: 13 968
Среднее 4,87 из 5
1. Сколько стоит помощь?
Цена, как известно, зависит от объёма, сложности и срочности. Особенностью «Всё сдал!» является то, что все заказчики работают со экспертами напрямую (без посредников). Поэтому цены в 2-3 раза ниже.
Специалистам под силу выполнить как срочный заказ, так и сложный, требующий существенных временных затрат. Для каждой работы определяются оптимальные сроки. Например, помощь с курсовой работой – 5-7 дней. Сообщите нам ваши сроки, и мы выполним работу не позднее указанной даты. P.S.: наши эксперты всегда стараются выполнить работу раньше срока.
3. Выполняете ли вы срочные заказы?
Да, у нас большой опыт выполнения срочных заказов.
4. Если потребуется доработка или дополнительная консультация, это бесплатно?
Да, доработки и консультации в рамках заказа бесплатны, и выполняются в максимально короткие сроки.
5. Я разместил заказ. Могу ли я не платить, если меня не устроит стоимость?
Да, конечно - оценка стоимости бесплатна и ни к чему вас не обязывает.
6. Каким способом можно произвести оплату?
Работу можно оплатить множеством способом: картой Visa / MasterCard, с баланса мобильного, в терминале, в салонах Евросеть / Связной, через Сбербанк и т.д.
7. Предоставляете ли вы гарантии на услуги?
На все виды услуг мы даем гарантию. Если эксперт не справится — мы вернём 100% суммы.
Все домашние задания, 4 класс, Решения, Пояснения, Рекомендации, 2012
К сожалению, на данный момент у нас невозможно бесплатно скачать полный вариант книги.
Но вы можете попробовать скачать полный вариант, купив у наших партнеров электронную книгу здесь, если она у них есть наличии в данный момент.
Также можно купить бумажную версию книги здесь.
Все домашние задания, 4 класс, Решения, Пояснения, Рекомендации, 2012.
Пособие содержит подробные решения, комментарии, пояснения всех домашних заданий ко всем основным учебникам, рекомендованным Министерством образования и науки РФ, по русскому языку, математике, литературному чтению, окружающему миру, информатике, английскому и немецкому языкам. В конце книги приводятся образцы сочинений.
Эта книга поможет родителям и репетиторам проконтролировать правильность выполнения учащимся домашнего задания.
Примеры.
Из двух городов, расстояние между которыми 1200 км, одновременно навстречу друг другу выехали два поезда. Через 6 ч они встретились. Найди скорость второго поезда, если средняя скорость первого поезда была 98 км/ч. Решение.
1) 98 • 6 = 588 (км) — прошел первый поезд
2) 1200 - 588 = 612 (км) — прошел второй поезд
3) 612:6 = 102 (км/ч)
Выражение: (1200 - 98 • 6): 6 - 102 (км/ч).
Ответ: средняя скорость второго поезда 102 км/ч.
Who do you depend on?
Do you fight with your friends?
Does your father smoke?
How long do you prepare for your lessons?
Have you ever sailed?
Are you interested in travelling?
Who discovered America?
морковь, слива, кукуруза, огурец
1) полевые культуры;
2) овощные культуры;
3) плодовые культуры;
4) цветочные культуры.
СОДЕРЖАНИЕ
Решение упражнений к учебнику «МАТЕМАТИКА» М. И. Моро и др.
Решения
Решение упражнений к учебнику «МАТЕМАТИКА» В. Н. Рудницкой
Решения
Решение упражнений к учебнику «МАТЕМАТИКА» Н. Б. Истоминой
Решения
Решение упражнений к учебнику «МАТЕМАТИКА» Л. Г. Петерсон
Решения
Решение упражнений к учебнику «РУССКИЙ ЯЗЫК» Т. Г. Рамзаевой
Решения
Решение упражнений к учебнику «РУССКИЙ ЯЗЫК» Л. М. Зелениной. Т. Е. Хохловой
Решения
Решение упражнений к учебнику «РУССКИЙ ЯЗЫК» Р. Н. Бунеева и др.
Решения
Решение упражнений к учебнику «АНГЛИЙСКИЙ ЯЗЫК» И. Н. Верещагиной, О. В. Афанасьевой
Решения
Решение упражнений к учебнику «АНГЛИЙСКИЙ ЯЗЫК» М. З. Биболетовой и др.
Решения
Решение упражнений к рабочей тетради «АНГЛИЙСКИЙ ЯЗЫК» М. З. Биболетовой и др.
Решения
Решение упражнений к учебнику «НЕМЕЦКИЙ ЯЗЫК» И. Л. Бим. Л. И. Рыжовой
Решения
Решение упражнений к учебнику «НЕМЕЦКИЙ ЯЗЫК» Н. Д. Гальсковой и др.
Решения
Решение упражнений к учебнику «ЛИТЕРАТУРНОЕ ЧТЕНИЕ» Л. А. Ефросининой
Решения
Решение упражнений к учебнику «МИР ВОКРУГ НАС» А. А. Плешакова
Решения
Решение упражнений к рабочей тетради «МИР ВОКРУГ НАС» А. А. Плешакова
Решения
Решение упражнений к учебнику «ИНФОРМАТИКА В ИГРАХ И ЗАДАЧАХ» А. В. Горячева
Решения
Образцы сочинений
Сочинения.
По кнопкам выше и ниже «Купить бумажную книгу» и по ссылке «Купить» можно купить эту книгу с доставкой по всей России и похожие книги по самой лучшей цене в бумажном виде на сайтах официальных интернет магазинов Лабиринт, Озон, Буквоед, Читай-город, Литрес, My-shop, Book24, Books.ru.
По кнопке «Купить и скачать электронную книгу» можно купить эту книгу в электронном виде в официальном интернет магазине «ЛитРес» , и потом ее скачать на сайте Литреса.
По кнопке «Найти похожие материалы на других сайтах» можно найти похожие материалы на других сайтах.
On the buttons above and below you can buy the book in official online stores Labirint, Ozon and others. Also you can search related and similar materials on other sites.
Решебник по математике 4 класс Чеботаревская
В этом учебном году ребенку предстоит повторить весь предыдущий материал предмета и подготовиться к переходу на следующий этап обучения. «ГДЗ по математике для 4 класса Чеботаревская (Начальная школа)» создан специально для того, чтобы каждый ученик смог подтянуть свои слабые стороны и как следует усвоить программу.
Курс для четвероклассников кажется несложным на первый взгляд. Однако не все так однозначно. Ведь далеко не каждый ребенок схватывает материал «на лету». Для того, чтобы справиться с возникающими сложностями, школьнику рекомендуется применять решебник. Он поможет учащемуся не отставать от остального класса и быстро наверстать упущенный материал в комфортной домашней обстановке.
Онлайн-решебник по математике для 4 класса Чеботаревская для младшего школьника
Значительная часть жизни современного человека связана с интернетом. И вот уже школьное образование стремительно переходит в режим онлайн. Чем раньше ребенок научится грамотно пользоваться мировой паутиной, тем больше образовательных возможностей у него появится со временем. Онлайн-решебник отлично способствует этому. Ведь применяя его, школьник учится:
- искать необходимую информацию и применять ее на практике;
- самостоятельно проверять домашнее задание;
- своевременно находить и исправлять ошибки;
- контролировать свою успеваемость.
Пособие содержит правильные ответы на все задания из одноименного учебника, а его интерфейс порадует своим удобством. Поэтому ребенок сможет без труда найти необходимый пример или задачу.
Как помочь ученику раскрыть свой потенциал
Каждый родитель мечтает о том, чтобы его ребенок хорошо учился, был внимательным и ответственным. Применяя «ГДЗ по математике для 4 класса Чеботаревская Т.М., Николаева В.Н. (Начальная школа)» маленький ученик сможет раскрыть свои образовательные способности. Главное - пользоваться решебником с умом и не допускать бездумного списывания. С его помощью, ребенок сможет выполнить домашнее задание, подготовиться к уроку и проверочным работам, разобраться в новом материале и повторить пройденные темы, поднимать руку, чаще выходить к доске и уверенно отвечать перед классом. Задача родителей - научить малыша правильно использовать решебник. Если применять его как дополнение к решебнику, то можно довольно быстро повысить уровень знаний. Это позитивно скажется на успеваемости и мотивации ученика.
Вариант решения домашнего задания №4. Задача 1
а) Пусть требуется осуществить левое внешнее соединение отношений R и S. В результат этой операции должны войти все соединенные кортежи, образованные в результате естественного соединения отношений, а также кортежи вида (t, NULL) для всех кортежей t отношения R, которые не соединяются ни с одним из кортежей отношения S.
В зависимости от того, какое из отношений имеет меньший размер, могут использоваться два различных алгоритма.
1) Пусть R(X,Y) помещается в доступное пространство оперативной памяти.
Для функционирования алгоритма требуется создать в оперативной памяти хэш- структуру по атрибуту соединения Y для хранения отношения R. Если М – число доступных буферов оперативной памяти, то хэш- структура может состоять из М-1 сегмента.
Главной проблемой в этом случае является проблема определения, что кортеж отношения R не был соединен ни с одним кортежем отношения S. Здесь возможно использовать несколько вариантов.
Хэш- структура должна содержать расширенные кортежи отношения R ( к кортежу добавляется еще один атрибут – значение булевского типа, которое сигнализирует о факте соединения данного кортежа хотя бы с одним из кортежей отношения S). Вместо атрибута можно использовать один бит в заголовке записи, если для него есть место.
Пусть M-1 – четное число. Тогда можно положить, что кортеж может находиться в двух сегментах (например, с номерами h(Y) и M-2-h(Y)). Если кортеж еще не был соединен ни с одним из кортежей отношения S, то он должен быть помещен в сегмент с номером h(Y). При первом соединении этого кортежа с каким-либо кортежем отношения S он должен быть перенесен в сегмент с номером M-2-h(Y).
Читаем последовательно блоки отношения R, формируя в оперативной памяти хэш- структуру по атрибуту соединения Y, создавая M-1 сегментов (либо М-2 для II варианта определения факта соединения кортежей, если М- четно). В случае первого варианта в заголовок кортежей заносится 0.
Считываем последовательно в один буфер оперативной памяти по одному блоку отношения S. Для каждого кортежа q отношения S, загруженного в блок:
После просмотра всех блоков отношения S требуется просмотреть всю хэш- структуру на предмет нахождения всех кортежей отношения R, которые не были соединены ни с одним из кортежей отношения S. В случае первого варианта нужно просмотреть все сегменты, копируя в буфер вывода кортежи (X, Y, NULL) для тех кортежей t отношения R, бит в заголовке кортежа (или соответствующий атрибут) которого равен 0. В случае же второго варианта кортеж (X, Y, NULL) копируется в буфер вывода для тех кортежей t отношения R, которые находятся в сегменте с номером h(Y) (Y- значение атрибута соединения кортежа t).
2) Пусть теперь S(Y, Z) помещается в доступное пространство оперативной памяти. Тогда алгоритм левого внешнего соединения будет значительно проще.
Считываем последовательно в один буфер оперативной памяти по одному блоку отношения R. Для каждого кортежа t отношения R, загруженного в блок:
Находим с помощью хэш- структуры все кортежи отношения S, которые должны быть соединены с кортежем t. Формируем для них кортеж соединения и записываем его в буфер вывода.
Если для кортежа t не было найдено ни одного кортежа отношения S, соединяющегося с ним, формируем кортеж (X,Y, NULL) и переносим его в буфер вывода.
б) Требуется осуществить полусоединение отношений R(X,Y) и S(Y,Z). Результатом такой операции является множество тех кортежей отношения R, которые соединяются хотя бы с одним из кортежей отношения S.
Пусть отношение R помещается в доступном пространстве оперативной памяти (М буферов). Тогда алгоритм выполнения полусоединения отношений R и S будет следующим:
1. Последовательно читаются блоки отношения R, формируется в оперативной памяти хэш- структура по атрибуту соединения Y, занимающая M-1 буферов оперативной памяти и состоящая из М-1 сегмента.
2. Считываем последовательно блоки отношения S. Для каждого кортежа q блока ищем кортежи отношения R, которые могли бы соединиться с кортежем q. Каждый найденный в хэш-структуре кортеж t отношения R записывается в буфер вывода и удаляется из хэш-структуры (чтобы в результирующем множестве не было дубликатов).
Пусть отношение S помещается в доступном пространстве оперативной памяти. Тогда алгоритм выполнения полусоединения отношений R и S будет следующим:
1.Считываются последовательно блоки отношения S, формируется в оперативной памяти хэш- структура по атрибуту соединения Y, состоящая из М-1 сегмента.
2. Считываются последовательно блоки отношения R. Для каждого кортежа t отношения R ищутся кортежи отношения S в хэш- структуре, которые могли бы быть соединены с кортежем t. Если найден хотя бы один такой кортеж, t записывается в буфер вывода. В противном случае, t игнорируется.
Задача 2.
Требуется провести гибридное хэш- соединение отношений R и S при следующих исходных данных:
B(R)=1700, B(S)=500, M=101.
Отношения хэшируются на k сегментов. Меньшим из отношений является отношение S, следовательно, требуется хранить в оперативной памяти именно m сегментов хэш- структуры отношения S. В этом случае k-m сегментов должны иметь в оперативной памяти по одному буферу для их формирования. Один буфер следует оставить для последовательной подкачки блоков отношений. Оценка размера сегмента отношения S составляет . Тогда ограничение на размер оперативной памяти имеет следующий вид: . Экономия по сравнению с обычным хэш –соединением при этом (оценка с округлениями) составляет .
Пусть m=1. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 6. Для более точной оценки требуется проверить это ограничение на реальном размере сегмента, т.е. k должно удовлетворять неравенству . k=6 неравенству удовлетворяет.
Размер сегмента отношения S = блока.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 84(1 сегмент целиком в оперативной памяти)+5(для остальных сегментов)+1(для последовательной подкачки блоков отношений) = 90 буферов.
Пусть m=2. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 11. Однако при данном k нарушается более точное ограничение . Поэтому k=12.
Размер сегмента отношения S = блока.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 2*42(2 сегмента целиком в оперативной памяти)+10(для остальных сегментов)+1(для подкачки блоков отношений) = 95 буферов.
Пусть m=3. Тогда требуется минимизировать k при ограничении . Минимальное k, удовлетворяющее ограничениям – k = 18. Это значение k удовлетворяет неравенству, построенному для реального размера сегмента .
Размер сегмента отношения S = блоков.
Таким образом, при первом проходе гибридного хэш- соединения будет задействовано 3*28(3 сегмента целиком в оперативной памяти)+15(для остальных сегментов)+1(для подкачки блоков отношений) = 100 буферов.
В данном случае уже можно остановить перебор, поскольку неиспользованным остается всего один буфер, что, в принципе, приемлемое незадействованное пространство.
Число операций ввода/вывода = операции ввода/вывода.
Среднее время работы алгоритма = 32,4* 5 862 = 189 928,8 мс = 3,165 мин.
Задача 3.
а) Поиск всех книг с ценой 100 рублей ().
Вариант 1. Отношение Book кластеризовано, индекс не используется. Тогда число операций ввода/вывода = B(Book) = 250.
Вариант 2. Отношение Book некластеризованное, индекс не используется. Тогда число операций ввода/вывода = T(Book) = 2 500.
Вариант 3. Использование индекса. Так как этот индекс должен быть построен по атрибуту Price, индекс является вторичным, так что весьма маловероятно, что он может быть кластеризованным. Следовательно, число операций ввода/вывода = .
б) Производится естественное соединение отношений Order и Customer.
1. Пусть используется однопроходной алгоритм соединения отношений Order и Customer.
Требуется выполнить B(Order)+B(Customer) = 2 500+700 = 3 200 операций ввода/вывода.
Требование к размеру M доступного пространства оперативной памяти – меньшее из отношений должно помещаться в M -1 буфер оперативной памяти.
2. Пусть используется двухпроходной алгоритм соединения отношений Order и Customer, основанный на хэшировании.
Хэшируем отношение Customer в M-1 сегментов хэш- структуры по атрибуту соединения CustID. Один сегмент будет иметь длину = 700/(М-1) блоков. Записываем хэш- структуру на диск.
Хэшируем отношение Order в M-1 сегментов хэш- структуры по атрибуту соединения CustID. Один сегмент будет иметь длину = 2 500/(М-1) блоков. Записываем хэш- структуру на диск.
Соединяем соответствующие по номерам сегменты хэш-структур двух отношений. Для проведения соединения сегментов требуется, чтобы меньший из них помещался в М-1 буфер оперативной памяти, так как один буфер используется для последовательного просмотра блоков сегмента другого отношения. В нашем случае получим, что
Таким образом, получим, что . Наименьшее положительное целое число, удовлетворяющее данному неравенству 28.
Следовательно, для проведения такого алгоритма требуется как минимум 28 буферов оперативной памяти.
Пусть используется двухпроходной алгоритм соединения отношений Order и Customer, основанный на сортировке.
Количество списков отношения Customer =.
Количество списков отношения Order =.
На втором проходе алгоритма потребуется использовать по одному буферу оперативной памяти под каждый из сформированных подсписков. Игнорируя буфер вывода, получим, что . Немного ослабив неравенство (без учета округлений), получим, что размер памяти должен удовлетворять неравенству . Минимальное целое число, удовлетворяющее этому неравенству, M=57.