Генерация схемы базы данных

Процесс генерации физической схемы БД из модели данных в ERwin называется пря-мым проектированием (Forward Engineering). При генерации физической схемы ERwin включает необходимые возможности, доступные при определении таблиц в выбранной СУБД. Для генерации БД следует выбрать пункт меню Tools/Forward Engineering. По-является соответствующий диалог. Закладка Options служит для задания вариантов ге-нерации объектов БД. Для задания генерации какого-либо объекта следует выбрать его в левом списке закладки, после чего включить соответствующий вариант в правом спи-ске. В закладке Summary отображаются все варианты, заданные в закладке Options.

Кнопка Generate запускает процесс генерации схемы. Возникает диалог связи с БД и начинает выполняться генерация. При этом возникает диалог Generate Database Schema, в котором можно выбрать дополнительные параметры генерации.

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

Отчёты

Для генерации отчетов в ERwin имеется специальный инструмент – Report Browser. Он позволяет выполнять предопределенные отчеты, сохранять результаты их выполнения, создавать собственные отчеты, печатать и экспортировать их в распространенные фор-маты. Каждый отчет может быть настроен индивидуально, данные в нем могут быть отсортированы и отфильтрованы.

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

Редактор Edit ERwin Report даёт возможность изменить любой существующий отчет.

Полученный после выполнения отчета набор данных можно отформатировать, распечатать, экспортировать или сохранить в виде представления. Для экспорта следу-ет выбрать в контекстном меню пункт Export result set. Допустимые форматы экспорта:

CSV – текстовый файл;

HTML;

DDE – экспорт в MS Word или MS Excel;

RPTwin – экспорт в специализированный генератор отчетов.

31. Транзакции. Плоские, многозвенные, вложенные транзакции.

Классическая транзакция – последовательность операций изменения базы данных или выборки, которая воспринимается СУБД как атомарное действие. Дисциплина транзакций включает различные функции для поддержки приложений, основанных на коммуникациях. Транзакция объединяет несколько действий, которые рассматриваются как единое целое. Это значит, что должно быть обозначено начало транзакции и её завершение, которое может быть как успешным, так и неуспешным. Во втором случае транзакция обязана вернуть базу данных в исходное состояние – откатить транзакцию. Принято считать, что любая транзакция основана на наборе принципов, называемом ACID:

атомарность (Atomicity) – выполнение действий по принципу «все или ничего»;

целостность (Consistency) – корректные преобразования состояний системы;

изолированность (Isolation) – данные, для которых нарушения целостности возникли в процессе выполнения транзакции, невидимы до фиксации;

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

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

правило фиксации – фиксация делает результаты видимыми только для родительского уровня;

правило отката – откат корневой транзакции ведет к откату всей иерархии;

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

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

32. SQL: общая характеристика. Простейшие запросы. Условия выбора. Примеры.

Язык, предназначенный для работы с реляционными базами данных – SQL (язык структурных запросов – Structured Query Language) – был призван продемонстрировать возможность эффективной работы с множествами, представленными отношениями. Возможности языка должны быть достаточными для реализации всех операторов реляционной алгебры. Язык должен быть непроцедурным – предполагалось, что таким образом облегчается работа пользователя, не умеющего программировать. Типы данных в различных версиях SQL могут заметно различаться, что связано с набором типов данных, принятом в конкретной СУБД. В стандарте ANSI рекомендуется использовать символьные (например, CHAR, VARCHAR) и числовые (INT, DEC) типы данных. Кратко и неформально структуру языка можно представить следующим образом. Язык состоит из команд, оканчивающихся точкой с запятой. Команды состоят из последовательности фраз, разделенных пробелами. Фразы состоят из ключевого слова, за которым через пробелы следуют аргументы.

Текст ::= команда; ... команда; Команда ::= фраза ... фраза

Фраза ::= Ключевое_слово аргумент аргумент ... аргумент

Основу языка SQL составляют запросы к базе данных. Запросы определяются командой Select. Простейшие запросы – отображение содержимого всей таблицы, проекция, перестановка атрибутов, выбор. Команда для них имеет следующий формат:

