Глава 5

ТЕХНОЛОГИИ ДОСТУПА К ДАННЫМ.

ФАЙЛОВЫЕ СИСТЕМЫ И БАЗЫ ДАННЫХ

В истории вычислительной техники можно проследить две основные области ее применения:

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

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

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

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

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

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

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

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

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

Прежде всего, практически во всех современных компьютерах основными устройствами внешней памяти являются магнитные диски с подвижными головками, и именно они служат для хранения файлов [24, 25, 31]. Магнитные диски представляют собой пакеты магнитных пластин (платтеров), между которыми на одном рычаге двигается пакет магнитных головок. Шаг движения пакета головок является дискретным, и каждому положению пакета головок логически соответствует цилиндр магнитного диска. На каждой поверхности цилиндр «высекает» дорожку, так что каждая поверхность содержит число дорожек, равное числу цилиндров. При разметке магнитного диска (специальном действии, предшествующем использованию диска) каждая дорожка размечается на одно и то же количество блоков таким образом, что в каждый блок можно записать по максимуму одно и то же число байтов. Таким образом, для выполнения обмена с магнитным диском на уровне аппаратуры нужно указать номер цилиндра, номер поверхности, номер блока на соответствующей дорожке и число байтов, которое нужно записать или прочитать от начала этого блока.

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

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

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

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

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

Идентификация файлов

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

Известны два базовых варианта:

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

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

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

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

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

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

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

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

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

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

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

Области использования файлов

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

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

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

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

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

В табл. 5.1 приведены типичные команды обращения к файловым системам, характерные для различных ОС.

Файловая система NTFS

Структура файловой системы. Как и любая другая система, NTFS делит все полезное пространство диска на кластеры — блоки данных, используемые единовременно. NTFS поддерживает различные размеры кластеров — от 512 байт до 64 Кбайт, стандартом считается кластер размером 4 Кбайт.

Диск NTFS условно делится на две части (рис. 5.2). Первые 12 % диска отводятся под так называемую MFT-зону — пространство, в котором размещен метафайл MFT (Master File Table). Запись каких-либо данных в эту область невозможна-MFT-зона всегда держится пустой — это делается для того, что бы главный служебный файл (MFT) не фрагментировался при своем расширении. Остальные 88 % диска представляют собой пространство для размещения файлов.

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

Структура MFT. Каждый элемент файловой системы NTFS представляет собой файл, даже служебная информация. Как уже говорилось, главный файл NTFS называется MFT, или Master File Table — общая таблица файлов, которая размещается в MFT-зоне и представляет собой централизованный каталог всех остальных файлов диска. MFT поделен на записи фиксированного размера (обычно 1 Кбайт), и каждая запись соответствует какому-либо файлу. Первые 16 файлов носят служебный характер и недоступны операционной системе — они называются метафайлами, причем самый первый из них — сам MFT. Эти первые 16 элементов MFT — единственная часть диска, имеющая фиксированное положение. Остальная часть MFT-файла может сполагаться, как и любой другой файл, в произвольных местах иска — восстановить его положение можно с помощью его самого, используя за основу первый элемент MFT.

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

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

Базовая единица распределения дискового пространства для файловой системы NTFS — кластер. Размер кластера выражается в байтах и всегда равен целому количеству физических секторов. В качестве адреса файла NTFS использует номер кластера не физическое смещение в секторах или байтах.

Загрузочный сектор тома NTFS располагается в начале тома а его копия — в середине тома. Загрузочный сектор состоит из стандартного блока параметров BIOS, количества секторов в томе, а также начального логического номера кластера основной копии MFT и зеркальной копии MFT.

Каждый атрибут файла NTFS состоит из полей: тип атрибута, длина атрибута, значение атрибута и, возможно, имя атрибута.

Имеется системный набор атрибутов, определяемых структурой тома NTFS. Системные атрибуты имеют фиксированные имена и коды их типа, а также определенный формат. Могут применяться также атрибуты, определяемые пользователями. Их имена, типы и форматы задаются исключительно пользователем. Атрибуты файлов упорядочены по убыванию кода атрибута, причем атрибут одного и того же типа может повторяться несколько раз. Существует два способа хранения атрибутов файла — резидентное хранение в записях таблицы MFT и нерезидентное хранение вне ее. Сортировка может осуществляться только по резидентным атрибутам. Файлы NTFS состоят, по крайней мере, из атрибутов, приведенных в табл. 5.2.

Размещение файлов. Небольшие файлы (small). Если файл имеет небольшой размер, то он может целиком располагаться внутри одной записи MFT размером 2 Кбайт (рис. 5.3,а)  Из-за того, что файл может иметь переменное количество атрибутов, а также из-за переменного размера атрибутов нельзя наверняка утверждать, что файл уместится внутри записи. Однако, обычно файлы размером менее 1500 байт помещаются внутри записи MFT.

Большие  файлы   (Large).  Если файл не вмещается в одну запись MFT, то этот факт отображается в значении атриоу та «данные», который содержит признак того, что файл являете нерезидентным и находится вне таблицы M FT. В этом случае а рибут «данные» содержит номер кластера для первого кластер каждого фрагмента данных (data run), а также количество непрерывных кластеров в каждом фрагменте (рис. 5.3, б).

Очень большие файлы  (huge). Если файл настолько велик, что его атрибут данных не помещается в одной записи, то этот атРибут становится нерезидентным, т. е. он размещается в другой записи таблицы  MFT, ссылка на которую помещена в исходной  записи о файле  (рис.  5.3,  в).  Эта ссылка называется внешним  атрибутом (external attribute). Нерезидентный атрибут содержит указатели на фрагменты данных.

