Реферат: Http://www citforum ru/database/osbd/contents shtml Основы современных баз данных

http://www.citforum.ru/database/osbd/contents.shtml

Основы современных баз данных

С.Д. Кузнецов, информационно-аналитические материалы
Центра Информационных Технологий

Предисловие

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

Заметим, что литературы на русском языке, посвященной тематике СУБД, очень мало. Невозможно порекомендовать одну или несколько книг, содержание которых покрывало бы материал данного курса. К числу лучших относятся книги К. Дейта "Введение в системы баз данных" (Наука, 1980) и "Руководство по реляционной СУБД DB2" (Финансы и статистика, 1988), а также книга Дж. Ульмана "Основы систем баз данных" (Финансы и статистика, 1983). Хотя эти книги несколько устарели (на английском языке вышло уже несколько дополненных изданий), их стоит читать.

Основное назначение данного курса - систематическое введение в идеи и методы, используемые в современных реляционных системах управления базами данных. В курсе не рассматривается какая-либо одна популярная СУБД; излагаемый материал в равной степени относится к любой современной системе. Как показывает опыт, без знания основ баз данных трудно на серьезном уровне работать с конкретными системами, как бы хорошо они не были документированы.

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

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

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

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

В пятой части курса подробно рассматривается язык реляционных баз данных SQL. Исходные понятия SQL обсуждаются на основе версии языка, разработанной в рамках проекта System R. Затем кратко описывается история SQL после System R и, в частности, международная деятельность по его стандартизации. После этого систематически излагается наиболее распространенный стандарт языка - SQL-89. Обсуждаются способы использования SQL при программировании прикладных систем. Пятая часть курса завершается рассмотрением наиболее важных свойств, появившихся в последнем стандарте языка SQL-92.

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

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

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

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



Содержание

Введение

Лекция 1. Базы данных и файловые системы

1.1. Файловые системы

1.1.1. Структуры файлов

1.1.2. Именование файлов

1.1.3. Защита файлов

1.1.4. Режим многопользовательского доступа

1.2. Области применения файлов

1.3. Потребности информационных систем

Лекция 2. Функции СУБД. Типовая организация СУБД. Примеры

2.1. Основные функции СУБД

2.1.1. Непосредственное управление данными во внешней памяти

2.1.2. Управление буферами оперативной памяти

2.1.3. Управление транзакциями

2.1.4. Журнализация

2.1.5. Поддержка языков БД

2.2. Типовая организация современной СУБД

2.3. Пример: System R

Лекция 3. Ранние подходы к организации БД. Системы, основанные на инвертированных списках, иерархические и сетевые СУБД. Примеры. Сильные места и недостатки ранних систем

3.1. Основные особенности систем, основанных на инвертированных списках

3.1.1. Структуры данных

3.1.2. Манипулирование данными

3.1.3. Ограничения целостности

3.2. Иерархические системы

3.2.1. Иерархические структуры данных

3.2.2. Манипулирование данными

3.2.3. Ограничения целостности

3.3. Сетевые системы

3.3.1. Сетевые структуры данных

3.3.2. Манипулирование данными

3.3.3. Ограничения целостности

3.4. Достоинства и недостатки

Теоретические основы

Лекция 4. Общие понятия реляционного подхода к организации БД. Основные концепции и термины

4.1. Базовые понятия реляционных баз данных

4.1.1. Тип данных

4.1.2. Домен

4.1.3. Схема отношения, схема базы данных

4.1.4. Кортеж, отношение

4.2. Фундаментальные свойства отношений

4.2.1. Отсутствие кортежей-дубликатов

4.2.2. Отсутствие упорядоченности кортежей

4.2.3. Отсутствие упорядоченности атрибутов

4.2.4. Атомарность значений атрибутов

4.3. Реляционная модель данных

4.3.1. Общая характеристика

4.3.2. Целостность сущности и ссылок

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

5.1. Реляционная алгебра

5.1.1. Общая интерпретация реляционных операций

5.1.2. Замкнутость реляционной алгебры и операция переименования

5.1.3. Особенности теоретико-множественных операций реляционной алгебры

5.1.4. Специальные реляционные операции

5.2. Реляционное исчисление

5.2.1. Кортежные переменные и правильно построенные формулы

5.2.2. Целевые списки и выражения реляционного исчисления

5.2.3. Реляционное исчисление доменов

Лекция 6. Проектирование реляционных БД

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

6.1.1. Вторая нормальная форма

