Типы индексов

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

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

Вторичный индекс - это индекс, который определен на поле файла данных, отличном от поля, по которому выполняется упорядочение.

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов. Индекс может быть разреженным (sparse) или плотным (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле. Ключ поиска для индекса может состоять из нескольких полей.

Опр. Хеширование – метод доступа, обеспечивающий прямую адресацию данным путем преобразования значений ключа в относительный или абсолютный физический адрес.

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

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

Хеш-функция должна обеспечивать равномерное распределение ключей по адресам таблицы, однако двум разным ключам может соответствовать один адрес. Если адрес уже занят, возникает состояние, называемое коллизией, которое устраняется специальными алгоритмами: проверка идет к следующей ячейке до обнаружения своей ячейки. Элемент с ключом помещается в эту ячейку.

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

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

Простейшим алгоритмом хеширования может являться функция f(k)єk (mod 10), где k - ключ, целое число.

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

Индексированный последовательный файл имеет более универсальную структуру, которая обычно включает следующие компоненты:

• первичная область хранения;
• отдельный индекс или несколько индексов;
• область переполнения.

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

21. Назначение и общая характеристика языка SQL, структура операторов DML.

Язык SQL стал стандартным языком доступа к БД.

В его функции входят:

1. SQL позволяет определить данные и манипулировать данными;

2. Содержит специальные средства определения ограничений целостности БД;

3. Осуществляет авторизацию доступа к объектам БД.

Язык SQL является непроцедурным структурированным языком.

Язык SQL является реляционно-полным – любой оператор реляционной алгебры может быть выражен подходящим оператором SQL.

Операторы SQL:

Можно выделить следующие группы операторов:

1. Операторы DDL (Data Definition Language) - операторы определения объектов базы данных.

CREATE SCHEMA – создать схему базы данных; DROP SCHEMA –удалить схему; CREATE TABLE – создать таблицу; ALTER TABLE – изменить таблицу; DROP TABLE – удалить таблицу; CREATE DOMAIN – создать домен; ALTER DOMAIN – изменить домен; DROP DOMAIN – удалить домен; CREATE COLLATION – создать последовательность; DROP COLLATION – удалить; CREATE VIEW – создать представление; DROP VIEW – удалить представление;

2. Операторы DML (Data Manipulation Language) - операторы манипулирования данными.

SELECT – отобрать строки из таблиц; INSERT – добавить строки в таблицу;

UPDATE – изменить строки в таблице; DELETE – удалить строки в таблице;

COMMIT – зафиксировать внесенные изменения;

ROLLBACK – откатить внесенные изменения;

3. Операторы защиты и управления данными.

CREATE ASSERTION – создать ограничение;

DROP ASSERTION – удалить ограничение;

GRANT – предоставить привилегии пользователю или приложению на манипулирование объектами;

REVOKE – отменить привилегии пользователя или приложения;

Пример: Выбрать все данные из таблицы поставщиков (ключевые слова SELECT … FROM …): SELECT * FROM P;

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

Пример: Выбрать все строки из таблицы поставщиков, удовлетворяющих некоторому условию: SELECT * FROM P WHERE P.PNUM > 2, еще можно использовать логические операции (OR), предикаты (IN, BETWEEN)

Пример: Выбрать некоторые колонки из исходной таблицы, удалив из результата повторяющиеся строки (ключевое слово DISTINCT):

Пример: Найти всех заказчиков, чьи имена начинаются с буквы ‘К’:
SELECT * FROM Заказчики WHERE cname LIKE 'К%';

Пример: Найти наибольшую сумму приобретений, полученную каждым продавцом:
SELECT snum, MAX (amt) FROM ПорядкиGROUP BY snum;

Правое соединение: SELECT [Номер заказа], Фрукты.Наименование, Количество, Категория

FROM [Состав заказа] RIGHT JOIN Фрукты ON Фрукты. [Код фрукта]=[Состав заказа].Наименование;

ПРОСТОЙ ВЛОЖЕННЫЙ:

SELECT Наименование, [Опиcание фрукта], Категория, Cтоимоcть

FROM Фрукты

WHERE [Код фрукта] IN (SELECT Наименование

FROM [Состав заказа]);

22. ER-модели: основные определения. Правила преобразования ER-модели в

реляционную модель данных

Модель сущность-связь (ER-модель) — модель данных, позволяющая описывать концептуальные схемы предметной области.

Основные определения ER-модулей:

Опр. Сущность – это реальный или представляемый объект, информация в котором должна храниться в БД и быть допустимой.

Все сущности объединяются в (опр.) тип сущности – это множество объектов имеющих одинаковую структуру данных.

Опр. Сильные сущности – это сущности, существование которых в БД не зависит от сущности в БД других сущностей.

Опр. Связь – это графически изображенная ассоциация, устанавливаемая между сущностями.

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

Степень связи показывает, сколько сущностей участвует в связи.

Связь:

1) Обязательная (сплошная линия);

2) Необязательная (пунктирная линия).

Опр. Атрибут – любая деталь, которая служит для уточнения, идентификации, классификации числа характеристики или выражения состояния сущности.

Указание домена атрибута является необязательной процедурой.

ER – модули различают идентификатор. Это может быть атрибут, комбинация атрибутов, связь, комбинация связей, комбинация связей и атрибутов