Сверхбольшие файлы (extremely huge). Для сверхбольших файлов внешний атрибут может указывать на несколько нерезидентных атрибутов (рис. 5.3, г). Кроме того, внешний атрибут, как и любой другой атрибут, может храниться в нерезиной форме, поэтому в NTFS не может быть атрибутов слишком большой длины, которые система не может обработать.

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

Небольшие списки файлов (small indexes). Если количество файлов в каталоге невелико, то список файлов может быть резидентным в записи в MFT, являющейся каталогом. В этом случае он называется небольшим каталогом (рис. 5.4, а). Небольшой список файлов содержит значения атрибутов файла. По умолчанию — это имя файла, а также номер записи MTF, содержащей начальную запись файла.

Большие списки файлов (large index). По мере того, как каталог растет, список файлов может потребовать нерезидентной формы хранения. Однако начальная часть списка  всегда остается резидентной в корневой записи каталога в табл це MFT (рис. 5.4, б).

Имена файлов резидентной части списка файлов являются узлами В-дерева. Остальные части списка файлов размещаются вне MFT. Для их поиска используется специальный атрибут «размещение списка» (Index Allocation — IA), представляющий собой набор номеров кластеров, которые указывают на остальные части списка. Одни части списков являются листьями дерева, а другие — промежуточными узлами, т. е. содержат наряду с именами файлов атрибут Index Allocation, указывающий на списки файлов более низких уровней.

Имена файлов

NTFS поддерживает имена файлов длиной до 255 символов. Имена файлов NTFS используют набор символов UNICODE с 16-битовыми символами. NTFS автоматически генерирует поддерживаемое MS-DOS имя для каждого файла. Таким образом, файлы NTFS могут использоваться в сети операционными системами MS-DOS и OS/2.

Поскольку NTFS использует набор символов UNICODE для имен файлов, существует возможность использования некоторых запрещенных в MS-DOS символов. Для генерации короткого имени файла в стиле MS-DOS NTFS удаляет все запрещенные символы, точки (кроме одной), а также любые пробелы из длинного имени файла. Далее имя файла усекается до 6 символов, добаштяется тильда (~) и номер. Расширение имени файла усекается до 3 символов.

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

Другие особенности ФС

Надежность NTFS. NTFS является восстанавливаемой (recoverable) файловой системой, которая может привести себя в корректное состояние при практически любых реальных сбоях. Любая современная файловая система основана на таком понятии, как транзакция — действие, совершаемое целиком и корректно или не совершаемое вообще.

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

При модификации файла специальная компонента файловой системы — сервис регистрации файлов (Log File Service) — фиксирует всю информацию, необходимую для по-торения (redo) или отката (undo) транзакции в специальном файле с именем $LogFile. Если транзакция не завершается нормально, то NTFS пытается закончить транзакцию (повторить) или производит ее откат.

Для обеспечения сохранности пользовательских данных используется программная поддержка массивов RAID (Redundant Array of Inexpensive/Independent Disks — см. рис. 5.16) [24, 25]. В сочетании с поддержкой зеркализации дисков или расщепления с контролем четности (RAID 5) NTFS может выдержать любой одиночный сбой. В Windows NT поддерживаются уровни 0, 1 и 5. В RAID 0 данные расщепляются на блоки по 64 Кбайт, поддерживается от 2 до 32 дисков. RAID 1 осуществляется на уровне разделов, т. е. зеркализируются именно разделы. При отказе зеркализованного раздела администратор должен отменить отношения зеркализации, чтобы использовать оставшийся раздел как отдельный том. Затем можно использовать свободный раздел на другом диске, чтобы вновь установить зеркальные отношения. Зеркализации может быть подвергнут любой раздел, включая загрузочный (Boot Partition). В принципе зеркализация является более дорогим способом, чем Другие, так как коэффициент использования дискового пространства составляет только 50 %, с другой стороны, для небольших сетей это весьма приемлемый вариант, так как для его реализации достаточно только двух дисков.

RAID 5 требует минимум трех дисков (максимум 32 диска), поддерживает файловые системы FAT, NTFS, причем загрузочный раздел не может быть расщеплен. Если отказывает диск, входящий в состав массива RAID 5, то компьютер может продолжать работу и получать доступ к данным. Однако данные отказавшего диска будут в течение всего времени регенерироваться на основании данных других дисков, и производительность си темы может упасть. Можно воссоздать данные отказавшего диска на новом диске. Для этого нужно иметь свободный раздел на каком-либо работоспособном диске равного или большего раз мера, чем отказавший. Затем запускается процедура восстанет ления данных из пункта Regenerate меню Fault Tolerance утилиты Disk Manager.

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

Сжатие. NTFS имеет встроенную поддержку сжатия дисков — то, для чего раньше приходилось использовать Stacker или DoubleSpace. Любой файл или каталог в индивидуальном порядке может храниться на диске в сжатом виде — этот процесс прозрачен для приложений. Сжатие файлов осуществляется с высокой скоростью, однако при этом часто возникает отрицательный эффект — фрагментация сжатых файлов. Сжатие осуществляется блоками по 16 кластеров и использует так называемые виртуальные кластеры — гибкое решение, позволяющее добиться полезных эффектов, например, половина файла может быть сжата, а половина — нет. Это достигается благодаря тому, что хранение информации о компрессированности определенных фрагментов очень похоже на обычную фрагментацию файлов.

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

Hard Link — один и тот же файл может иметь два имени (несколько указателей файла-каталога или разных каталогов ссылаются на одну и ту же MFT-запись). Допустим, один и тот же файл имеет имена l.txt и 2.txt, и если пользователь удалит файл l.txt, останется файл 2.txt, наоборот, если сотрет 2.txt – останется файл 1.txt, т. е. оба имени с момента создания файла равноправны. Файл физически удаляется лишь тогда, когда будет удалено его последнее имя.

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

