Введение в системы управления базами данных

Введение в системы управления базами данных

(преподаватель: к.т.н. К.А. Хайдаров)

1. Предисловие
2. Исторический обзор
3. Основные понятия и определения
4. Индексирование в базах данных
5. Методы доступа к файлам
6. Хэширование
7. Архитектура базы данных. Физическая и логическая независимость
8. Процесс прохождения пользовательского запроса
9. Пользователи банков данных
10. Основные функции группы администратора БД
11. Классификация моделей данных
12. Физическое проектирование базы данных
13. Теоретико-графовые модели данных
14. Основные определения реляционной модели данных
15. Теоретико-множественные операции реляционной алгебры
16. Специальные операции реляционной алгебры
17. 13 правил Кодда для СУБД

Корпоративные СУБД 1. Российская СУБД ЛИНТЕР 2. Российская объектная СУБД НИКА 3. СУБД InterBase фирмы Borland 4. Свободная СУБД Firebird 5. Ольга Левченко СУБД DB2 корпорации IBM 6. Оксана Фещенко СУБД Progress 7. Рустем Косембаев СУБД Oracle 8. Ольга Левченко Microsoft SQL Server 9. Никита Анохин СУБД PostgreSQL Однопользовательские СУБД (оболочки) 10. СУБД визуального программирования MS Office Access 11. СУБД визуального программирования 1C Движки (engines) для СУБД 12. Распределенная файловая система Google File System (GFS) 13. Высокопроизводительная СУБД Berkeley DB 14. СУБД-движок SQLite 15. Движок для монопольных СУБД: MS Jet DBE

1. Язык SQL. Формирование запросов к базе данных
2. Проектирование реляционных БД на основе принципов нормализации
3. Инфологическое моделирование
4. Принципы поддержки целостности в реляционной модели данных
5. Физические модели баз данных
6. Распределенная обработка данных
7. Модели транзакций
8. Встроенный SQL
9. Защита информации в базах данных
10. Обобщенная архитектура СУБД
11. Перспективы развития БД и СУБД

Глоссарий

Тестовые вопросы по дисциплине

Дополнительная литература

ОСНОВЫ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННЫХ БАЗ ДАННЫХ

С. Д. Кузнецов Технологии баз данных

Лекции Программирование в среде серверных SQL-СУБД

Лекции Банки данных Интернет

к оглавлению программирование в среде SQL-серверов

 

к алгоритмизации алгоритмы, струкутуры данных и программирование СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Предисловие. Теория баз данных

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

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

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

Учебное пособие полностью соответствует требованиям стандарта по дисциплине «Базы данных» для всех вычислительных специальностей, а также для бакалавров по направлению 5528 «Информатика и вычислительная техника» и 050703 "Информационные системы".

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

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

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

Третья тема посвящена первым теоретико-графовым моделям, которые использовались в ранних системах управления базами данных.

В теме четвертой начинается обсуждение современной реляционной модели, которая является основой практически для всех коммерческих систем управления базами данных (СУБД) и наиболее распространена в настоящий момент. В этой же теме дается описание первого языка манипулирования данными, предложенного для данной модели ее создателем американским математиком Е.Ф. Коддом — реляционной алгебры.

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

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

Седьмая тема посвящена семантическим или инфологическим моделям, используемым в современных программных системах поддержки проектирования, называемых CASE-системами (Computer Aided Software Engineering).

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

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

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

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

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

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

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

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

к алгоритмизации алгоритмы, струкутуры данных и программирование СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

 

к алгоритмизации алгоритмы, струкутуры данных и программирование СУБД ЯиМП 3GL 4GL 5GL технологии прогр.

Что такое СУБД?

Современные авторы часто употребляют термины «банк данных» и «база данных» как синонимы, однако в общеотраслевых руководящих материалах по созданию банков данных Государственного комитета по науке и технике (ГКНТ), изданных в 1982 г., эти понятия различаются. Там приводятся следующие определения банка данных, базы данных и СУБД:

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

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

Система управления базами данных, СУБД - совокупность языковых и программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями.

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

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

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

ПО признаку масштаба можно классифицировать современные СУБД на четыре основных уровня или типа:

Нижний, "нулевой" уровень

СУБД - библиотечный встраиваемый модуль, "движок" - эта СУБД представляет собой исполняемую библиотеку, подключаемую к прикладной программе, как например SQLite, являющаяся частью почти любого современного браузера или Borland Database Engine, выполняющая те же функции в продуктах фирмы Borland: Delphi, C++Builder и др., Berkeley DB, используемая в ОС UNIX и часть других СУБД, таких как MySQL.

Первый уровень

Монопольная, "десктоп" СУБД - эта СУБД представляет собой обычную прикладную программу, которая используется для однопользовательского использования (монопольного режима), например, MS Access.

Второй уровень

Корпоративная СУБД - эта СУБД представляет собой программный комплекс, когда ее предназначением является серверная многопользовательская обработка данных общей для многих пользователей базы данных, например, такие известные продукты, как IBM DB2, Oracle, MySQL, MS SQL-Server, СУБД Progress.

Третий уровень

Гипер-СУБД поисковой системы Интернет - эта СУБД представляет собой иерархическую, как минимум, двухуровневую систему управления банком данных, в которой нижний уровень представлен СУБД аналогичными корпоративным, а верхний - "мастер-СУБД", которая осуществляет управление нижним уровнем множества СУБД, кластеризуя большие объемы данных через СУБД нижнего уровня путем перераспределения потоков и объемов информации между СУБД нижнего уровня, но оперируя не первичными данными, а лишь индексной информацией. Примером такой СУБД является распределенная СУБД BigTable корпорации Google.

