Информационное обеспечение сетевых АИС. Теоретические основы БД. Информация и данные.
Множества и операции над мно-жествами.
Теоретико-множественные операции
Поскольку реляционная теория базируется на теории множеств, естественно предположить, что теоретико-множественные операторы можно применять и для отношений. Как мы увидим далее, это предположение вполне справедливо.
Итак, рассмотрим четыре оператора:
Объединение
Пересечение
Вычитание
Декартово произведение
Объединение
Оператор объединения применим только к отношениям, совместимым по типу, т.е. к отношениям, имеющим одно и то же множество атрибутов, причем одноименные атрибуты определены на одинаковых доменах.
Операция объединения отношений A и B обозначается следующим образом:
A UNION B
Результат операций теории множеств можно сделать нагляднее посредством диаграмм Эйлера-Венна. Построим диаграмму для операции объединения:
Мы видим, что результатом объединения двух множеств является множество, включающее в себя все элементы исходных множеств.
В случае, когда A и B - отношения, результатом их объединения является отношение, заголовок которого совпадает с заголовками A и B, а тело включает кортежи из обоих отношений (исключая возможные дубликаты).
Например, отношение COMP_BOOKS содержит данные по компьютерным книгам в библиотеке, а отношение MATH_BOOKS - по математическим книгам. Отношение, являющееся результатом оператора (COMP_BOOKS UNION MATH_BOOKS), содержит перечень книг из обоих разделов, причем книги, включенные в оба раздела (например, по численным методам), будут представлены в результирующем отношении в единственном экземпляре.
Пересечение
Для этого оператора отношения-операнды также должны быть совместимы по типу. Обозначается пересечение следующим образом:
A INTERSECT B
Диаграмма для пересечения:
Результатом пересечения двух множеств является множество, элементы которого принадлежат одновременно обоим множествам.
В случае пересечения двух отношений результат - отношение, заголовок которого совпадает с заголовками исходных отношений, а тело включает кортежи, имеющиеся в обоих отношениях.
Если продолжить пример с библиотекой, то оператор (COMP_BOOKS INTERSECT MATH_BOOKS) определяет множество книг, включенных в оба раздела одновременно.
Вычитание
Как и в предыдущем случае, отношения-операнды должны быть совместимы по типу. Обозначение вычитания:
A MINUS B
Продолжая иллюстрацию для пересечения множеств, изобразим их разность графически:
Как видно на диаграмме, результирующее множество состоит из элементов, принадлежащих A и не принадлежащих B. Нетрудно догадаться, что применительно к отношениям эта операция дает отношение, заголовок которого совпадает с заголовками исходных отношений, а тело включает все кортежи первого отношения, не включенные во второе.
Возвращаясь к примеру с библиотекой, заметим, что оператор (COMP_BOOKS MINUS MATH_BOOKS) выбирает все компьютерные книги, которых нет в математическом разделе.
Декартово произведение
Для декартова произведения двух множеств нарисовать наглядную диаграмму довольно-таки затруднительно, во всяком случае, для меня. Поэтому придется ограничиться словесным описанием этой операции в применении к отношениям.
Если даны два отношения A и B, то их декартовым произведением является отношение, заголовок которого образован сцеплением заголовков исходных отношений, а тело - сцеплением кортежей этих отношений.
Обозначается эта операция так:
A TIMES B
В отличие от предыдущих операций, совместимости по типу исходных отношений не требуется. Более того, если отношения содержат атрибуты с одинаковыми именами, атрибут одного из отношений придется переименовать, чтобы избежать неоднозначности имен в результирующем отношении.
Операция кажется гораздо причудливее, чем три предыдущих. Следует добавить, что и особой самостоятельной ценности она не имеет. Применяется она обычно только в сочетании с реляционными операциями
Математическая логика.
Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.»[1] Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков).»[2] Это определение соответствует определению С. К. Клини: математическая логика — это «логика, развиваемая с помощью математических методов».[3] Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы».[4] Все эти определения не противоречат, а дополняют друг друга.
Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. Такие точные языки имеют две стороны: синтаксис и семантику. Синтаксисом называется совокупность правил построения объектов языка (обычно называемых формулами). Семантикой называется совокупность соглашений, описывающих наше понимание формул (или некоторых из них) и позволяющих считать одни формулы верными, а другие — нет.
Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и , то выводима и формула B.
Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление И называется семантически пригодным для языка Я, если любая выводимая в И формула языка Я является верной. Аналогично, исчисление И называется семантически полным в языке Я, если любая верная формула языка Я выводима в И.Математическая логика изучает логические связи и отношения лежащие в основе логического ( дедуктивного ) вывода с использованием языка математики
Алгебра высказываний.
Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Высказывания могут быть истинными, ложными или содержащими истину и ложь в разных соотношениях.
Базовыми элементами, которыми оперирует алгебра логики являются высказывания. Высказывания строятся над множеством {B, , , , 0, 1}, где B — непустое множество, над элементами которого определены три операции:
отрицание (унарная операция),
конъюнкция (бинарная),
дизъюнкция (бинарная),
константы — логический ноль 0 и логическая единица 1.
Моделирование и описание предметной области АИС.
Инфологическая или информационная модель (схема данных) и ее описание предполагает моделирование входных, промежуточных и результатных информационных массивов предметной области и их характеристика. Необходимо детально освятить как на основе входных документов и нормативно справочной информации происходит обработка с использованием массивов оперативной информации и формирования выходных данных.
Концептуальная схема предметной области. Основные модели данных.
Концептуальные модели и схемы баз данных
Широкое распространение реляционных СУБД и их использование в самых разнообразных приложениях показывает, что реляционная модель данных достаточна для моделирования предметных областей. Однако проектирование реляционной базы данных в терминах отношений на основе кратко рассмотренного нами механизма нормализации часто представляет собой очень сложный и неудобный для проектировщика процесс.
При этом проявляется ограниченность реляционной модели данных в следующих аспектах:
Модель не предоставляет достаточных средств для представления смысла данных. Семантика реальной предметной области должна независимым от модели способом представляться в голове проектировщика. В частности, это относится к упоминавшейся нами проблеме представления ограничений целостности.
Для многих приложений трудно моделировать предметную область на основе плоских таблиц. В ряде случаев на самой начальной стадии проектирования проектировщику приходится производить насилие над собой, чтобы описать предметную область в виде одной (возможно, даже ненормализованной) таблицы.
Хотя весь процесс проектирования происходит на основе учета зависимостей, реляционная модель не предоставляет каких-либо средств для представления этих зависимостей. Несмотря на то, что процесс проектирования начинается с выделения некоторых существенных для приложения объектов предметной области ("сущностей") и выявления связей между этими сущностями, реляционная модель данных не предлагает какого-либо аппарата для разделения сущностей и связей.
Потребности проектировщиков баз данных в более удобных и мощных средствах моделирования предметной области вызвали к жизни направление семантических моделей данных. При том, что любая развитая семантическая модель данных, как и реляционная модель, включает структурную, манипуляционную и целостную части, главным назначением семантических моделей является обеспечение возможности выражения семантики данных.
Прежде, чем мы коротко рассмотрим особенности одной из распространенных семантических моделей, остановимся на их возможных применениях.
Наиболее часто на практике семантическое моделирование используется на первой стадии проектирования базы данных. При этом в терминах семантической модели производится концептуальная схема базы данных, которая затем вручную преобразуется к реляционной (или какой-либо другой) схеме. Этот процесс выполняется под управлением методик, в которых достаточно четко оговорены все этапы такого преобразования.
Менее часто реализуется автоматизированная компиляция концептуальной схемы в реляционную. При этом известны два подхода: на основе явного представления концептуальной схемы как исходной информации для компилятора и построения интегрированных систем проектирования с автоматизированным созданием концептуальной схемы на основе интервью с экспертами предметной области. И в том, и в другом случае в результате производится реляционная схема базы данных в третьей нормальной форме (более точно следовало бы сказать, что автору неизвестны системы, обеспечивающие более высокий уровень нормализации).
Наконец, третья возможность, которая еще не вышла (или только выходит) за пределы исследовательских и экспериментальных проектов, - это работа с базой данных в семантической модели, т.е. СУБД, основанные на семантических моделях данных. При этом снова рассматриваются два варианта: обеспечение пользовательского интерфейса на основе семантической модели данных с автоматическим отображением конструкций в реляционную модель данных (это задача примерно такого же уровня сложности, как автоматическая компиляция концептуальной схемы базы данных в реляционную схему) и прямая реализация СУБД, основанная на какой-либо семантической модели данных. Наиболее близко ко второму подходу находятся современные объектно-ориентированные СУБД, модели данных которых по многим параметрам близки к семантическим моделям (хотя в некоторых аспектах они более мощны, а в некоторых - более слабы).
Системы БД.
Концепция БД.
В информационной системе с использованием технологии баз данных решается задача информационного моделирования какой-либо предметной области (ПО) или её фрагмента.
Хранилищем данных о ПО является, как правило, внешняя память, данные лежат в файлах внешней памяти.
До появления концепции БД и соответствующих этой концепции программных средств управление данными во внешней памяти производилось с помощью файловых систем, которые являются подсистемой ОС. Но их возможности для информационного моделирования ПО ограничены.
Файловые системы обеспечивают хранение слабоструктурированной информации, оставляя дальнейшую структуризацию прикладным программам (пакетам ПП). Поэтому для ПО, для которой структура информации не является простой, требуется создание специализированной программной надстройки для работы с такой информацией, которая включала бы в свой состав не только специальные программы, но и специальные данные, описывающие, например, взаимосвязь информации, размещаемой в различных файлах.
Кроме того, файловые системы не имеют в своём составе специальных языковых средств для формирования информационных запросов пользователей, не позволяют восстанавливать согласованные состояния данных, если по какой-либо причине произошло нарушение их целостности, имеют неразвитые средства, обеспечивающие параллельную работу с данными нескольких пользователей.
Стремление увеличить возможности файловых систем в соответствии с указанными и некоторыми другими пользовательскими потребностями, стремление стандартизировать программные средства для моделирования различных ПО и привело к возникновению концепции баз данных.
Основные черты концепции БД:
данные отделяются от ПП, появляется специальная программная надстройка для управления данными, называемая системой управления базами данных (СУБД); СУБД управляет данными и служит посредником между ними и ПП; ПП упрощаются, освобождаются от функций структуризации, хранения и поиска данных;
появляются стандартизированные данные о фактографических данных – метаданные, управляемые СУБД; метаданные описывают информационные параметры и взаимосвязи фактографических данных о ПО;
СУБД совместно с метаданными представляет собой стандартизированное инструментальное средство для моделирования ПО различной природы;
происходит централизация (интеграция) данных, их многоаспектное использование для различных приложений, что сокращает избыточность данных, позволяет обеспечить более высокий уровень достоверности данных и оптимизировать различные процедуры ведения и использования БД.
Словарь – справочник данных. Концептуальное и логическое описание БД.
Иерархические структуры данных.
Введение
Архитектура реляционных баз данных ориентирована на хранение внутри таблиц БД информации о сущностях информационной системы и связях между ними. Каждая из записей таблицы содержит информацию об одном экземпляре. Организация хранения информации о независимых друг от друга экземплярах сущностей (т.е. так называемых «плоских» данных) не вызывает никаких затруднений. Однако, наряду с «плоскими» данными, при построении даже простых информационных систем, приходится хранить в БД и информацию о «вложенных» друг в друга сущностях, т.е иерархические данные. Организация хранения такой информации в реляционных БД проста, но не всегда очевидна для тех, кто впервые сталкивается с подобной задачей. В данной статье я попытаюсь поделиться накопленным опытом.
Примеры, приводимые далее, были созданы и протестированы с помощью Interbase 6.
Иерархии данных
Чтобы обсудить проблему хранения иерархии в реляционной БД, мы вначале рассмотрим вопрос о том, какие же иерархии данных могут встретиться на практике. В реальной жизни иерархии имеют, как правило, некоторые ограничения. Учитывая эти ограничения, можно построить более эффективные процедуры обработки иерархических данных.
Так, в общем случае, дерево может иметь любое количество уровней иерархии. Но в частных случаях число уровней может, и часто оказывается, конечным. Может быть ограничено количество непосредственных потомков одного элемента иерархии.
Рассмотрим некоторые варианты представления иерархических структур в реляционных БД.
Возможные варианты структур БД для хранения иерархий
Наиболее общим случаем является дерево с неограниченным уровнем вложенности и неограниченным количеством потомков. Для хранения такого рода иерархии необходимо добавить в описание сущности дополнительное поле – ссылку на первичный ключ предка. Такой способ организации иерархии является самым распространенным и универсальным. Однако ему присущи следующие недостатки:
Необходимость рекурсивных запросов для получения полного пути от произвольного элемента до корня дерева.
Сложность вычисления уровня вложенности произвольного элемента.
Сложность получения всех (в том числе и не прямых) потомков данного узла.
Дальнейшее рассмотрение мы будем вести на примере построения иерархической структуры – тематического каталога библиотеки. Данный каталог применяется для классификации, сортировки и поиска книг по их содержанию. Будем считать, что каждый элемент каталога описывается собственным неуникальным символьным именем. Для обеспечения уникальности записей для каждого элемента каталога необходимо ввести первичный ключ. Для поддержки иерархичности данных введем дополнительное поле-ссылку на предка данного элемента иерархии
Сетевые структуры данных.
Сетевой подход к организации данных является расширением иерархического. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных потомок может иметь любое число предков.
Сетевая БД состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме БД набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.
Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:
Каждый экземпляр типа P является предком только в одном экземпляре L;
Каждый экземпляр C является потомком не более, чем в одном экземпляре L.
На формирование типов связи не накладываются особые ограничения; возможны, например, следующие ситуации:
Тип записи потомка в одном типе связи L1 может быть типом записи предка в другом типе связи L2 (как в иерархии).
Данный тип записи P может быть типом записи предка в любом числе типов связи.
Данный тип записи P может быть типом записи потомка в любом числе типов связи.
Может существовать любое число типов связи с одним и тем же типом записи предка и одним и тем же типом записи потомка; и если L1 и L2 - два типа связи с одним и тем же типом записи предка P и одним и тем же типом записи потомка C, то правила, по которым образуется родство, в разных связях могут различаться.
Типы записи X и Y могут быть предком и потомком в одной связи и потомком и предком - в другой.
Предок и потомок могут быть одного типа записи.
Физическое размещение данных.
Организация хранения
Основными единицами физического хранения являются блок данных, экстент, файл (либо раздел жесткого диска). Логический уровень представления информации включает пространства (либо табличные пространства). Блок данных (block) или страница (page) является единицей обмена с внешней памятью. Размер страницы фиксирован для базы данных (Oracle) или для ее различных структур (DB2, Informix, Sybase) и устанавливается при создании. Очень важно сразу правильно выбрать размер блока: в работающей базе изменить его практически невозможно (для этого часто проводят ряд испытаний базы данных-прототипа).
Размер блока оказывает большое влияние на производительность базы данных — при больших размерах скорость операций чтения/записи растет (особенно это характерно для полных просмотров таблиц и операций интенсивной загрузки данных), однако возрастают накладные расходы на хранение (база увеличивается) и снижается эффективность индексных просмотров. Меньший размер блока позволяет более экономно расходовать память, но вместе с тем относительно дорог. Длинные блоки (16, 32 или 64 Кбайт) лучше использовать для больших объектов данных: полнотекстовые фрагменты, мультимедиа-объекты, длинные строки и т.п. Короткие блоки (2 или 4 Кбайт) лучше подходят для значений числовых типов, недлинных строк, значений даты и времени. Следует также учитывать размер блока ОС, он должен быть кратен размеру блока базы данных. Малый размер блока лучше подходит для систем оперативной обработки транзакций, потому что, если сервер блокирует данные на уровне блоков, то это позволяет большему числу пользователей работать, не мешая друг другу (рис. 1). В системах поддержки принятия решений, для которых более критичным является не общая пропускная способность (количество транзакций в единицу времени), а среднее время отклика (response time), больший блок предпочтительнее.
Рис. 1. Зависимость размера блока данных от типа приложения
Администратор отводит пространство для базы данных на внешних устройствах большими фрагментами: файлами и разделами диска. В первом случае доступ к диску осуществляется операционной системой, что дает определенные преимущества, например, работа с файлами средствами ОС. Во втором случае с внешним устройством работает сам сервер. При этом достигается более высокая производительность; кроме того, использование дисков необходимо в случае, если кэш ОС не может работать в режиме сквозной (write-through) записи. Диски особенно эффективны для ускорения операций записи данных (подобный механизм поддерживается Oracle, DB2 и Informix; например, в DB2 данная единица размещения называется контейнером).
Пространством внешней памяти, отведенным ему администратором, сервер управляет с помощью экстентов (extent), т.е. непрерывных последовательностей блоков. Информация о наличии экстентов для объекта схемы данных находится в специальных управляющих структурах, реализация которых зависит от СУБД. На управление экстентами (выделение пространства, освобождение, слияние) тратятся определенные ресурсы, поэтому для достижения эффективности нужно правильно определять их параметры. СУБД от Oracle, IBM, Informix позволяют определять параметры этих структур, а в Sybase экстенты имеет постоянный размер, равный 8 страницам. Уменьшение размера экстента будет способствовать более эффективному использованию памяти, однако при этом возрастают накладные расходы на управление большим количеством экстентов, что может замедлить операции вставки большого количества строк в таблицу. Кроме того, сервер может иметь ограничение на максимальное количество экстентов для таблицы. При слишком большом размере экстентов могут возникнуть проблемы с выделением для них необходимого количества памяти. Обычно определяется размер начального экстента, размер второго и правило определения размеров следующих экстентов. На рис. 2 иллюстрируется взаимосвязь блоков, экстентов и файлов баз данных.
Рис. 2. Блоки, экстенты и файлы базы данных
В Informix существует еще одна единица физического хранения, промежуточная между файлом (или разделом диска) и экстентом, — это «чанк» (от английского chunk, что дословно переводится как «емкость»). Чанк позволяет более гибко управлять очень большими массивами внешней памяти. В одном разделе диска или файле администратор может создать несколько чанков. Чанк также служит единицей зеркалирования.
Общим для СУБД Oracle, DB2 и Informix является понятие пространства (для Oracle и DB2 это табличное пространство). Различные логические структуры данных, такие как таблицы и индексы, временные таблицы и словарь данных размещены в табличных пространствах. В DB2 и Informix дополнительно можно устанавливать размер страницы отдельно для каждой из этих структур. Группировка хранимых данных по пространствам производится по ряду признаков: частота изменения данных, характер работы с данными (преимущественно чтение или запись и т.п.), скорость роста объема данных, важность и т.п. Таким образом, например, только читаемые таблицы помещаются в одно пространство, для которого установлены одни параметры хранения, таблицы транзакций размещаются в пространстве с другими параметрами и т.д. (рис. 3).
Рис. 3. Физическое размещение данных по устройствам
Одна логическая единица данных (таблица или индекс) размещается точно в одном пространстве, которое может быть отображено на несколько физических устройств или файлов. При этом физически разнесены (располагаться на разных дисках) могут не только логические единицы данных (таблицы отдельно от индексов), но и данные одной логической структуры (таблица на нескольких дисках). Такой способ хранения называется горизонтальной фрагментацией: таблица делится на фрагменты по строкам. В Oracle вместо термина «фрагментация» используется «секционирование» (partitioning). Фрагментация — один из способов повышения производительности.
Могут применяться различные схемы записи данных во фрагментированные таблицы. Одна из них — круговая (round-robin), когда некоторая часть вставляемых в таблицу строк записывается в первый фрагмент, другая часть — в следующий и так далее по кругу. В данном случае за счет распараллеливания может быть увеличена производительность операций модификации данных и запросов. Существует и другая схема, включающая логическое разделение строк таблицы по ключу («кластеризация»). Данная схема позволяет избежать перерасхода процессорного времени и уменьшить общий объем операций ввода/вывода. Ее суть в том, что при создании таблицы все пространство значений ключа таблицы разбивается на несколько интервалов, а строкам с ключами, принадлежащими разным интервалам, назначаются различные месторасположения. Впоследствии, при обработке запроса, данная информация учитывается оптимизатором. Если производится поиск по ключу, то оптимизатор может удалять из рассмотрения фрагменты таблицы, не удовлетворяющие условию выборки. Например, создание кластеризованной таблицы будет выглядеть следующим образом (этот и все остальные SQL-скрипты приведены для Oracle)
