Проблемы обработки информации

Лекция 1

Глава 1

ОСНОВНЫЕ ПОНЯТИЯ БАЗ ДАННЫХ

Восприятие реального мира можно соотнести с последовательностью разных, хотя иногда и взаимосвязанных, явлений. С давних времен люди пытались описать эти явления (даже тогда, когда не могли их понять). Такое описание называют данными.

Активная деятельность по отысканию приемлемых способов обобществления непрерывно растущего объема информации привела к созданию в начале 60-х годов специальных программных комплексов, называемых «Системы управления базами данных» (СУБД).

Основная особенность СУБД – это наличие процедур для ввода и хранения не только самих данных, но и описаний их структуры. Файлы, снабженные описанием хранимых в них данных и находящиеся под управлением СУБД, стали называть банки данных, а затем «Базы данных» (БД).

Лекция 2

МЕТОДЫ И СРЕДСТВА ОБРАБОТКИ ДАННЫХ

1. Информационные системы с низкоуровневым доступом: носитель--двоичные данные--приложение--пользователь

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

2. Файловые информационные системы: носитель--двоичные данные--файловая система--приложение--пользователь.

Удовлетворяют признаку 1, частично 2. Данные представляются на носителе в составе файлов – логических единиц, не требующих при их обработке знания команд носителя и явного указания адресов фрагментов данных на носителе. Файл представляет собой последовательность байтов – минимальных единиц представления информации в оперативной памяти компьютера. Для представления больших структурных единиц данных (имя, дата рождения и др.) так же как и в случае низкоуровневого доступа используются наборы байтов, которые в свою очередь группируются в наборы верхнего уровня (паспортные данные включают имя и дату рождения и, в свою очередь входят в данные о сотруднике некоторого учреждения). Соответствующим образом файл делится на фрагменты байтов, и информация о таком разделении «зашита» внутри приложения. Изменение структуры влечет изменение (переписывание) процедур обработки данных в приложении.

3. Информационные системы с базами данных
а) носитель--двоичные данные--файловая система--СУБД--приложение--пользователь
б) носитель--двоичные данные--СУБД--приложение--пользователь

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

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

Таким образом, наиболее полно удовлетворяют представлению о «идеальной» информационной системе обработки данных именно системы с базами данных. Далее мы внимательно рассмотрим определение базы данных и познакомимся с наиболее развитым направлением в теории и практике баз данных – реляционными базами данных.

Лекция 3

ПОНЯТИЕ БАЗЫ ДАННЫХ

Что такое база данных? - База данных (БД) - поименованная совокупность структурированных данных, хранимых в памяти вычислительной системы стандартным способом и отображающих состояние объектов и их взаимосвязей в рассматриваемой предметной области.

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

Задача выявления сущностей предметной области и их атрибутов является весьма сложным этапом концептуального проектирования БАЗЫ ДАННЫХ, и в общем случае не имеет однозначного решения. Обычно необходимо выполнить несколько итераций для получения приемлемого решения на текущем этапе проектирования БАЗЫ ДАННЫХ, при этом, возможно, впоследствии возникнет необходимость изменения состава сущностей и их атрибутов. Более подробно методы построения концептуальной модели БАЗЫ ДАННЫХ будут рассмотрены на последующих лекциях.

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

Сущность «студент» характеризуется следующим набором признаков (атрибутов), важных для предметной области «Контроль успеваемости студентов университета»: Фамилия, имя, отчество, номер зачетной книжки, номер академической группы, текущий рейтинг по каждому из предметов. Номер зачетной книжки (а также имя, фамилия, отчество) позволяют различать студентов как экземпляров сущности «студент». Академическая группа включает набор признаков: наименование группы, наименование факультета. Состав наборов признаков отличают сущности «группа» и «студент».

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