Рассмотрим основные понятия, употребляемые в технологии баз данных.

Таблица базы данных - - совокупность строк и столбцов. Почти полная аналогия с таблицами на бумаге. Важные уточнения: Каждый столбец должен иметь имя, уникальное в пределах этой таблицы. А строки, в теории баз данных, могут следовать в любом порядке, и не имеют номеров. Хотя Delphi, FoxPro и другие добавляют к каждой строке номер, но при выборке данных в SQL, вы его, в общем случае, не получите. Поэтому к каждой строке принято добавлять какой-нибудь идентификатор, для того, чтобы потом можно было легко найти ее.

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

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

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

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

• Уникальностью. В таблице нет двух разных строк с одиноковыми значениями в нашем потенциальном ключе.
• Неизбыточностью. Нельзя убрать один из столбцом из ключа, так, чтобы он не потерял уникальности.

Рассмотрим, например, такую таблицу:

№ паспорта	Фамилия	Имя	Отчество	Должность
	Иванов	Иван	Иванович	Директор
	Петров	Петр	Иванович	Бухгалтер
	Сидорова	Мария	Ивановна	Секретарь

Табличка у нас простая и небольшая. Но нам хватит.

В данной таблице в качестве потенциального ключа можно рассматривать любой столбец. Но она у нас будет расширяться, так что будем смотреть в будущее.

Понятно, что отчество не может быть потенциальным ключом - есть совпадения. Фамилия - может, если только мы не планируем появления новых строк в таблице. Можно взять комбинацию фамилии и должности, врядли у нас будет два директора-однофамильца. Номер паспорта также подходит на роль потенциального ключа. Я думаю вы поняли мою мысль - к каждой конкретной таблице потенциальнх ключей может быть много. Выбор потенциального ключа - дело программиста. Тот же номер паспорта может не подойти, если мы ожидаем кого-нибудь с поддельным паспортом;) Выбор делается каждый раз заново для каждой ситуации.

Первичные ключи

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

Первичный ключ - это один из потенциальных ключей. Тот, который нам больше понравится. Вам какой больше нравиться? В реальной ситуации, новичок выберет номер паспорта. А что выберет профессионал? Профессионал добавит еще одно поле-счетчик, которое будет содержать уникальное для каждой записи значение. В Delphi такой тип поля называется AutoIncrement, в SQL Server есть целых 2 варианта - TimeStamp и свойтсво Identity поля.

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

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

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

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

Внешний ключ - это ключ, расшифровка которого лежит в другой таблице.

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

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

Итак, имеем две таблицы:

Код работника	Вид движения	Сумма
	Оклад
	Премия
	Налоги	-25
	Оклад
...	...	...

 

Код работника	Фамилия	Имя	Отчество
	Иванов	Иван	Иванович
	Петров	Петр	Иванович
	Сидорова	Мария	Ивановна

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

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

Ранее мы обошли вопрос "А что будет, если не найдется работника с кодом, который мы использовали?" Ничего хорошего не будет. Такой ситуации надо всячески избегать, так как при этом возникнут сбои в нашей программе.

Ссылочная целостность, Refential Integrity - такое состояние, когда у нас все что надо правильно находится. Контроль ссылочной целостности - обеспечение такого состояния.

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

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

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

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

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

 

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

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

Основные из них перечислены ниже.

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

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

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

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

Вторичные индексы

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

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

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

Многоуровневые индексы

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

Методы доступа к файлам

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

Существуют следующие основные типы организации файлов.

• Неупорядоченная организация файла предусматривает произвольное неупорядоченное размещение записей на диске.
• Упорядоченная (последовательная) организация предполагает размещение записей в соответствии со значением указанного поля.
• В хэшированием файле записи хранятся в соответствии со значением некоторой хэш-функции.

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

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

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

Неупорядоченные файлы

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

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

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

Упорядоченные файлы

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

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

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

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

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

 

Хэширование

Статическое хэширование

В хэшированием файле записи не обязательно должны вводиться в файл последовательно. Вместо этого для вычисления адреса страницы, на которой должна находиться запись, используется хэш-функция (hash function), параметрами которой являются значения одного или нескольких полей этой записи. Подобное поле называется полем хэширования (hash field), а если поле является также ключевым полем файла, то оно называется хэш-ключом (hash key). Записи в хэшированием файле распределены произвольным образом по всему доступному для файла пространству. По этой причине хэшированные файлы иногда называют файлами с произвольным или прямым доступом (random file или direct file).

хэш-функция выбирается таким образом, чтобы записи внутри файла были распределены наиболее равномерно. Один из методов создания хэш-функции называется сверткой (folding) и основан на выполнении некоторых арифметических действий над различными частями поля хэширования. При этом символьные строки преобразуются в целые числа с использованием некоторой кодировки (на основе расположения букв в алфавите или кодов символов ASCII). Например, можно преобразовать в целое число первые два символа поля табельного номера сотрудника (атрибут staffNo), а затем сложить полученное значение с остальными цифрами этого номера. Вычисленная сумма используется в качестве адреса дисковой страницы, на которой будет храниться данная запись. Более популярный альтернативный метод основан на хэшировании с применением остатка от деления. В этом методе используется функция MOD, которой передается значение поля. Функция делит полученное значение на некоторое заранее заданное целое число, после чего остаток от деления используется в качестве адреса на диске.

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

Для разрешения конфликтов можно использовать следующие методы:

• открытая адресация;
• несвязанная область переполнения;
• связанная область переполнения;
• многократное хэширование.

Открытая адресация

При возникновении конфликта