Select [Distinct] <список атрибутов> From<таблица> [Where <условие>];

Для удаления дублирующихся строк служит вариант Distinct. Предикат, определяющий условия выбора, может содержать обычные операции отношения (<, <=, =, <>, >=, >), операцию between … and … (истина, когда первый операнд не меньше второго и не больше третьего) и логические операции (and, or, not). Для задания множества служат круглые скобки, ограничивающие его определение. Множество может определяться как простым перечислением элементов, так и запросом. Последний вариант будет рассматриваться позже. Для определения принадлежности элемента множеству служит операция in. Для символьных значений допускается выбор по маске. Символ «%» маскирует любую цепочку в искомой строке, символ «_» лишь один символ, фраза like определяет маску.

33. SQL: функции агрегирования. Группировка, условия отбора групп. Примеры.

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

COUNT – количество непустых строк или значений атрибутов, отличных от null, удовлетворяющих заданному условию;

SUM – сумма значений атрибута;

AVG – среднее значение атрибута;

MAX – максимальное значение атрибута;

MIN – минимальное значение атрибута.

В команде Select они используются в списке выбираемых полей наряду с именами атрибутов. Их аргументы – имена атрибутов, причем, для SUM и AVG допустимы аргументы только числового типа. . Вариант COUNT(*) подсчитывает количество строк в выборке, включая и пустые, и повторяющиеся. Применять Distinct здесь нельзя. Вариант All позволяет считать все непустые значения атрибута, включая повторяющиеся.

Select COUNT(Distinctном_прод) FromЗаказ;

Select COUNT(Allсумма) FromЗаказ;

Select COUNT(*) FromПродавец;

Select SUM(сумма/1000) FromЗаказ;

Group By. Записи группируются по одинаковым значениям указанного атрибута. Если при этом в запросе участвует агрегатная функция, она выполняется для каждой группы.

Фраза Group By может содержать более одного атрибута, по которым группируются записи. В этом случае первый атрибут в списке определяет самую внешнюю группу, второй – группу внутри первой и т.п. При работе с группами данных может возникнуть необходимость отбирать группы по какому-нибудь признаку, например, определить общие суммы заказов по дням и среди них отобрать те, которые превышают некоторое число. Если бы дело касалось записей, задача легко решалась бы фразой Where: …Where сумма >…. Но к группе она неприменима. Для отбора групп по некоторому признаку используется фраза Having.

Select дата, Sum(сумма) FromЗаказ Group Byдата HavingSum(сумма)>5000;

34. SQL:соединение двух таблиц, более двух, соединение таблицы с собою. Примеры.

Select <список атрибутов> Fromr, s WhereA1 = B1 and A2 = B2 and… and Am = Bm;

В этом случае говорим о

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

Selectимя_пок, имя_прод, Покупатель.город FromПокупатель, Продавец WhereПокупатель.город=Продавец.город;

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

Select<список атрибутов> Fromr пн1, s пн2 …

Select<список атрибутов> Fromr Asпн1, s Asпн2 …

Здесь пн1 и пн2 – псевдонимы таблиц r и s соответственно.

Select a.имя_пок, b.имя_пок, a.значимость From Покупатель a, Покупатель b

Wherea.значимость=b.значимость; anda.имя_пок < b.имя_пок;

35. SQL: вложенные запросы. Примеры.

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

Select* FromЗаказ Whereном_прод = (Selectном_прод FromПродавец Whereимя_прод = ’Сидоров’); // Запрос корректен, если есть ровно один продавец Сидоров. Если такого нет – результат не определен, если их более одного – результат ошибочен.

Selectкомиссия FromПродавец Whereном_прод in(Selectном_прод FromЗаказ Whereном_пок in(Selectном_пок FromПокупатель Whereгород=’Москва’));

36. SQL: связанные запросы. Примеры.

Для реализации вложенного запроса может потребоваться информация из таблиц внешнего запроса. Запросы такого типа называются связанными.

Select* FromПокупатель a Where’03.10’ in(Selectдата FromЗаказ b Wherea.ном_пок=b.ном_пок);