6.1.2. Третья нормальная форма

6.1.3. Нормальная форма Бойса-Кодда

6.1.4. Четвертая нормальная форма

6.1.5. Пятая нормальная форма

6.2. Семантическое моделирование данных, ER-диаграммы

6.2.1. Семантические модели данных

6.2.2. Основные понятия модели Entity-Relationship (Сущность-Связи)

6.2.3. Нормальные формы ER-схем

6.2.4. Более сложные элементы ER-модели

6.2.5. Получение реляционной схемы из ER-схемы

Две классические экспериментальные системы

Лекция 7. System R: общая организация системы, основы языка SQL

7.1. Используемая терминология

7.2. Основные цели System R и их связь с архитектурой системы

7.3. Организация внешней памяти в базах данных System R

7.4. Интерфейс RSS

7.5. Синхронизация в System R

7.6. Журнализация и восстановление в System R

Лекция 8. Ingres: общая организация системы, основы языка Quel

8.1. История СУБД Ingres

8.2. Ingres как UNIX-ориентированная СУБД. Динамическая структура системы: набор процессов

8.3. Структуры данных, методы доступа, интерфейсы доступа к данным

8.4. Общая характеристика языка QUEL. Язык программирования EQUEL

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

Внутренняя организация реляционных СУБД

Лекция 9. Cтруктуры внешней памяти, методы организации индексов

9.1. Хранение отношений

9.2. Индексы

9.2.1. B-деревья

9.2.2. Хэширование

9.3. Журнальная информация

9.4. Служебная информация

Лекция 10. Управление транзакциями, сериализация транзакций

10.1. Транзакции и целостность баз данных

10.2. Изолированность пользователей

10.3. Сериализация транзакций

Лекция 11. Методы сериализации транзакций

11.1. Синхронизационные захваты

11.1.1. Гранулированные синхронизационные захваты

11.1.2. Предикатные синхронизационные захваты

11.1.3. Тупики, распознавание и разрушение

11.2. Метод временных меток

Лекция 12. Журнализация изменений БД

12.1. Журнализация и буферизация

12.2. Индивидуальный откат транзакции

12.3. Восстановление после мягкого сбоя

12.4. Физическая согласованность базы данных

12.5. Восстановление после жесткого сбоя

Язык реляционных баз данных SQL

Лекция 13. Язык SQL. Функции и основные возможности

13.1. SEQUEL/SQL СУБД System R

13.1.1. Запросы и операторы манипулирования данными

13.1.2. Операторы определения и манипулирования схемой БД

13.1.3. Определения ограничений целостности и триггеров

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

13.1.5. Определение управляющих структур

13.1.6. Авторизация доступа к отношениям и их полям

13.1.7. Точки сохранения и откаты транзакции

13.1.8. Встроенный SQL

13.1.9. Динамический SQL

13.2. Язык SQL в коммерческих реализациях

13.3. Стандартизация SQL

Лекция 14. Стандартный язык баз данных SQL

14.1. Типы данных

14.2. Средства определения схемы

14.2.1. Оператор определения схемы

14.2.2. Определение таблицы

14.2.3. Определение столбца

14.2.4. Определение ограничений целостности таблицы

14.2.5. Определение представлений

14.2.6. Определение привилегий

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

15.1. Структура запросов

15.1.1. Спецификация курсора

15.1.2. Оператор выборки

15.1.3. Подзапрос

15.2. Табличное выражение

15.2.1. Раздел FROM

15.2.2. Раздел WHERE

15.2.3. Раздел GROUP BY

15.2.4. Раздел HAVING

15.3. Агрегатные функции и результаты запросов

15.3.1. Семантика агрегатных функций

15.3.2. Результаты запросов

Лекция 16. Использование SQL при прикладном программировании

16.1. Язык модулей или встроенный SQL?

16.2. Язык модулей

16.2.1. Определение процедуры

16.3. Встроенный SQL

16.4. Набор операторов манипулирования данными

16.4.1. Операторы, связанные с курсором

16.4.2. Одиночные операторы манипулирования данными

16.5. Динамический SQL в Oracle V.6

16.5.1. Оператор подготовки

16.5.2. Оператор получения описания подготовленного оператора

16.5.3. Оператор выполнения подготовленного оператора

16.5.4. Работа с динамическими операторами SQL через курсоры

Лекция 17. Некоторые черты SQL/92 и SQL-3

17.1. Оператор выделения памяти под дескриптор