в) структурированные данные – данные, элементы которых упорядочены в соответствии с некоторыми соглашениями. К каждому элементу структурированных данных можно обратиться непосредованно, используя информацию о структуре. Например, если данные хранятся в таблице, то имя пятого ученика мы можем получить из ячейки, находящейся на пересечении столбца «Имя» и пятой строки таблицы, если данные структурированы с помощью таблицы. Кроме определения правила расположения элементов данных в общем хранилище данных структурирование часто подразумевает определение типа данных – то есть способа их представления и объема требуемой для их хранения памяти. В нашем случае имя может являться строкой из 25 символов.

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

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

е) поименованная – совокупность данных должна быть явно определена и фиксирована заданием структуры хранимых данных и имени этой структуры. Каждое приложение работает с определенной базой данных, используя ее имя для доступа к ней.

Лекция 4

Лекция 5

МОДЕЛЬ СУЩНОСТЬ-СВЯЗЬ

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

Одной из наиболее распространенных инвариантных (не привязанных к конкретной СУБД) программных систем ER-моделирования является ERWIN (Computer Associates), особенности применения которой при проектировании БД мы рассмотрим на лабораторной работе.

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

СУЩНОСТЬ

Сущностью или информационным объектом предметной области называется некоторое понятие, общее для ряда объектов реального мира.

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

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

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

Различают зависимые и независимые сущности. Экземпляры независимой сущности могут существовать вне зависимости от существования экземпляров других сущностей. Необходимым условием существования экземпляров зависимой сущности является наличие связанных экземпляров некоторой другой сущности (или сразу нескольких). Зависимая сущность обозначается прямоугольником со скругленными углами.

АТРИБУТ

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

 

Лекция 6

СВЯЗИ МЕЖДУ СУЩНОСТЯМИ

Между сущностями могут быть установлены связи, показывающие, каким образом сущности соотносятся или взаимодействуют между собой. Связь может существовать между двумя или несколькими разными сущностями или между сущностью и ней же самой (рекурсивная связь). Связь именуется глаголом или глагольной фразой. Имя связи выражает некоторое ограничение или правило. Между двумя сущностями может быть задано сколько угодно связей с разными смысловыми нагрузками.

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

Различают следующие типы связей:
а) идентифицирующая связь «один ко многим» (независимая сущность с зависимой от нее). Обозначается сплошной линией с точкой на дочернем конце связи. При этом первичный ключ родительской записи включается в качестве первичного ключа дочерней.

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

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

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

Для указания количества дочерних сущностей связи используется понятие мощности (кардинальности) связи, уточняющее понятие связи «один ко многим».

Ассоциативная - сущность, связанная с несколькими родительскими сущностями. Такая сущность содержит информацию о связях сущностей

Именующая - частный случай ассоциативной сущности, не имеющей собственных атрибутов (только атрибуты родительских сущностей, мигрировавших в качестве внешнего ключа). В качестве примера можно рассмотреть предыдущий пример с сущностью «Изучаемый группой предмет» без атрибута «Семестр».

Категориальная - дочерняя сущность в иерархии наследования.

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

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

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

ИМЯ РОЛИ

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

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

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

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

Рекурсивная связь называется иерархической рекурсией, если каждая сущность связана с несколькими дочерними сущностями, но имеет только одну родительскую

Другим видом рекурсии является сетевая рекурсия (network recursion), когда каждая сущность может быть связана с несколькими как в роли родительской, так и в роли дочерней.

ДОМЕН

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

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

Лекция 7-8

РЕЛЯЦИОННЫЙ ПОДХОД

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

ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

Каждому экземпляру сущности соответствует строка таблицы – кортеж.

Домен представляет собой множество всех возможных значений определенного атрибута отношения.

Схема отношения (заголовок отношения) представляет собой список имен атрибутов. Множество кортежей отношения часто называют содержимым (телом) отношения.

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

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

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

Ключи используют для достижения следующих целей:

• 1) исключения дублирования значений в ключевых атрибутах;
• 2) упорядочения кортежей. Возможно упорядочение по возрастанию или по убыванию значений всех ключевых атрибутов, а также смешанное упорядочивание - по одним — возрастание, по другим — убывание;
• 3) ускорения работы к кортежами отношения;
• 4) организации связывания таблиц.