При вычислении простого вложенного запроса внутренний подзапрос вычисляется автономно до выполнения внешнего запроса. Связанный запрос так выполнен быть не может: выполнение внутреннего подзапроса зависит от состояния таблиц, объявленных во внешнем запросе. Следовательно, внутренний подзапрос должен выполняться для каждой строки внешней таблицы, от которой он зависит. Итак, сформулируем правила выполнения связанных запросов.

1. Выбрать очередную строку внешней таблицы, от которой зависит внутренний подзапрос, она называется строкой-кандидатом.

2. Сохранить ее под псевдонимом, указанном во внешней фразе From.

3. Выполнить подзапрос. Используемые в подзапросе значения строки-кандидата называются внешними ссылками.

4. Оценить результат внешнего запроса на основании результата подзапроса.

5. Повторить процедуру для следующих строк внешней таблицы.

37. SQL: предикаты, определённые на подзапросах. Примеры.

В состав логических выражений SQL могут входить предикаты, определенные на подзапросах: признак того, что подзапрос не пуст (Exists), признак того, что все элементы удовлетворяют некоторому условию (All) и признак того, что существует хотя бы один элемент, удовлетворяющий некоторому условию (Any, Some). Функция Exists истинна, если ее аргумент (подзапрос) содержит хотя бы один элемент, в противном случае она ложна. Легко видеть, что в подзапросе этой функции использование агрегатных функций бессмысленно. Рассмотрим применение функции Exists на примерах.

Выбрать всех покупателей из Тулы, если хотя бы один из них сделал заказ:

Select* FromПокупатель Whereгород=’Тула’ and Exists(Select* FromЗаказ Whereном_пок in(Selectном_пок FromПокупатель Whereгород=’Тула’));

Предикат All имеет вид All <переменная> (<подзапрос>), где – операция сравнения. Он принимает истинное значение, если каждое значение подзапроса удовлетворяет условию, определяемому операцией . Естественно, этот предикат редко может применяться для операции равенства: в этом случае все элементы выборки должны быть равны между собой. Неравенство – более содержательная операция, она обозначает, что левая часть не равна ни одному из элементов выборки. Правда, этот предикат легко реализуется операцией in. Более интересны операции «больше», «меньше» и т.п.

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

Select* FromПокупатель Whereзначимость>All(Selectзначимость FromПокупатель

Whereгород =’Тула’);

Предикат Any (синоним – Some) имеет вид Any <переменная>(<подзапрос>), где – операция сравнения. Он принимает истинное значение, если хотя бы одно значение подзапроса удовлетворяет условию, определяемому операцией . Этот предикат чаще используется для операции равенства, чем для «больше», «меньше» и т.п.

Выбрать всех покупателей, живущих в городе, где есть продавец:

Select* FromПокупатель Whereгород= Any(Selectгород FromПродавец);

Для пустой выборки All принимает значение истина, Any и Exists – ложь. При сравнении с null предикаты Any и All принимают неопределенное значение, Exists никогда неопределенное значение не принимает.

38. SQL: объединение. Примеры.

Операция объединения реализуется фразой Union, которая объединяет два независимых подзапроса. Эта операция объединяет два множества в одно, значит, элементы исходных множеств должны быть однотипными. При объединении из результата автоматически исключаются тождественные строки, в отличие от команды Select. Чтобы их оставить, следует использовать вариант Union All.

Выбрать номера покупателей, значимость которых выше 200 или которые сделали заказ на сумму более 3000:

Selectном_пок FromПокупатель Whereзначимость>200

Union Selectном_пок FromЗаказ Whereсумма>3000 Order Byном_пок;

Объединение – операция над двумя операндами, поэтому для объединения более чем двух выборок используют скобочные конструкции:

(Select<выборка 1> Union [All] Select< выборка 2>)

Union [All]

(Select< выборка 3> Union [All] Select< выборка 4>) …

39. SQL: изменение содержания таблиц.

Понятие «изменение базы данных» имеет, по крайней мере, две стороны: изменение содержания существующей БД и изменение ее структуры