17.2. Оператор освобождения памяти из-под дескриптора

17.3. Оператор получения информации из области дескриптора SQL

17.4. Оператор установки дескриптора

17.5. Оператор подготовки

17.6. Оператор отказа от подготовленного оператора

17.7. Оператор запроса описания подготовленного оператора

17.8. Оператор выполнения подготовленного оператора

17.9. Оператор подготовки с немедленным выполнением

17.10. Оператор объявления курсора над динамически подготовленным оператором выборки

17.11. Оператор определения курсора над динамически подготовленным оператором выборки

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

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

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

17.15. Оператор позиционного удаления по курсору, связанному с динамически подготовленным оператором выборки

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

17.17. Подготавливаемый оператор позиционного удаления

17.18. Подготавливаемый оператор позиционной модификации

17.19. Сводка новых возможностей SQL-3

17.19.1. Типы данных

17.19.2. Некоторые другие свойства SQL-3

Компиляторы языка SQL

Лекция 18. Компиляторы SQL. Проблемы оптимизации

18.1. Общая схема обработки запроса

18.2. Синтаксическая оптимизация запросов

18.2.1. Простые логические преобразования запросов

18.2.2 Преобразования запросов с изменением порядка реляционных операций

18.2.3 Приведение запросов со вложенными подзапросами к запросам с соединениями

18.3. Семантическая оптимизация запросов

18.3.1. Преобразования запросов на основе семантической информации

18.3.2. Использование семантической информации при оптимизации запросов

18.4. Выбор и оценка альтернативных планов выполнения запросов

18.4.1. Генерация планов

18.4.2. Оценка стоимости плана запроса

18.4.3. Более точные оценки

СУБД в архитектуре "клиент-сервер"

Лекция 19. Архитектура "клиент-сервер"

19.1. Открытые системы

19.2. Клиенты и серверы локальных сетей

19.3. Системная архитектура "клиент-сервер"

19.4. Серверы баз данных

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

19.4.2. Преимущества протоколов удаленного вызова процедур

19.4.3. Типичное разделение функций между клиентами и серверами

19.4.4. Требования к аппаратным возможностям и базовому программному обеспечению клиентов и серверов

Распределенные базы данных

Лекция 20. Распределенные БД

20.1. Разновидности распределенных систем

20.2. Распределенная система управления базами данных System R*

20.2.1. Именование объектов и организация распределенного каталога

20.2.2. Распределенная компиляция запросов

20.2.3. Управление транзакциями и синхронизация

20.3. Интегрированные или федеративные системы и мультибазы данных

Современные направления исследований и разработок

Лекция 21. Системы управления базами данных следующего поколения

21.1. Ориентация на расширенную реляционную модель

21.2. Абстрактные типы данных

21.3. Генерация систем баз данных, ориентированных на приложения

21.4. Оптимизация запросов, управляемая правилами

21.5. Поддержка исторической информации и темпоральных запросов

Лекция 22. Объектно-ориентированные СУБД

22.1. Связь объектно-ориентированных СУБД с общими понятиями объектно-ориентированного подхода

22.2. Объектно-ориентированные модели данных

22.3. Языки программирования объектно-ориентированных баз данных

22.3.1. Потеря соответствия между языками программирования и языками запросов в реляционных СУБД

22.3.2. Языки программирования ООБД как объектно-ориентированные языки с поддержкой стабильных (persistent) объектов

22.3.3. Примеры языков программирования ООБД

22.4. Языки запросов объектно-ориентированных баз данных

22.4.1. Явная навигация как следствие преодоления потери соответствия

22.4.2. Ненавигационные языки запросов

22.4.3. Проблемы оптимизации запросов

22.5. Примеры объектно-ориентированных СУБД

22.5.1. Проект ORION

22.5.2. Проект O2

Лекция 23. Системы баз данных, основанные на правилах

23.1. Экстенсиональная и интенсиональная части базы данных

23.2. Активные базы данных

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

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

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

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

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

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

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