В табл. 5.3 приведены некоторые характеристики ФС ряда различных ОС.

5.2. Базы данных и СУБД

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

Предположим, что мы решили реализовать эту информационную систему на основе файловой системы и пользоваться при этом одним файлом, расширив базовые возможности файловой системы за счет специальной библиотеки функций. Поскольку минимальной информационной единицей в нашем случае является сотрудник, естественно потребовать, чтобы в этом файле содержалась одна запись для каждого сотрудника. Очевидно, что поля таких записей должны содержать полное имя сотрудника (сотр_имя), номер его удостоверения (сотр_номер) , информацию о его соответствии занимаемой должности (СОТР_статус — для простоты «да» или «нет»), размер зарплаты (СОТР_ЗАРП), номер отдела (СОТР_ОТД_НОМЕР). Поскольку мы хотим ограничиться одним файлом, эта же запись должна содержать имя руководителя отдела (сотр_отд_рук).

Для выполнения функций нашей информационной системы требуется возможность многоключевого доступа к этому файлу по уникальным ключам (не дублируемым в разных записях) СОТР_ИМЯ и СОТР_НОМЕР. Кроме того, должна обеспечиваться возможность выбора всех записей с общим заданным значением СОТР_ОТД_НОМЕР, т. е. доступ по неуникальному ключу. Чтобы получить численность отдела или общий размер зарплаты, информационная система должна будет каждый раз выбирать все записи о сотрудниках отдела и подсчитывать соответствующие общие значения.

Таким образом, для реализации даже такой простой системы на базе файловой системы:

•  во-первых, требуется создание достаточно сложной  надстройки, обеспечивающей многоключевой доступ к файлам;

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

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

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

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

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

Типология БД

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

По форме представляемой информации выделяют:

• фактографические;

• документальные;

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

По типу хранимой (немультимедийной) информации выделяют:

• фактографические;

• документальные;

• лексикографические БД.

Лексикографические базы — классификаторы, кодификаторы, словари основ слов, тезаурусы, рубрикаторы и т. д., обычно используемые в качестве справочных совместно с документальными или фактографическими БД.

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

По типу используемой модели данных выделяют три классических класса БД:

• иерархические;              

• сетевые;

• реляционные.

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

По топологии хранения данных различают локальные и распределенные БД.

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

По функциональному назначению (характеру решаемых с помощью БД задач и, соответственно, характеру использовани данных) выделяют операционные и справочно-информацион ные БД.

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

По сфере возможного применения различают универсальные и специализированные (или проблемно-ориентированные) системы.

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

По назначению содержащейся информации выделяют БД

• деловой информации (социальная, коммерческая и другая информация, кадастры, регистры);

•  информации для специалистов (экономическая, правоохранительная и др информация);

•  массовой информации.

По способу доступа существуют БД:

•  размещенные на хостах (доступные через сети);

• тиражируемые в коммуникативных форматах;

• тиражируемые  с  программными средствами  (включая - CD-ROM);

• локальные.

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

Таким образом, СУБД решают множество проблем, которые затруднительно или вообще невозможно решить при использовании файловых систем. При этом существуют:

•  приложения, для которых вполне достаточно файлов;

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

• приложения, для которых безусловно нужны базы данных.

Модели данных и структура БД

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

Рассмотрим некоторые наиболее известные (или «замечательные») модели данных — иерархическую, сетевую, реляционную.

Иерархическая МД (НМД). Впервые реализована в СУБД  IBM — IMS (Information Management System), разработанной для поддержки банка данных по программе Apollo. При данном подходе предметная область представляется в виде совокупности структур иерархического типа (граф — «дерево»).

Основные понятия ИМД:

• поле — минимальная единица данных;

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

Конкретные данные, входящие в сегмент, называются экземпляром сегмента.

В ИМД существуют также следующие понятия:

•  брат — узел, имеющий того же родителя, что и другой узел;

•  ветвь — узел дерева вместе со всеми его отпрысками, отдаленными потомками и родительскими источниками;

• лист – узел, у которого нет отпрысков;    

• обход дерева — процесс обследования по очереди каждого узла дерева в иерархической модели данных  и пр.

Преимущества IMS и реализованной в ней иерархической модели:

•  простота модели. Принцип построения IMS легок для понимания.   Иерархия  базы данных  напоминает структуру компании или генеалогическое дерево;

•  использование отношений предок/потомок. СУБД IMS позволяла легко представлять отношения  предок—потомок (или часть—целое, причина—следствие), например: «а является частью В» или «А владеет В»;

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

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

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

Сетевая модель данных (модель CODASYL). В предложенной CODASYL модификации иерархической модели одна запись могла участвовать в нескольких отношениях предок/потомок. В сетевой модели такие отношения называются множествами (set). В 70-е гг. независимые производители программного обеспечения реализовали сетевую модель в таких продуктах, как IDMS компании Cullinet, Total компании Cincom, которые приобрели большую популярность. Сетевые БД обладали рядом преимуществ:

•  гибкость — множественные отношения предок—потомок  позволяют сетевой БД хранить данные, структура которых сложнее обычной иерархии;                                                  

• стандартизованность — соответствие стандарту CODASYL;

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

Недостаток — жесткость БД, наборы отношений и структуру записей приходилось

задавать заранее.  Изменение  структуры данных означало перестройку всей БД.

Реляционная модель данных и операции  над отношениями                                                          

В то время как иерархическая модель в своей основе является формализацией и обобщением пользовательских свойств некоторой конкретной системы (IMS), в случае реляционной модели сначала были разработаны некоторые математические основы и лишь через 5—10 лет появились первые коммерчески эффективные системы.