Добавление данных в таблицу выполняется командой Insert:

Insert Into<таблица> Values(<знач1>, <знач2>, …<значN>);

Либо с указанием атрибутов(не обязательно всех):

Insert Into<таблица> (<атр1>, <атр2>, …<атрk>) Values(<знач1>, <знач2>, …<значk>);

Вместо прямого указания значений можно использовать запрос.

Очевидные замечания.

Таблица уже должна существовать.

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

Типы (домены) выбираемых значений должны соответствовать типам (доменам) атрибутов таблицы.

Добавленные записи не должны нарушать уникальность ключа.

В качестве значения <значi> может быть задано любое допустимое выражение.

Исключение строк из таблицы производится командой Delete.

Delete From<таблица>;

Delete From<таблица> Where<условие>;

Изменение значений полей производится командой Update

Update<таблица> Set<атр1>=<знач1>, <атр2>=<знач2>, …<атрk>=<значk>;

Либо

Update<таблица> Set<атр1>=<знач1>, <атр2>=<знач2>, …<атрk>=<значk> Where<условие>;

Увеличить комиссионные всем продавцам, имеющим более трех покупателей, на 0,1:

UpdateПродавец Setкомиссия=комиссия+0.1 Where3<(SelectCOUNT(Distinctном_пок) FromЗаказ WhereЗаказ.ном_прод=Продавец.ном_прод);

40. SQL: создание, удаление, модификация таблиц. Примеры.

Создание таблицы производится следующей командой (фрагменты в квадратных скобках [] могут отсутствовать):

Create Table <таблица>

(<атр1> <тип1> [<(размер1)>] [<ограничения1>], <атр2> <тип2> [<(размер2)>] [<ограничения2>], . . . <атрN> <типN> [<(размерN)>] [<ограниченияN>]

[, Primary Key (<первичный ключ>)];

[, Foreign Key (<внешний ключ>) References <таблица2> <родительский ключ>]);

Ограничения на атрибут: запрет на пустоту (not null), указание на уникальность значения (unique), на то, что этот атрибут – первичный ключ (primary key) или внешний ключ (references <таблица2>(<родительский ключ>)), на необходимость удовлетворять условиям (check(<предикат>)), на значение по умолчанию (default=<значение>).

(ном_прод Numeric(2) primary key,

имя_прод Char(40) not null,

город Char(20) default=’Москва’,

комиссия Numeric(4,2) check(комиссия<1));

Create Table Продавец

С помощью команды Alter Table можно добавлять и удалять атрибуты, изменять их описание, изменять описание таблицы. Формат команды для добавления атрибута:

Alter Table<таблица> Add<атр> <тип> [<(размер)>] [<ограничения>];

Удаление таблицы может быть выполнено тогда, когда она пустая, то есть у нее предварительно были удалены все данные. Команда удаления:

Drop Table <таблица>;

Для ускорения поиска в таблицах SQL предоставляет возможность пользоваться индексами. Создание индекса производится следующей командой:

Create Index<имя индекса> On<таблица> (<атр1>, <атр2>, …<атрk>);

Если создается уникальный индекс, вместо Create Index используется вариант Create Unique Index. Удаление индекса производится командой

Drop Index<имя индекса>;

41. Методы хранения данных и доступа к ним. Методы физически последовательного и прямого доступа. Области применения.

Для оценки методов доступа и хранения используются понятия:

Эффективность доступа – отношение числа логических обращений к числу физических при выборке элемента данных.

Эффективность хранения – отношение числа информационных байтов к числу физических при хранении.

Последовательный метод. В этом методе предполагается физическое расположение записей в логической последовательности. Для выборки записи необходимо просмотреть все предшествующие ей. Очевидно, что эффективность доступа линейно зависит от длины файла. Как правило, время доступа в этом случае недопустимо велико. С другой стороны, для этого метода характерна очень высокая эффективность хранения. Кроме того, алгоритм доступа к данным крайне прост. Следовательно, метод не может применяться там, где необходим быстрый доступ к данным большого объема. Но его можно использовать в тех случаях, когда по характеру задачи следует выбирать записи последовательно (например, полное копирование данных), а также при очень небольших объемах данных в силу простоты алгоритма доступа.