Первая развитая файловая система была разработана фирмой IBM для ее серии 360. К настоящему времени она очень устарела, и мы не будем рассматривать ее подробно. Заметим лишь, что в этой системе поддерживались как чисто последовательные, так и индексно-последовательные файлы, а реализация во многом опиралась на возможности только появившихся к этому времени контроллеров управления дисковыми устройствами. Если учесть к тому же, что понятие файла в OS/360 было выбрано как основное абстрактное понятие, которому соответствовал любой внешний объект, включая внешние устройства, то работать с файлами на уровне пользователя было очень неудобно. Требовался целый ряд громоздких и перегруженных деталями конструкций. Все это хорошо знакомо программистам среднего и старшего поколения, которые прошли через использование отечественных аналогов компьютеров IBM.
^ 1.1.1. Структуры файлов
Дальше мы будем говорить о более современных организациях файловых систем. Начнем со структур файлов. Прежде всего, практически во всех современных компьютерах основными устройствами внешней памяти являются магнитные диски с подвижными головками, и именно они служат для хранения файлов. Такие магнитные диски представляют собой пакеты магнитных пластин (поверхностей), между которыми на одном рычаге двигается пакет магнитных головок. Шаг движения пакета головок является дискретным, и каждому положению пакета головок логически соответствует цилиндр магнитного диска. На каждой поверхности цилиндр "высекает" дорожку, так что каждая поверхность содержит число дорожек, равное числу цилиндров. При разметке магнитного диска (специальном действии, предшествующем использованию диска) каждая дорожка размечается на одно и то же количество блоков таким образом, что в каждый блок можно записать по максимуму одно и то же число байтов. Таким образом, для произведения обмена с магнитным диском на уровне аппаратуры нужно указать номер цилиндра, номер поверхности, номер блока на соответствующей дорожке и число байтов, которое нужно записать или прочитать от начала этого блока.

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

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

В некоторых файловых системах базовый уровень доступен пользователю, но более часто прикрывается некоторым более высоким уровнем, стандартным для пользователей. Распространены два основных подхода. При первом подходе, свойственном, например, файловым системам операционных систем фирмы DEC RSX и VMS, пользователи представляют файл как последовательность записей. Каждая запись - это последовательность байтов постоянного или переменного размера. Записи можно читать или записывать последовательно или позиционировать файл на запись с указанным номером. Некоторые файловые системы позволяют структурировать записи на поля и объявлять некоторые поля ключами записи. В таких файловых системах можно потребовать выборку записи из файла по ее заданному ключу. Естественно, что в этом случае файловая система поддерживает в том же (или другом, служебном) базовом файле дополнительные, невидимые пользователю, служебные структуры данных. Распространенные способы организации ключевых файлов основываются на технике хэширования и B-деревьев (мы будем говорить об этих приемах более подробно в следующих лекциях). Существуют и многоключевые способы организации файлов.

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

Конечно, для обоих подходов можно обеспечить набор преобразующих функций, приводящих представление файла к некоторому другому виду. Примером тому служит поддержание стандартной файловой среды системы программирования на языке Си в среде операционных систем фирмы DEC.
^ 1.1.2. Именование файлов
Остановимся коротко на способах именования файлов. Все современные файловые системы поддерживают многоуровневое именование файлов за счет поддержания во внешней памяти дополнительных файлов со специальной структурой - каталогов. Каждый каталог содержит имена каталогов и/или файлов, содержащихся в данном каталоге. Таким образом, полное имя файла состоит из списка имен каталогов плюс имя файла в каталоге, непосредственно содержащем данный файл. Разница между способами именования файлов в разных файловых системах состоит в том, с чего начинается эта цепочка имен.

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

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

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

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

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

Заметим, что в ранних версиях файловой системы ОС UNIX вообще не были реализованы какие бы то ни было средства синхронизации параллельного доступа к файлам. Операция открытия файла выполнялась всегда для любого существующего файла, если данный пользователь имел соответствующие права доступа. При совместной работе синхронизацию следовало производить вне файловой системы (и особых средств для этого ОС UNIX не предоставляла). В современных реализациях файловых систем ОС UNIX по желанию пользователя поддерживается синхронизация при открытии файлов. Кроме того, существует возможность синхронизации нескольких процессов, параллельно модифицирующих один и тот же файл. Для этого введен специальный механизм синхронизационных захватов диапазонов адресов открытого файла.
^ 1.2. Области применения файлов
После этого краткого экскурса в историю файловых систем рассмотрим возможные области их применения. Прежде всего, конечно, файлы применяются для хранения текстовых данных: документов, текстов программ и т.д. Такие файлы обычно образуются и модифицируются с помощью различных текстовых редакторов. Структура текстовых файлов обычно очень проста: это либо последовательность записей, содержащих строки текста, либо последовательность байтов, среди которых встречаются специальные символы (например, символы конца строки).

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

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