3) Подведение итогов

SUMMARIZE <отношение> BY <список атрибутов> ADD <выражение 1> AS <имя 1>, ... , <выражение 1> AS <имя 1> Групповые вычисления. Аналогично EXTEND выполняется расчет значения и добавление нового атрибута под именем <имя>, но предварительно выполняется проецирование на атрибуты, указанные в <список атрибутов>. При проецировании множество кортежей исходного отношения разобьется на группы одинаковых строк отношения – проекции. Для каждой такой группы и выполняется расчет <выражение>. Так как <выражение> применяется к группе, оно должно быть обязательно итоговой функцией от атрибута или скалярного выражения, применяемой уже не к списку скалярных значений, а к столбцу значений в одной такой группе.

19. Внутренняя модель данных. Индексы и их разновидности. Плюсы и минусы индексации. Внутренняя модель данных.

Индекс – это таблица, состоящая из двух полей, первое поле – это ключ, второе поле – это ссылка на запись в БД с этим ключом индексации.

Индекс – объект базы данных, создаваемый с целью повышения производительности поиска данных.

Индекс позволяет выполнить две работы:

1) Выполнить сортировку файла не перемещая физически его записи;

2) Ускорить поиск информации.

Виды индексов:

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

Битовые индексы. Предположим, что в индексированной таблице т содержится п строк. Тогда битовый индекс для столбца с таблицы т будет содержать вектор из n битов для каждого возможного значения С и установленный бит будет соответствовать строке R, если в строке R содержится соответствующее значение из столбца С. Такие индексы позволяют эффективно выполнять запросы, в которых используются множества значений, но их эффективность снижается, если эти множества становятся слишком велики. Обратите внимание на то, что несколько реляционных операций (соединение, объединение, сокращение по равенству и т.п.) могут быть выполнены исключительно с индексами с помощью простых логических операций (AND, OR, NOT) над битовыми векторами. Доступ к реальным данным вообще не происходит до тех пор, пока не потребуется получение окончательного результирующего набора.

Хэшированные индексы (доступ с их использованием называется также хэш-адресацией или просто хэшированием). Хэшированные индексы эффективны для доступа к конкретным строкам, а не к диапазонам. Вычислительная стоимость зависит от количества строк линейно, при том условии, что хэш-функцию не требуется дополнять с учетом дополнительных значений ключа. Хэширование может также использоваться для эффективной реализации соединений.

Мулътитабличные индексы (иногда они называются индексами соединений). По существу, элемент мультитабличного индекса содержит указатели на строки в нескольких таблицах, а не просто указатели на строки в одной таблице. Такие индексы позволяют повысить производительность операций соединения и ускорить проверку ограничений целостности для нескольких таблиц.

Логические индексы (более известные как индексы на основе логических выражений). Логический индекс указывает, для каких строк определенной таблицы определенное логическое выражение (включающее столбцы рассматриваемой таблицы) принимает значение TRUE. Такие индексы особенно полезны, если соответствующее логическое выражение является общим компонентом условий операции сокращения.

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

Индексирование – в информационном поиске – процесс описания документов и запросов в терминах информационно-поискового языка. По результатам индексирования каждому документу назначается набор ключевых слов, отражающих его смысловое содержание.

Основной недостаток индексов в том, что трудно вносить изменения.

20. В-дерево. Создание, печать, добавление и удаление элементов.

B-дерево (Б-дерево) – структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.

Основной недостаток индексов в том, что трудно вносить изменения, а дерево упрощает внесение изменений, а сбалансированность позволяет ускорить поиск.

В основе В-дерева лежат следующие аксиомы:

1) В-дерево порядка n содержит 2n ключей 2n+1 ссылку;

2) В-дерево растет от листьев к корню;

3) Путь от корня к листу содержит одно и тоже количество шагов;

4) Каждый узел заполняется не менее чем на половину, кроме корня.

Ветвистость дерева — это свойство каждого узла дерева ссылаться на большое число узлов-потомков.

Назначение:

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

Структура и принципы построения:

B-деревом называется дерево, удовлетворяещее следующим свойствам:

1) Каждый узел содержит хотя бы один ключ. Ключи в каждом узле упорядочены. Корень содержит от 1 до 2n-1 ключей. Любой другой узел содержит от n-1 до 2n-1 ключей. Листья не являются исключением из этого правила. Здесь n - параметр дерева, не меньший 2.

2) У листьев потомков нет. Каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на сыновей.

3) Глубина всех листьев одинакова.

Поиск:

Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему сыну. Повторяем, пока не дошли до листа.

Добавление элементов:

Если в листе есть место, то ключ добавляется в сортированном порядке. Если нет места, то проверяется возможность балансировки, при этом выбирается либо 1 блок слева, либо справа. Если перетяжка невозможна, то блок делится на 2, n меньших ключей пересылаются в лево, n больших в право. Средний ключ выталкивается на уровень вверх.

Удаление элементов:

1) Если удаляемый ключ находится в листе, то он удаляется. И если количество записей становится меньше, чем n, то выполняется перетяжка либо из левого, либо из правого блока, таким образом чтобы количество колючей было ≥ n, но ≤ 2n. Если сумма ключей в обоих блоках недостаточна для перетяжки, то выполняется их объединение, и в них спускается ключ с верхнего уровня.

2) Если ключ находится не в листовой вершине, то он удаляется и заменяется на самый левый ключ, правого поддерева. При этом если в листе нехватка, то выполняется балансировка или слияние.