Прямой метод. Для прямого метода необходимо взаимно однозначное соответствие между ключом и адресом записи. В этом случае некоторая адресная функция (возможно, тривиальная) формирует адрес, по которому выбирается запись. Это наиболее эффективный метод по времени доступа, эффективность доступа всегда равна единице. Эффективность хранения зависит от плотности размещения ключей. Если это справочная (неизменяемая) таблица, ключи могут располагаться достаточно плотно. В общем случае этот метод довольно расточителен по памяти. Прямой метод применяется в случаях, когда время – наиболее ценный ресурс, например, при организации таблиц операционной системы, а также в тех случаях, когда характер задачи предполагает плотное хранение данных с доступом по номеру, например, в задачах вычислительной математики. Но уже для работы с разреженными матрицами он неэффективен.

42. Индексные методы хранения данных и доступа к ним. Индексно-последовательный и индексно-произвольный методы.

В основе индексных методов доступа лежит создание вспомогательной структуры –индекса, содержащего ключи поиска и ссылки на физические адреса данных. Термин «ключ поиска» не обязательно подразумевает его уникальность, это просто атрибут (комбинация атрибутов), который должен удовлетворять критерию поиска. Если ключ поиска уникален, его называют первичным ключом. В зависимости от вида ключа поиска различаются первичные и вторичные индексы. Доступ к данным производится в два этапа. Вначале в индексе (индексном файле) находятся требуемые значения ключей, затем из основного файла по ссылке извлекается требуемая информация. Разумеется, ни эффективность доступа, ни эффективность хранения при использовании этих методов не могут достигать единицы, но производительность системы в целом может стать достаточно высокой. Для ее увеличения обычно требуют, чтобы индекс целиком размещался в оперативной памяти. Индексы могут быть устроены по-разному. Если поиск и выборка производится по комбинации атрибутов (индексному выражению), соответствующий индекс называется составным. Индекс, построенный на иерархии ссылок, называется многоуровневым. Индекс, который содержит ссылки не на все записи, а на некоторый диапазон, называется неплотным. Плотный индекс содержит ссылки на все записи. Элемент индекса часто называют статьей.

Индексно-последовательный метод.В индексно-последовательном методе информационный файл размещается по блокам одинакового размера, начальная часть блока заполняется информационными записями, конечная часть остается свободной. Строится индекс, статья которого содержит указатель на блок, а в качестве ключа индекса выбирается значение ключа первой или последней (это предпочтительнее) записи соответствующего блока. Индексы группируются в индексный файл, который упорядочен по значению ключа. Таким образом, индекс ссылается на группу записей, которые расположены в логическом порядке, то есть в данном методе используется неплотный индекс. Поиск производится следующим образом. В оперативную память загружается индекс, в нем выбирается ссылка на диапазон ключей, в котором предположительно находится искомая запись. Затем в память загружается нужный блок, в нем последовательным методом ищется нужный ключ. Неплотность индекса дает возможность уменьшить количество его записей по сравнению с объемом базы кратно размеру блока. Но индекс все равно может стать слишком большим и не помещаться в память. Тогда есть два пути: либо увеличить блок, либо как-то реорганизовать индекс. Блок увеличить можно лишь в ограниченных пределах: во-первых, он должен помещаться в память, во-вторых – поиск в нем ключа не должен заметно сказываться на производительности. С индексом можно поступить интереснее: его можно рассматривать как информационный файл и, в свою очередь, проиндексировать. Таким образом, получается иерархия индексов, каждый элемент которой способен разместиться в память. Начальную загрузку для этого метода делают из сортированного файла. Добавление записи в информационный файл производится в свободное место выбранного блока. Если свободного места нет, запись либо размещают в дополнительный блок, связанный с выбранным, который называется областью переполнения, либо делят блок пополам, формируя два новых. В первом случае процесс формирования блока проще, но зона последовательного поиска увеличивается на величину блока. Во втором случае процесс деления занимает довольно много времени, но время последующего поиска увеличивается незначительно.