Реляционная модель предложена сотрудником компании IBM Е. Ф. Коддом в 1970 г. В настоящее время эта модель является фактическим стандартом, на который ориентируются практически все современные коммерческие СУБД.

В реляционной модели достигается гораздо более высокий уровень абстракции данных, чем в иерархической или сетевой. Это обеспечивается за счет использования математической теории отношений (само название «реляционная» происходит от английского relation — «отношение»).

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

Декартово произведение: для заданных конечных множеств D_1, D_{2 ,} …, D_N (не обязательно различных) декартовым (прямым) произведением  D₁ × D₂ × …× D_N называется множество наборов: {d₁ ,d₂ …,d_N},где d₁ D₁, d₂  D₂,..., d_N D_N.

Например, если даны два множество А = {а₁, а₂, а₃} и В={b₁, b₂}, их декартово произведение будет иметь вид

C=A х В = {{а₁b₁}, {а₁,b₂}, {а₂,b₁}, {a₂,b₂}, {a₃,b₁,}, {a₃ b₂}}.

Отношение:  отношением  R,  определенным  на  множества D₁, D₂, ..., D_N, называется подмножество декартова произведены D₁ х D₂ x ... х D_N. При этом:

множества D₁, D₂, ..., D_N называются доменами отношения-элементы декартова произведения {d₁, d₂, ..., d_N} называются кортежами;

число N определяет степень отношения (N= 1  — унарное, N= 2 — бинарное, ..., N-арное);

количество кортежей называется мощностью отношения;

На множестве С из предыдущего примера могут быть определены отношения

R₁ ={{а₁,b₂},{а₃,b₂}} или   R₂ = {{a₁,b₁}, {a₂,b₁},{a₁,b₂}}.

Отношения удобно представлять в виде таблиц. Строки таблицы называются экземплярами отношения, столбцы — атрибутами; каждый атрибут имеет область значений, называемую доменом. На рис. 5.6 представлена таблица (отношение степени 5), содержащая некоторые сведения о деталях автомобилей.

Так, таблица Деталь содержит сведения обо всех деталях, хранящихся на складе, а ее строки являются наборами значений атрибутов конкретных деталей. Каждый столбец таблицы — это совокупность значений конкретного атрибута объекта.   Столбец  Материал   может  содержать  конечный   перечень значений – Сталь, Олово, Цинк, Никель и т. д. В столбце Количество содержатся целые неотрицательные числа, Значения в столбце Вес – вещественные числа, равные весу детали в килограммах.

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

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

Так как строки в таблице не упорядочены, невозможно выбрать строку по ее позиции — среди них не существует «первой», «второй», «последней». Любая таблица имеет один или несколько столбцов, значения в которых однозначно идентифицируют каждую ее строку. Такой столбец (или комбинация столбцов) называется первичным ключом (primary key). В таблице Деталь первичный ключ — это столбец Номер_детали. В нашем примере каждая деталь на складе имеет единственный номер, по которому из таблицы Деталь извлекается необходимая информация. Следовательно, в этой таблице первичный ключ — это столбец Номердетали. В этом столбце значения не могут дублироваться — в таблице Деталь не должно быть строк, меющих одно и то же значение в столбце Номер_детали. Если а лица удовлетворяет этому требованию, она называется отношением (relation).

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

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

Таблицы невозможно хранить и обрабатывать, если в базе данных отсутствуют «данные о данных» (метаданные), например, описатели таблиц, столбцов и т. д. Метаданные также представлены в табличной форме и хранятся в словаре данных (DD — data dictionary) или описателе БД (DBD — data base definition) — служебном файле или системной таблице БД.

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

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

Для того чтобы гарантировать корректность и взаимную непротиворечивость данных, на базу данных накладываются некоторые ограничения, которые называют ограничениями целостности (data integrity constraints).

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

Свойства отношений.

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

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

Атомарность значений атрибутов, т. е. среди значений домена не могут содержаться множества значений (отношения).

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

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

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

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

Б. Операции над одним отношением:

• селекция, или построение отношения-результата из отношения-источника путем отбора экземпляров, удовлетворяющих некоторому критерию отбора. Операция селекции соответствует поиску информации в БД по логическим условиям; (find ...   with,    find...where,    locate, см табл. 5.5

• проекция, или построение результирующего отношения п тем отбора части атрибутов всех экземпляров исходного отнощ ния. Данной операции в реальных СУБД соответствует поняти пользовательской подсхемы  и операции  выдачи  необходимы данных  (DISPLAY, VIEW, SET FORM TO, REPORT FORM...).

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

В СУБД соединению соответствует поиск связанных данных     или     логическое     (физическое)     связывание     файлов (FIND. . .COUPLED,  SET   RELATION   TO,  JOIN.

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

Язык SQL

С целью стандартизации формального описания запросов к базе данных они формулируются на стандартном языке запросов (ЯМД — язык манипулирования данными), которым для многих СУБД является SQL [8].

Появление и развитие этого языка как средства описания доступа к базе данных связано с созданием теории реляционных баз данных. Прообраз языка SQL возник в 1970 г. в рамках научно-исследовательского проекта System/R, работа над которым велась в лаборатории Санта-Тереза фирмы IBM, и со временем развился в стандарт интерфейса с реляционными СУБД и разработчики нереляционных СУБД снабжают свои системы SQL-интерфейсом.

Язык SQL имеет официальный стандарт — ANSI/ISO. Боль шинство разработчиков СУБД придерживаются этого стандарта, однако часто расширяют его для реализации новых возможностей обработки данных.

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

if-then-else, for, while и т. д.

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

В запросах на языке SQL используются имена, которые однозначно идентифицируют объекты базы данных. В частности, это – имя таблицы (Деталь), имя столбца (Название_детали), а также имена других объектов в базе, которые относятся к дополнительным типам (например, имена процедур и правил). Наряду с простыми используются также сложные имена — например, квалифицированное имя столбца (qualified column name) определяет имя столбца и имя таблицы, которой он принадлежит (Название_детали. Вес).

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

Рассмотрим несколько примеров.

Запрос: определить   количество  деталей  на   складе  для щсех типов деталей реализуется следующим образом:

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

Запрос: какие детали, изготовленные из стали, хранятся на складе?, сформулированный на языке SQL, выглядит так:

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

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

Результат запроса — таблица из двух столбцов —  Название_детали, Количество, которая содержит название и число деталей,  изготовленных из пластмассы и весящих менее 5 кг. По сути, операция выборки является операцией селекции (найти все строки     таблицы  Деталь, у которых  Материал = `пластмасса` и Вес < 5), а затем – проекции (извлечь Название_детали и Количество из выбранных ранее строк).

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

Допустим, что сформулирован запрос к базе данных Склад:

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

Если же был предварительно создан индекс по столбцу Номер таблицы Деталь, то время поиска в таблице будет сокращено до минимума. Индекс будет содержать значения из столбца Номер и ссылку на строку с этим значением в таблице Деталь. При выполнении запроса СУБД вначале найдет в индексе значение 'Т145-А8' (и сделает это быстро, так как индекс упорядочен, з его строки невелики), а затем по ссылке в индексе определит физическое расположение искомой строки.

Индекс создается оператором SQL CREATE INDEX (СОЗДАТЬ ИНДЕКС). В данном примере оператор

Позволит создать индекс с именем Индекс _детали по столбцу Номер таблицы деталь.

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

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

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

Завершая обсуждение языка SQL, еще раз подчеркнем, что это — язык запросов. На нем нельзя написать сколько-нибудь сложную   прикладную   программу,   которая   работает   с   базой данных. Для  этой  цели  в  современных  СУБД  используются языки   четвертого   поколения   (Forth Generation Language  — 4GL), обладающие как основными возможностями процедурных языков третьего поколения (3GL), таких, как Си, Паскаль, Ада, так и возможностью встроить в текст программы операторы SQL, а также средствами управления интерфейсом пользователя (меню, формами, вводом пользователя и т. д.). Сегодня язык 4GL — это один из фактических стандартов средств Разработки   приложений,   работающих   с   базами   данных.   Бол подробное описание одного из 4GL (Adabas/Natural) читате может найти, например, в [14]. В табл. 5.5 приводятся некото рые команды манипулирования данными других языков и си тем [14].

Модел «сущность—связь»

Модель сущность—связь или Entity-Relationship (ER) представляет собой обобщение РМД путем разделения отношений, описывающих предметную область на две группы — сущностей и связей.

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

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

Основные представления о структуре БД в рамках указанной модели заключаются в следующем:

а) совокупность сущностей и связей образует концептуальную схему базы данных и отражает структуру предметной области. Элементами схемы являются типы (классы) сущностей и связей; типы состоят из экземпляров, описывающихся значениями атрибутов. На рис. 5.8 приведен пример фрагмента диаграммы «сущность — связь», описывающей учебный процесс вуза. Здесь сущностями являются ФАКУЛЬТЕТ, ДИСЦИПЛИНА, СПЕЦИАЛЬНОСТЬ (с возможными атрибутами, например наименование, продолжительность обучения, ЧИСЛО часов и пр.). Связями являются    выпускает,    включает    (возможные    атрибуты    — КВАЛИФИКАЦИЯ, СЕМЕСТР   ОБУЧЕНИЯ и пр.);

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

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

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

Структуры баз данных

Рассмотрим вкратце обобщенные логическую и физическую структуры БД.

Логическая структура БД (рис. 5.9) предполагает следующие уровни рассмотрения БД:

• база данных (database) — включает одну или несколько подбаз (файлов, таблиц, массивов), каждая из которых состоит из агрегатов данных (записей, документов) — record. Запись  идентифицируется   внутренним   номером   (ISN   —   internal sequential number,   BH3   —   внутренний   номер   запис SDN — sequential document number и пр.);

• запись (документ) — совокупность разнотипных и разноструктурных данных, описывающих (относящихся к) объект реального мира, элемент предметной области АИС. Запись состоит из полей (field);

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

• элементарные (имеющие фиксированную или ограниченную длину)  и  не содержащие  входящих в них структур данных;

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

• текстовые — поля переменной (неопределенной) длины и сложной внутренней структуры (обычно это иерархическая последовательность типа раздел – подраздел –предложение – слово);

• бинарные — данные, интерпретируемые как поля, однако обычно физически не входящие в состав записей БД. Необходимо отметить, что поля данного типа (BLOB — Binary Large Object) фактически являются данными, до обработки которых данная СУБД еще «не доросла» и поэтому работа с ними возлагается на пользователя (прикладные программы). В частности, в системах FoxBase и Clipper большие текстовые (так называемые MEMO) поля также не обрабатываются системой и фактически оказываются в статусе BLOB;

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

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

Поля, указанные в заштрихованных прямоугольниках (см. 5.9) относятся к фактографическим АИС, остальные — к документальным.

Физическая структура БД в общем случае имеет вид, приведенный на рис. 5.10, и включает следующие компоненты:

• файл (файлы) исходных (первичных) данных (текстов, бинарных данных) содержит собственно объекты, подлежащие поиску, обработке и пр.;

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

• индекс — файл (файлы), связывающий адрес (номер) объекта с его содержанием (значением атрибута объекта) обычно состоит из инверсного списка и частотного словаря, который облегчает составление запросов на поиск и повышает обозримость БД;

• словарь данных — файл, содержащий составленное с необходимой степенью подробности описание состава БД, документов, записей, агрегатов данных, их имена, типы и структуры, способы интерпретации и обработки.

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

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

В конкретных случаях возможна менее полная комплектность приведенной физической схемы:

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

•  в справочно-библиографических БД текстовые данные находятся во вторичном файле, а первичный отсутствует;

•  в БД с полнотекстовым поиском может отсутствовать вторичный  файл,  а  индексирование  (построение  частотны словарей и инверсных списков) проводится по первичному файлу (страницы или абзацы полных текстов);

• может отсутствовать частотный  словарь или   инверсн список.

Надо отметить также вариативность физической реализации и взаимосвязи лингвистического и информационного обеспечения АИС:

• словарь данных может физически входить в информационные файлы (первичный или вторичный);

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

Обработка транзакций

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

Традиционные транзакции характеризуются четырьмя свойствами: атомарности, согласованности, изолированности, долговечности (прочности) — ACID (Atomicity, Consistency, Isolation, Durability). Иногда традиционные транзакции называют ACID-транзакциями. Упомянутые выше свойства означают следующее:

•  атомарность — операции транзакции образуют неразделимый, атомарный блок с определенным началом и концом. Этот блок либо выполняется от начала до конца, либо не выполняется вообще. Если в процессе выполнения транзакции произошел сбой, происходит откат (backup, возврат) к исходному состоянию;

•  согласованность   гарантирует,   что   по   мере   выполнения транзакций данные переходят из одного согласованного состояния в другое — транзакция не разрушает взаимной согласованности данных;

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

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

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

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

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

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

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

В стандарте ANSI/ISO SQL определены модель транзакций и функции операторов commit и rollback. Стандарт определяет, что транзакция начинается с первого SQL-оператора, инииии руемого пользователем или содержащегося в программе. Все по следующие SQL-операторы составляют тело транзакции. Транзакция завершается одним из четырех возможных способов

(рис 5.П):

• оператор commit означает успешное завершение транзакции; его использование делает постоянными изменения, внесенные в базу данных в рамках текущей транзакции;

• оператор rollback прерывает транзакцию, отменяя изменения, сделанные в базе данных в рамках этой транзакции; новая транзакция начинается непосредственно после использования rollback;

• успешное завершение программы, в которой была инициирована текущая транзакция, означает успешное завершение транзакции (как будто был использован оператор commit);

• ошибочное завершение программы прерывает транзакцию (как будто был использован оператор rollback).

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

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

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

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

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

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

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

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

• если две транзакции, А и В, выполняются параллельно, то СУБД полагает, что результат будет такой же, как если бы:

– транзакция А выполнялась первой, а за ней была выполнена транзакция В;

– транзакция В выполнялась первой, а за ней была выполнена транзакция А.

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

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

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

В современной литературе часто встречается термин OLTP ( Оn - Line Transaction Processing), который обычно переводят как «оперативная обработка транзакций», т. е. выполнение транзакции в режиме реального времени. Система OLTP обязана учитывать   жесткие временные требования, следующие из специфики прикладной области. Например,   процедура   покупки   и оформления авиабилета должна происходить быстро и не задерживать очередь. Система, регистрирующая продажи билетов должна обрабатывать одновременно несколько сотен запросов (транзакций), поступающих от множества продавцов авиабилетов. Требования по скорости обработки запроса могут бьггк очень жесткими, однако вызваны они требованиями реальной жизни. Если говорить о прикладных областях OLTP, то это прежде всего, центры кредитных карточек, системы резервирования авиабилетов и мест в отелях, телекоммуникационные системы и т. д.

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

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

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

СУБД (DBMS — database management system) — комплекс языков и программ, позволяющий создавать БД и управлять ее работой. СУБД обрабатывает поступающие от пользователей и прикладных процессов обращения к БД, а затем выдает необходимые им сведения. СУБД характеризуется используемой моделью и средствами администрирования, разработки прикладных процессов, работы в информационной сети.

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

СУБД обеспечивает:

• описание и контроль данных;

• манипулирование данными (запись, поиск, выдачу, изменение содержания);

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

• защиту от сбоев, поддержку целостности и восстановление;

• работу с транзакциями и файлами;

• безопасность данных.

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

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

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

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

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

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

По используемому языку общения:

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

•  открытые, в которых для общения с БД используется язык программирования,   «расширенный»   операторами   языка манипулирования данными (ЯМД). В этом случае необходимо участие квалифицированного программиста.

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

По выполняемым функциям:

•  операционные,   предполагающие   иные   виды   обработки по получению информации, не хранящейся в явном виде в БД;

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

По сфере применения:

•  универсальные, настраиваемые на любую предметную о ласть путем создания соответствующей БД и прикладны программ;

•  проблемно-ориентированные на определенные процедуры обработки данных, присущих конкретной области применения.                                                                              

В структурном составе СУБД могут быть выделены ядро и среда (рис. 5.12) [14, 32].                                                   

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

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

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

•  физическая подготовка дисковой памяти к размещению БД;

•  подготовка справок о составе БД, структуре файлов, количестве данных и занимаемом объеме;

• загрузка   файла   БД   из   последовательного   набора   данных ОС;

• дозагрузка (расширение существующего файла);

• модификация БД: расширение или перемещение физических наборов данных, реорганизация;

•  модификация файла (таблицы, группы таблиц): добавление новых полей в структуру записи; инвертирование полей или освобождение (превращение инвертированных полей в сканируемые);

• выгрузка образа БД (файла таблицы) для сохранения в архивном наборе данных;

• создание и ведение словаря данных и др.

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

•  диалоговые интерфейсы;

•  генераторы отчетов;

•  система конструирования и поддержки интерактивных тех нологий в информационных системах (ЯП АИС).

5.3. Физическая организация данных в системах управления данными

Расширим вкратце некоторые принципы физической организации данных.

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

С общепринятой точки зрения к вопросам организации данных относятся:

•  выбор типа записи — единицы обмена в операциях ввода-вывода;

•  выбор способа размещения записей в файле и, возможно, метода оптимизации размещения;

•  выбор способа адресации и метода доступа к записям.

Типы записей

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

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

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

На логическом уровне выделяют следующие типы:

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

• записи переменной длины, когда каждый экземпляр записи может иметь длину,

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

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

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

Организация файлов — способ размещения записей

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

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

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

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

•  ускорением или упрощением средств адресации файла (например, средств прямой адресации или хэширования);

•  уменьшением размера используемого индекса и сокращением, таким образом, времени поиска в нем;

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

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

Можно выделить две «чистые» стратегии определения места (адреса) для размещения записей: последовательное (sequential) и произвольное (random) размещение. В этом смысле алгоритм размещения определяет тип организации файла.

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

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

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

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

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

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

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

Способы адресации и методы доступа к записям

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

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

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

Основные проблемы при адресации файла можно сформулировать следующим образом:

•  по первичному ключу определить местоположение записи с данным ключом;

•  организовать набор записей, чтобы поиск потребовал как можно меньше затрат.

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

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

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

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

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

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

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

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

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

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

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

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

•  число преобразуется в адрес блока и, если в нем есть свободное место, то логическая запись размещается там;

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

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

Архитектура файловой организации баз данных

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

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

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

Таким образом, БД физически состоит из нескольких фалов: основного, индексного, файла метаданных, файлов указателей и т. д. (рис. 5.10, 5.14, а). В этом случае ОС активно участвует в навигации, беря на себя функции выборки, новления, вставки, удаления записей из физических файлов.

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

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

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

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

Все страницы данных имеют одинаковую структуру чающую:                                                                                          

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

•  дескрипторы строк, задающие смещение строки на странице и длину строки, что позволяет при переупорядочении строк на страницах не производить физического перемещения строк, так как все манипуляции производятся с дескрипторами;

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

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

Модели распределения данных по физическим носителям

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

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

Примером, иллюстрирующим подход с точки зрения прак ческих компромиссов выбора решения, являются RAID-Mac вы. На рис. 5.15 приведены два варианта: RAID-0, обеспечив щий максимальную производительность при «стандартной» надежности, и RAID-1, обеспечивающий  «двойную» надеж при «стандартной» производительности.                                    

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

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

Главное отличие между сцеплением и расщеплением заключается в размещении смежных данных.

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

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

5.4. Анализ информации и хранилища данных

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

Интеллектуальный анализ данных

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

В общем   случае   процесс ИАД  состоит из трех стадий (рис. 5.16):                                                                

• выявление закономерностей (свободный поиск);

• использование выявленных закономерностей для предсказания неизвестных значений (прогностическое моделирование);

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

Кроме того, могут быть сформулированы следующие задачи:

• выделение в массивах данных групп записей, сходных по некоторым признакам (кластерный анализ);

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

Все методы ИАД подразделяются на две большие группы по принципу работы с исходными обучающими данными:          

•  в первом случае исходные данные могут храниться в явном детализированном виде и  непосредственно использоваться для прогностического моделирования и/или анализа исключений; это так называемые методы рассуждений на основе анализа прецедентов. Главной проблемой этой группы методов является затрудненность использования на больших объемах данных, хотя именно при анализе больших хранилищ данных методы ИАД приносят наибольшую пользу;

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

Две эти группы и примеры входящих в них методов представлены на рис. 5.17.

OLAP – технологии и хранилища данных

В основе концепции OLAP лежит принцип  многомерного представления данных. В 1993 г. Е. Ф. Кодд рассмотрел недостатке реляционной модели, в первую очередь указав на невозможность «объединять, просматривать и анализировать данные с точки зрения множественности измерений, т. е. самым понятным для корпоративных аналитиков способом», и определил общие требования  к системам  OLAP,  расширяющим  функциональность реляционных  СУБД  и  включающим  многомерный анализ как одну из своих характеристик.

Аббревиатурой OLAP иногда обозначается не только многомерный взгляд на данные, но и хранение самих данных в многомерной БД. Однако Кодд отмечал, что «...реляционные БД были, есть и будут наиболее подходящей технологией для хранения корпоративных данных. Необходимость существует не в новой технологии БД, а, скорее, в средствах анализа, дополняющих функции существующих СУБД и достаточно гибких, чтобы предусмотреть и автоматизировать разные виды интеллектуального анализа, присущие OLAP».

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

Использование концепции хранилища данных (ХД) позволяет обеспечить:

•  своевременное обеспечение аналитиков всей информацией, необходимой для выработки решений;

•  создание единой модели данных организации;

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

Для хранилищ  данных  характерны   следующие   основные свойства:

• ориентация на предметную область — хранилище в первую очередь  отражает  специфику  предметной  области, а не приложений;

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

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

• поддержка хронологии — для выполнения большинства аналитических запросов необходим анализ тенденций развития явлений или характера изменения значений переменных во времени, что обычно достигается введением атрибутов типа дата/время;

• многомерное   концептуальное   представление   (multi-dimensional conceptual view) — множественная перспектива, состоящая из нескольких независимых измерений, вдоль которых могут быть проанализированы определенные совокупности данных. Одновременный анализ по нескольким измерениям определяется как многомерный анализ. Каждое измерение включает направления консолидации данных, состоящие из серии последовательных уровней обобщения, где каждый вышестоящий уровень соответствует большей степени агрегации данных по соответствующему измерению. Так, измерение Исполнитель  может определиться направлением консолидации, состоящим из уровней обобщения    предприятие—подразделение—отдел—служащий. Измерение Время может даже включать два направления консолидации — год—квартал—месяц—день и неделя—день, поскольку счет времени по месяцам и по неделям несовместим. В этом случае становится возможны произвольный выбор желаемого уровня детализации и формации  по  каждому из  измерений.  Операция спуска (drilling down) соответствует движению от высших ступен консолидации   к   низшим;   напротив,   операция   подъема (rolling up) означает движение от низших уровней к высшим (рис 5.18).

Кода определил 12 свойств, которыми должны обладать системы этого класса (табл. 5.6).

Модели данных, используемые для построения хранилищ

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

Многомерный OLAP (MOLAP). В специализированных СУБД, иных на многомерном представлении данных, данные организованы не в форме реляционных таблиц, а в виде упорядоченных многомерных массивов:

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

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

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

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

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

•  многомерные СУБД не позволяют работать с большими объемами данных. К тому же за счет денормализации и предварительно выполненной агрегации объем данных в многомерной  базе,  как правило,  соответствует в 2,5—100 раз меньшему объему исходных детализированных данных;

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

Следовательно, использование многомерных СУБД оправдано только при следующих условиях:                              

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

•  набор информационных измерений стабилен  (посколь любое изменение в их структуре почти всегда требует полной перестройки гиперкуба);

•  время ответа системы на нерегламентированные запроск является наиболее критичным параметром;

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

Реляционный OLAP (ROLAP). Непосредственное использование реляционных БД в системах оперативной аналитической обработки имеет следующие достоинства.

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

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

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

Главный недостаток ROLAP по сравнению с многомерными СУБД — меньшая производительность. Для обеспечения производительности, сравнимой с MOLAP, реляционные системы требуют тщательной проработки схемы базы данных и настроик индексов, т. е. больших усилий со стороны администраторов БД. Только при использовании звездообразных схем производитель ность хорошо настроенных реляционных систем  может приближена к производительности систем на основе много ных баз данных.            

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

В сложных задачах с многоуровневыми измерениями имеет мысл обратиться к расширениям схемы звезды — схеме созвездия (fact constellation schema) и схеме снежинки (snowflake schema). В этих случаях отдельные таблицы фактов создаются для возможных сочетаний уровней обобщения различных измерений (рис. 5.20). Это позволяет добиться лучшей производительности, но часто приводит к избыточности данных и к значительным усложнениям в структуре базы данных, в которой оказывается огромное количество таблиц фактов.   

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

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

Возможны гибридные системы (Hybrid OLAP — HOLAP), цель которых — совмещение достоинств и минимизация недостатков, присущих предыдущим классам.

Архитектуры хранилищ данных

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

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

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

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

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

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

• сфера   закономерностей.   Интеллектуальная   обработка  производится  методами  интеллектуального анализа данных (ИАД, Data Mining), главными задачами которых являются поиск функциональных и логических закономерностей в накопленной информации, построение моделей и правил, которые объясняют найденные аномалии  и/или прогнозируют развитие некоторых процессов.

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

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

Процесс загрузки данных обычно подразумевает решение следующих задач:

•  приведение данных к единому формату (унификация типов данных и их представления, исключение управляющих кодов);

•  предобработка данных (исключение дубликатов, устранение ошибочных значений, восстановление пропущенных значений);

•  агрегирование данных (вычисление обобщенных статистических показателей).

Ингеграция OLAP и ИАД

Оперативная аналитическая обработка и интеллектуальный пяти данных – две составные части процесса поддержки принятия решений. Однако большинство систем OLAP заостряет внимание только на обеспечении доступа к многомерным данным, а большинство средств ИАД, работающих в сфере закономерностей, имеют дело с одномерными перспективами данных. Эти анализа должны быть тесно объединены, т. е. системы ОLAP должны фокусироваться не только на доступе на поиске закономерностей (рис. 5.22). Как заметил N. Raden,  «многие компании создали... прекрасные хранилища данных, идеально разложив по полочкам горы неиспользуемой информации, которая сама по себе не обеспечивает ни быстрой, ни достаточно грамотной реакции на рыночные события».

В последнее время появилось обобщенное понятие «OLAP Data Mining» (многомерный интеллектуальный анализ) или «OLAP Mining» для обозначения такого объединения, причем определились несколько вариантов интеграции двух технологий:

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

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

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

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

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

Контрольные вопросы

1. Перечислите функции файловых систем.

2. Какова общая организация ФС NTFS?

3. Какие атрибуты файлов вам известны?

4. Охарактеризуйте разновидности размещения файлов в NTFS.

5  Каким образом осуществляется сжатие данных в NTFS?

6. Дайте определение понятия «База данных».

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

8.  Определите основные функции и назначение СУБД.

9.  Дайте основные характеристики моделей данных.

10. Что такое реляционное исчисление?

11. Перечислите основные компоненты логической и физической структуры БД.

12.  Что такое транзакции?

13.  Назовите отличительные особенности использования баз данных в ИС.

14.  Перечислите основные требования, предъявляемые к базам данных.

15.  Определите назначение и организацию инвертированного списка.

16.  В чем заключается страничная организация данных?

17.  Что такое хранилища данных?

18.  Перечислите основные свойства OLAP-технологий.

19.  В чем различие ROLAP и MOLAP?