Пусть в отношении R1 имеется не ключевой атрибут А, значения которого являются значениями ключевого атрибута В другого отношения R2. Тогда говорят, что атрибут А отношения R1 есть внешний ключ.

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

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

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

ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ

Пусть даны n множеств Dl, D2,... Dn, тогда отношение R есть множество упорядоченных кортежей dl, d2,... dn, где dk Dk, dk — атрибут, a Dk — домен отношения R.

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

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

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

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

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

КОНТРОЛЬ ЦЕЛОСТНОСТИ СВЯЗЕЙ

Контроль целостности связей Из перечисленных видов связи наиболее широко используется связь вида 1:М. Связь вида 1:1 можно считать частным случаем связи 1:М, когда одной записи главной таблицы соответствует одна запись вспомогательной таблицы. Связь М:1 по сути, является «зеркальным отображением» связи 1:М. Оставшийся вид связи М:М характеризуется как слабый вид связи или даже как отсутствие связи. Поэтому в дальнейшем рассматривается связь вида 1:М.

При образовании связи вида 1:М одна запись главной таблицы (главная, родительская запись) оказывается связанной с несколькими записями дополнительной (дополнительные, подчиненные записи).

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

• каждой записи основной таблицы соответствует нуль или более записей дополнительной таблицы;
• каждая запись дополнительной таблицы имеет ровно одну родительскую запись основной таблицы.

Контроль целостности осуществляется при выполнении следующих основных операций над данными двух таблиц:

• ввод новых записей,
• модификацию записей,
• удаление записей.

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

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

Лекция 9

Лекция 10-11

УСТРОЙСТВА ХРАНЕНИЯ ДАННЫХ

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

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

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

Разница в характеристиках устройств и способах их применения для хранения данных приводит обычно к различным способам отображения данных в устройства хранения. Большинство СУБД при этом выполняют достаточно сложные операции преобразования с целью максимально эффективного использования и первичных и вторичных устройств.

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

ХЕШИРОВАННЫЕ ФАЙЛЫ

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

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

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

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

Более популярный альтернативный метод основан на перемешивании на основе остатка от деления.

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

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

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

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

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

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

Лекция 12-13

ОТКРЫТАЯ АДРЕСАЦИЯ

При возникновении конфликта система выполняет линейный поиск первого доступного слота в вычисленном сегменте. Если такой слот не найден, поиск продолжается в следующем сегменте. Если слот не найден и в последнем сегменте, поиск слота продолжается с первого сегмента. Если слот не найден до достижения первоначального сегмента, то запись невозможна (БД переполнена).

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

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

Преимущества
1. Высокая плотность записи при фиксированных по размеру сегментах (БД переполнена, когда заполнены все слоты).
2. Высокая эффективность поиска, записи, удаления для разреженных БД, т.к. записи будут расположены рядом со своим сегментом.

Недостатки.
1. Большая потеря производительности при выполнении операций поиска, записи, удаления при сильно заполненных БД.
2. Фиксированный размер БД.

МНОГОКРАТНОЕ ХЕШИРОВАНИЕ

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

ДИНАМИЧЕСКОЕ ХЕШИРОВАНИЕ

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

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

Рассмотрим кратко один тип динамического хеширования, который называется расширяемым хешированием. Вначале записи добавляются только в первый сегмент, и так продолжается до тех пор, пока он не будет полностью заполнен. В этот момент сегмент расщепляется на 2i новых сегментов, где 0 < i < n (обычно i=1, то есть сегмент разбивается на 2 новых сегмента). Адреса сегментов хранятся в каталоге – таблице адресов сегмента. Адрес сегмента, предназначенного для хранения данных со значением хеш-функции равном P, находится в k-ой ячейке каталога, где k – десятичное число, соответствующее двоичному числу, полученному из старших i бит двоичного числа P. После расщепления сегментов ранее хранимые данные перераспределяются по новым сегментам.

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

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

Лекция 14

ИНДЕКСИРОВАННЫЕ ФАЙЛЫ

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

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

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

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

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

Файл данных может иметь один первичный индекс и несколько вторичных индексов.

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

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