Эффективность доступа зависит от размера индексов и числа уровней их иерархии. Кроме того, на нее влияет размер блоков, наличие в них свободных мест, наличие областей переполнения. Эффективность хранения в основном зависит от объема свободного места в блоках и от величины индексов.

Индексно-произвольный метод.В отличие от предыдущего, этот метод основан на использовании плотного индекса. В этом случае число статей индекса равно количеству информационных записей. Суть метода состоит в следующем. Для информационной структуры (файла) формируется индекс, который содержит значения ключей поиска и ссылки на соответствующие записи. При поиске записи вначале в индексе выбирается статья с искомым ключом, затем по ссылке выбирается непосредственно требуемая запись. Поиск однозначен, если он производится по первичному или другому уникальному индексу. В случае вторичного ключа результат поиска – выборка из записей с равными ключами. Как и в индексно-последовательном методе, нужно стремиться к тому, чтобы весь индекс размещался в памяти. Но в данном случае, в силу плотности индекса, ситуация хуже из-за большего его размера. Более того, иногда он может превышать размер информационного файла. Уменьшение области поиска достигается, например, построением многоуровневого индекса. Ключи обычно бывают упорядоченными для последующего дихотомического поиска, но не исключаются и другие алгоритмы. Естественно, упорядоченность записей в информационном файле не существенна, однако иногда она позволяет заметно сократить время работы. Например, выдача отчета по всему файлу с сортировкой по ключу поиска приведет к последовательному просмотру статей индекса, но к хаотичному выбору записей в случае их сильного перемешивания по этому ключу. Это, в свою очередь, приводит к «дерганью» головки дисковода, что заметно увеличивает время доступа. Решение проблемы – сортировка по ключу поиска. К замедлению поиска приводит и дублирование значений ключей, следовательно, этот метод наиболее эффективен для первичных индексов.

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

43. Метод хранения данных и доступа к ним, основанный на инвертированных списках. Представление инвертированных списков битовыми картами (шкалами).

Инвертированные списки.Два предыдущих метода ориентировались, в основном, на поиск записей с уникальным значением ключа. Однако нередко возникает задача выбора группы записей по определенным параметрам, каждый из которых не уникален. Более того, записей с каким-то фиксированным значением параметра может быть очень много. Это характерно, например, для библиотечного поиска, когда требуется подобрать книгу с заданным годом издания, автором, издательством и т.п. Для подобных задач существуют специальные методы, наиболее популярный из которых – метод инвертированных списков или инвертированный метод. Считается, что поиск может проводиться по значениям любых полей (вторичных ключей) или их комбинации. Для каждого вторичного ключа создается индекс. В нем на каждое значение ключа формируется список указателей на записи файла с этим значением. Это не обязательно физическая ссылка, допускается и первичный ключ. Таким образом, инвертированный индекс группируется по именам полей, которые в свою очередь группируются по значениям. При поиске записи с заданным значением ключа выбирается нужный индекс, в нем каким-то способом (например, индексно-произвольным) выбирается статья с этим значением, затем выбирается весь список ссылок на записи с искомым значением. Дальнейший выбор записей с одинаковым значением вторичного ключа производится по ссылкам, содержащимся в выбранном списке. Легко видеть, что поиск по комбинации значений полей сводится к выбору соответствующих списков и их пересечению (операция И) или объединению (операция ИЛИ). Действительно, в пересечении списков содержатся ссылки на записи, удовлетворяющие обоим критериям, а в объединении – хотя бы одному. Критерии могут включать как условия на один ключ, так и на разные. При этом можно использовать не только равенство, но и другие операции отношения.

