Файл: Базы Данных Теор. Экзамен.doc

Сначала определим размер индексной записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100 000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно 2 байт. Тогда длина индексной записи будет равна:

LI = LK + 2 = 14 + 2 = 14 байт.

Тогда количество индексных записей в одном блоке будет равно KIZB = LB/LI = 1 024/14 = 73 индексные записи в одном блоке. Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей:

KIB = KBO/KZIB = 12 500/73 = 172 блока.

 Тогда время доступа по прежней формуле будет определяться так:

T _поиска = log ₂ KIB + 1 = log ₂ 172 + 1 = 8 + 1 = 9 обращений к диску.

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

129. Что такое В-дереья? Как они строятся? Как рассчитать размер индексных файлов в виде В-деревьев?

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

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

В общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Исключение составляет самый нижний уровень, где расположены записи основной области. Именно эти записи и являются «листьями» (конечными вершинами) данного дерева. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Термин «сбалансированное» (от английского balanced — сбалансированный, взвешенный) и дал название данному методу организации индекса. Не путайте, пожалуйста, с двоичными деревьями, они также могут иметь сокращение B-tree (Binary Tree), но это совсем другая структура.

Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску.

На первом уровне, как нам известно, число блоков равно числу блоков основной области — 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс. Не будем менять длину индексной записи, а будем считать ее прежней, равной 14 байтам. Количество индексных записей в одном блоке нам тоже известно и равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока:

KIB 3 = KIB 2 /KZIB = 172/73 = 3 блока.

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

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

T_д = R_уровн. = 4.

Полученное B-дерево может быть представлено так, как изображено на рис. 11.5

130. Как строятся взаимосвязанные файлы с однонаправленными цепочками? Разработать алгоритмы удаления записей и добавления записей в данные файлы.

Моделирование отношения 1:М с использованием однонаправленных указателей

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

Основной файл F1

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

Структура подчиненного файла:

В качестве примера рассмотрим связь между преподавателями и занятиями, которые эти преподаватели проводят. В файле F1 приведен список преподавателей, а в файле F2 — список занятий, которые они ведут.

В этом случае содержимое двух взаимосвязанных файлов F1 и F2 может быть расшифровано следующим образом: первая запись в файле F1 связана с цепочкой записей файла F2, которая начинается с записи номер 1, следующая запись номер 4 и последняя запись в цепочке — запись номер 5. Последняя — потому, что пятая запись не имеет ссылки на следующую запись в цепочке. Аналогично можно расшифровать и остальные связи. Если мы проведем интерпретацию данных связей на уровне предметной области, то можно утверждать, что преподаватель Иванов ведет предмет «Вычислительные сети» в группе 4306, «Моделирование» в группе 84305 и «Вычислительные сети» в группе 4309.

Алгоритм нахождения нужных записей подчиненного файла

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

• Шаг 2. Анализируем указатель в основном файле. Если он пустой, т. е. стоит прочерк, значит, для этой записи нет ни одной связанной с ней записи в подчиненном файле. Выводим соответствующее сообщение, в противном случае переходим к шагу 3.

• Шаг 3. По ссылке-указателю в найденной записи основного файла переходим прямым методом доступа по номеру записи на первую запись в цепочке подчиненного файла. Переходим к шагу 4.

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

• Шаг 5. Анализируем указатель на следующую запись в цепочке. Если он пуст, то анализируем буфер; если буфер пуст, то выводим сообщение, что искомая запись отсутствует, и прекращаем поиск. В противном случае по ссылке-указателю переходим на следующую запись в подчиненном файле и снова переходим к шагу 4

131. Как строятся взаимосвязанные файлы с двунаправленными цепочками? Разработать алгоритмы удаления записей и добавления записей в данные файлы. Использование цепочек записей позволяет эффективно организовывать модификацию взаимосвязанных файлов. Для того чтобы эффективно использовать дисковое пространство при включении новой записи в подчиненный файл, ищем первое свободное место, т. е. запись, помеченную символом «*», и на ее место заносим новую запись, после этого производим модификацию соответствующих указателей. Необходимо различать 3 случая:

1) добавление записи на первое место в цепочке;

2) добавление записи в конец цепочки;

3) добавление записи на заданное место в цепочке.

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

Для нашего примера это выглядит следующим образом:

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

Рис. 11.5. Взаимосвязь двух основных и одного связующего файлов

132. Какие типы страниц используются в MSSQLServer? Как организованы страницы данных в MS SQL Server?

В SQL 2000 существуют 6 основных типов страниц:

• страница данных (Data page). В станицах этого типа хранятся структурированные данные, т. е. все типы данных, исключая тип text, ntext, image;

• индексные страницы (Index page). В страницах этого типа хранятся индексы;

• текстовые страницы (Text/image page). В страницах данного типа хранятся как раз слабоструктурированные данные типа text, ntext, image;

• карты распределения блоков (Global allocation map page), часто именуемые GAM. Этот тип страниц хранит информацию об использовании экстентов (блоков);

• карты свободного пространства (Page free space page). В страницах этого типа хранится информация о свободном пространстве на страницах;

• индексные карты размещения (Index Allocation Map page), называемые IAM. Страницы этого типа хранят информацию об экстентах, которые используются конкретными таблицами или индексами.

Организация страницы данных(параметры):

• номер страницы в формате <номер файла, номер страницы>;

• идентификатор объекта, которому принадлежит страница;

• номер индекса, которому принадлежит страница;

• уровень внутри индексного дерева, которому принадлежит страница;

• количество отведенных строк на странице, количество заполненных слотов;

• общий объем свободного пространства на странице;

• указатель на расположение свободного пространства после последней строки на странице;

• минимальная длина строки на странице;

• объем зарезервированного пространства.

Типовые задания

Задание 1. Написать запросы в реляционной алгебре

Даны отношения, моделирующие работу туристического агенства, имеющего много филиалов в различных странах:

R1

R2

R3

Составить запросы, позволяющие выбрать:

1. Клиентов, заключивших договоры с несколькими филиалами.

2. Филиалы, которые работают с клиентами только одной страны.

3. Клиентов, которые заключили несколько договоров с одним филиалом.

4. Филиалы, которые заключили договоры только с клиентами из той же станы, в которой расположен этот филиал.

5. Клиентов, которые заключили несколько договоров с разными филиалами.

6. Клиентов, которые заключили только один договор.

Задание 2.

Схема БД, которая моделирует работу с лицевыми счетами физических лиц.

Список всех атрибутов с указанием их типа

Физическая модель БД «bank» на сервере

Написать запросы на языке SQL

1. Вывести список филиалов банка, которые имеют минимальное количество счетов.

2. Вывести список районов с указанием количества филиалов банка, которые расположены в данном районе.

3. Вывести список счетов, которые открыты в филиале номер 1 нашего банка.

4. Вывести сумму вкладов на всех счетах филиала № 1

5. Вывести остаток на всех счетах господина Андреева А.А.

6. Вывести количество операций занесения денег на каждый счет, т.е. получить таблицу <счет, количество операций >

7. Вывести общую сумму снятых денег со всех счетов господина Андреева А.А.

8. Вывести список филиалов банка с указанием количества счетов каждого типа, открытых в данных филиалах.

9. Вывести список филиалов, в которых не открыто ни одного счета.

10. Вывести список клиентов, которые открыли счета, по которым не выполнено ни одной операции занесения или снятия денег.