Более эффективна работа со списками при использовании метода битовых карт, который тоже предназначен для работы с вторичными ключами. Во многом он эквивалентен предыдущему, только вместо списков используются битовые шкалы, длина которых равна количеству информационных записей. Наличие единицы в позиции N означает, что в N-й записи значение соответствующего ключа совпадает с искомым значением, наличие нуля – нет. Очевидно, что объединение всех битовых шкал для всех значений заданного ключа дает шкалу, состоящую из одних единиц. В этом методе вместо работы со списками выполняются логические операции с битовыми шкалами. Для выбора искомых записей следует пробежать результирующую битовую шкалу и отобрать записи, номера которых равны позициям шкалы, содержащим единицы. Этот метод хорош, когда количество различных значений вторичных ключей, а значит, и шкал, невелико. В этом случае среднее количество единиц в шкале достаточно велико, что повышает эффективность работы. Заметим, что в предыдущем методе в таких условиях удлиняются списки, что, наоборот, снижает эффективность. Особенно удобно использовать битовые карты при задании сложных условий выбора: операции над битовыми шкалами гораздо проще и быстрее, чем со списками. Понятно, что с ростом количества информационных записей и количества различных вторичных ключей эффективность этого метода падает, особенно эффективность хранения. Достоинства метода – независимость от объема файла при выборе данных по произвольным значениям ключа, отбор списка записей по сложным условиям без обращения к файлу. Особенно эффективно применение инвертированных списков при выборке данных по совокупности критериев, если атрибуты имеют сравнительно небольшой диапазон значений. Недостаток – большие затраты времени на создание и обновление инвертированных индексов, причем, время зависит от объема данных. Этот метод обычно используется лишь для поиска. Для начальной загрузки данных и обновления используют другие методы.

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

44. Метод хранения данных и доступа к ним, основанный на перемешанных таблицах (хеширование).

Он представляет собой расширение метода прямого доступа на случай отсутствия взаимно однозначного соответствия между ключом и адресом записи. Существует адресная функция (хеш-функция), которая по ключу формирует адрес, однако, не исключено, что один и тот же адрес выделится разным ключам. Эта ситуация называется коллизией, а соответствующие ключи – синонимами. Алгоритм хеширования включает в себя механизм разрешения коллизий. Эффективность данного метода доступа во многом зависит от эффективности этого механизма. Кроме того, существенно влияет распределение ключей и размер таблицы. Чем больше размер таблицы по отношению к информационным строкам, тем меньше обычно вероятность коллизий, тем выше эффективность доступа. Простейшая реализация метода заключается в том, что исходя из предположения о равномерном распределении значения ключей, функция хеширования отображает их равномерно на множество допустимых адресов. Простейший способ разрешения коллизий следующий. Если при попытке размещения по указанному адресу выясняется, что там уже что-то лежит, последовательно ищется первое свободное место, при прохождении через конец таблицы указатель возвращается на начало. Если свободная запись найдена – хорошо, в противном случае считается, что таблица переполнена. Аналогично ищутся данные при выборке. Если по указанному адресу есть данные, проверяется их ключ. При несовпадении регистрируется коллизия, которая разрешается, как указано ранее. Если данных нет, поиск неудачен. Этот алгоритм прост, но неэффективен по времени при заполнении таблицы более чем наполовину. Кроме того, при неравномерном распределении ключей этот алгоритм приводит к локальным сгущениям записей и увеличению числа коллизий при относительно свободной таблице. Если есть априорные сведения о распределении ключей, можно построить хеш-функцию, отображающую их опять же равномерно. Это заметно повысит эффективность даже для простого алгоритма разрешения коллизий.

Теперь рассмотрим метод хеширования более подробно. Пусть M – число записей в таблице, k K – ключ из множества допустимых значений ключа K, a – адрес в таблице, h(k) – хеш-функция, которая по значению ключа формирует адрес: a=h(k), то есть отображает множество ключей K на интервал адресов [0, M-1]. Будем считать, что M больше количества возможных записей. Так как рассматриваемый метод не предполагает взаимно однозначного соответствия ключей и адресов, допускается существование таких k1 и k2, что при k1k2 выполняется h(k1) = h(k2). Эта ситуация, как уже было сказано, называется коллизией, а k1 и k2 называются синонимами.

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

Методы хеширования:

Метод деления

Метод умножения

Преобразование системы исчисления

Деление многочленов