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

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

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

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

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

Данная модель базируется на двух главных параметрах: Pr(rel) и Pr(nonrel), т.е. на вероятности релевантности и нерелевантности документа запросу пользователя, которые вычисляются на основе вероятностных весовых коэффициентов терминов и фактического присутствия терминов в документе.

Подразумевается, что релевантность является бинарным свойством, и поэтому Pr(rel) = 1 - Pr(nonrel). Кроме того, в этой модели применяются два стоимостных параметра: al и а2. Они характеризуют соответственно потери, связанные с включением в результат нерелевантного документа и пропуском релевантного документа.

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

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

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

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

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

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

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

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

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

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

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

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

В некоторых случаях представленные два метода не дают удовлетворительного результата. Наличие ошибок 1-го и 2-го рода в реальной системе обуславливает разбиение всего массива документов системы по отношению к запросу на 4 подмассива:

Разбиение массива документов

Выданные Невыданные

Релевантные А С

Нерелевантные В D

А - массив выданных релевантных документов; В - массив выданных нерелевантных документов; С - массив невиданных релевантных документов; D - массив невиданных нерелевантных документов; Введем следующие обозначения: a - количество выданных релевантных документов; b - количество выданных нерелевантных документов; c - количество невиданных релевантных документов; d -количество невыданных нерелевантных документов; Существуют следующие показатели эффективности ДИПС:

1.Коэффициент полноты p , характеризующий долю выданных релевантных документов во всем массиве релевантных документов:

a pa c??.

2.Коэффициент точности n , характеризующий долю выданных релевантных документов во всем массиве выданных документов:

a na b??.

3.Коэффициент шума е, характеризующий долю выданных нерелевантных документов во всем массиве выданных документов:

1 b e na b??????.

4.Коэффициент осадка q, характеризующий долю выданных нерелевантных документов во всем массиве нерелевантных документов:

b qb d??.

5.Коэффициент специфичности k , характеризующий долю невиданных нерелевантных документов во всем массиве нерелевантных документов:

d kb d??.

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

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

Рис. 10. Пример зависимости между коэффициентами полноты и точности

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

1. быстродействие ДИПС (интервал времени между моментом формулировки запроса и получением ответа на него);

2. пропускная способность (оценивается количеством вводимых документов и количеством ответов в единицу времени при заданных значениях коэффициентов полноты и точности);

3. производительность (оценивается количеством пользователей системы и частотой обращения с их стороны);

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

Лекция 13. Фактографические информационные системы

Предметная область

Понятие "предметная область" является базисным понятием в теории БД и поэтому не имеет строгого определения. Чтобы выяснить его смысл, обратимся к понятиям объект и предмет.

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

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

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

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

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

В каждый момент времени предметная область находится в одном из состояний, которое характеризуется совокупностью объектов и их взаимосвязей. Если объекты образуют объектное ядро, то совокупность взаимосвязей отражает структуру фрагмента действительности. С течением времени одни объекты исчезают, другие появляются, меняются свойства и взаимосвязи. Тем не менее возникающие новые состояния считаются состояниями одной и той же предметной области. Таким образом, предметную область целесообразно рассматривать как систему, переживающую свою историю, которая состоит из определенной последовательности состояний.После задания пространства состояний, можно рассматривать в нем определенные траектории или последовательности состояний so,s,,...,st, в которых находится предметная область в моменты времени 0,1 ,...,t. Члены такой последовательности не могут быть совершенно произвольными, поскольку состояние st обычно каким-либо образом связано с предшествующими состояниями s(1, s,,...,st,. Поэтому предметную область можно определить как класс всех действительно возможных последовательностей состояний. Такие последовательности называются траекториями предметной области. Совокупность всех общих свойств траекторий называется семантикой предметной области.

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

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

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

Тип - это понятие, объединяющее все объекты данного типа. В отличие от объекта, существующего в данный момент в конкретном месте, тип не имеет пространственно-временной локализации. Он охватывает все существовавшие, существующие и мыслимые объекты, относимые к данному типу. Типы обеспечивают непротиворечивое объединение локальных "точек зрения" различных групп пользователей. Каждый тип имеет уникальное имя. Например, при описании учебного процесса могут быть введены следующие типы людей: ПРЕПОДАВАТЕЛЬ, СТУДЕНТ, АСПИРАНТ и т. д.

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

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

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

Весь процесс проектирования БД можно разбить на ряд взаимосвязанных этапов, каждый из которых обладает своими особенностями и методами проведения. На рис. 10 представлены типовые этапы.

Рис. 11. Этапы проектирования БД

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

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

Анализ информационных потребностей потенциальных пользователей имеет два аспекта: определение собственно сведений об объектах предметной области; анализ возможных запросов к БД и требований по оперативности их выполнения.

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

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

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

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

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

Инфологическая модель «сущность--связь» (entity-relationship model; ER-model) П.Чена представляет собой описательную (неформальную) модель предметной области, семантически определяющую в ней сущности и связи.

Лекция 14. Инфологическая модель “Сущность - связь”

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

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

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

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

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

На рис.12 приведен пример изображения сущностей и связи между ними.

Рис. 12. Пример связи между сущностями

Данная диаграмма может быть интерпретирована следующим образом: Каждый СТУДЕНТ учится только в одной ГРУППЕ; Любая ГРУППА состоит из одного или более СТУДЕНТОВ. На следующем рисунке (рис.13) изображена сущность ЧЕЛОВЕК с рекурсивной связью, связывающей ее с ней же самой.

Рис.13. Пример рекурсивной связи

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

Каждый ЧЕЛОВЕК является сыном одного и только одного ЧЕЛОВЕКА;

Каждый ЧЕЛОВЕК может являться отцом для одного или более ЛЮДЕЙ ("ЧЕЛОВЕК").

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

Рис. 14. Изображение сущности с ее атрибутами

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

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

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

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

В третьей нормальной форме устраняются атрибуты, зависящие от атрибутов, не входящих в уникальный идентификатор. Эти атрибуты являются основой отдельной сущности.Мы остановились только на самых важных понятиях ER-модели данных. К числу более сложных элементов модели относятся следующие:

Подтипы и супертипы сущностей. ER-модель позволяет задавать отношение IS-A между типами. При этом если Т1 IS-A Т2 (где Т1 и T2 - типы сущностей), то Т1 называется подтипом Т2 а Т2- супертипом Т1. Т.о., существует возможность наследования типа сущности, исходя из одного или нескольких супертипов.

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

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

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

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

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

Лекция 15. Концептуальные модели данных

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

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

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

Типы структур данных

Среди широкого множества определений, обозначающих типы структур данных, наиболее распространена терминология CODASYL (Conference of DAta SYstems Language) -- международной ассоциации по языкам систем обработки данных, созданной в 1959 г.

В соответствии с этой терминологией используют пять типовых структур (в порядке усложнения):

1. элемент данных;

2. агрегат данных;

3. запись;

4. набор;

5. база данных.

Дадим краткие определения этих структур.

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

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

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

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

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

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

1. БД может содержать любое количество типов записей и типов наборов;

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

3. тип записи может быть владельцем и одновременно членом нескольких типов наборов.

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

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

Операции над данными

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

1. найти следующее данное (запись);

2. найти предыдущее данное;

3. найти п-е данное;

4. найти первое (последнее) данное.

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

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

1. ВОЕННО-УЧЕТНАЯ СПЕЦИАЛЬНОСТЬ = 200100;

2. ВОЗРАСТ > 20;

3. ДАТА < 19.04.2002 и т.п.

Булево условие отбора формируется путем объединения простых условий с применением логических операций, например:

1. (ДАТА_РОЖДЕНИЯ < 28.12.1963) И (СТАЖ > 10);

2. (УЧЕНОЕ_ЗВАНИЕ = ДОЦЕНТ) ИЛИ (УЧЕНОЕ ЗВАНИЕ = ПРОФЕССОР) и т.п.

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

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

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

Различают внутренние и явные ограничения.

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

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

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

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

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

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

1. иерархическая модель данных;

2. сетевая модель данных;

3. реляционная модель данных;

4. бинарная модель данных;

5. семантическая сеть.

Лекция 16. Модели данных

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

Внутреннее описание определяет организацию данных в памяти ЭВМ и организацию доступа к ним. Оно соответствует наиболее детальному представлению о процессах обработки данных в системе.

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

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

Концепция реляционной модели данных была предложена Е.Ф. Коддом в 1970 г. в связи с необходимостью обеспечить независимость представления и описания данных от прикладных программ.

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

Рис. 15 Пример таблицы реляционной модели данных

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

Схема отношения: СОТРУДНИКИ (Фамилия, Должность, Возраст). Число атрибутов - степень отношения, число кортежей - мощность отношения.

Реляционная база данных - набор взаимосвязанных отношений. Каждое отношение (таблица) представляется в памяти компьютера в виде файла.

Существуют следующие соответствия понятий:

Сущность (класс)	Отношение	Таблица	Файл
Экземпляр (объект) Атрибут	Кортеж Атрибут	Строка Столбец	Запись Поле

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

Основных операций над отношениями насчитывается 8:

- традиционные операции над множествами (объединение, пересечение, разность (вычитание), декартово произведение, деление);

- специальные реляционные операции: проекция, соединение и выбор (селекция, ограничение).

Языки для выполнения операций над отношениями делят на 2 класса:

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

2) языки реляционного исчисления, предоставляющие пользователю набор правил для записи “запросов” к базе данных, в которых содержится только информация о желаемом результате. Пример - языки запросов SQL (Structured Query Language).

Реляционная база данных в целом соответствующая 3НФ, обладает рядом свойств, знание которых облегчает и упорядочивает процедуры обработки хранящейся в ней информации. Типичные процедуры, выполняемые с базой данных: выборка, корректировка и арифметические вычисления.

Условия запросов второго типа могут комбинироваться с помощью логических операций И, ИЛИ, НЕ.

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

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

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

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

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

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

Иерархическая модель данных

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

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

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

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

Всякий узел иерархической структуры (кроме корня дерева) имеет один порождающий узел. Ниже (см. рис.16) изображен пример схемы иерархической структуры.



Рис. 16. Пример иерархической модели данных

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

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

Сетевая модель данных

Рассмотрим табель учета рабочего времени

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

Таблица позволяет получать ответы на запросы двух типов:

1. По заданной фамилии сотрудника сообщить его рабочие часы на различные даты.

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

В нормализованном виде получим таблицу:

Дата	Сотрудник	Рабочие
S12	S34	часы
Число	День недели	ФИО	Таб.номер
Р1	Р2	Р3	Р4	Q5
1 1 2 2	Понедельник Вторник Понедельник Вторник	Иванов Иванов Петров Петров	01 01 02 02	8 9 10 0

В составе нормализованного файла можно выделить СЕИ, которые располагаются то в ключе, то в результате запроса, и атрибут Q5, всегда относящийся к результату запроса. Запросы такого вида называются инверсными по отношению друг к другу, СЕИ S12 и S34 назовем инверсным условием поиска, атрибут Q5 - информацией связи. Этим запросам можно поставить в соответствие следующие иерархические структуры, изображенные на рис. 17.

Рис.17

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

Рис.18 V-образная сетевая схема

Такая структура называется V-образной сетевой схемой. Она содержит два порождающих сегмента и один подчиненный. Тип связей, соответствующий схеме - “один-ко-многим”.

Подчиненный сегмент Q5 является информацией связи между S12 и S34.

Экземпляр рассматриваемой V-образной сетевой схемы называется сетевой БД. Его нормализованное представление - таблица ТАБЕЛЬ_1, а двухвходовое - ТАБЕЛЬ (двухвходовая таблица).

Лекция 17. Программные средства реализации фактографических информационных систем

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

ERwin - инструмент моделирования данных для разработки базы данных, который поддерживает методологии IDEF1X и IE . Вы можете совместно использовать BPwin и ERwin как для моделирования процесса, так и для моделирования данных и Вы можете обмениваться объектами и названиями атрибута между двумя программами. Эта возможность особенно полезна для пользователей, кто разрабатывает модель бизнес процесса и модель базы данных одновременно. Любые изменения, которые Вы проводите в объекте и названии атрибута в любой модели, могут быть внесены в другую модель. Вы можете также создать двухсторонние линии связи между моделью BPwin и связанной с ней моделью ERwin, что выполняется, автоматически каждый раз, когда Вы открываете одну из связанных диаграмм. Это проводится для синхронизации моделей.

ERwin - CASE-средство проектирования баз данных фирмы Platinum. ERwin сочетает графический интерфейс Windows, инструменты для построения ER-диаграмм, редакторы для создания логического и физического описания модели данных и прозрачную поддержку ведущих реляционных СУБД. Для удобства изложения материала здесь и далее использована оригинальная терминология, принятая в ERwin.

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

ERwin можно использовать совместно с некоторыми популярными средствами разработки клиентских частей приложений: PowerBuilder, Visual Basic, Delphi. Кроме того, ERwin поддерживает работу в среде групповой разработки ModelMart, являющейся продуктом той же Platinum.

Процесс моделирования в ERwin базируется на методологии проектирования реляционных баз данных IDEF1X. Данная методология была разработана для ВВС США и теперь широко используется в правительственных учреждениях и частных компаниях как в самих США, так и далеко за их пределами. Она определяет стандарты терминологии и графического изображения типовых элементов на ER-диаграммах.

Структура процесса моделирования в ERwin

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

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

Процесс построения информационной модели состоит из следующих этапов:

1. Создание логической модели данных:

- определение сущностей;

- определение зависимостей между сущностями;

- задание первичных и альтернативных ключей;

- определение неключевых атрибутов сущностей.

2.Переход к физическому описанию модели:

- назначение соответствий имя сущности - имя таблицы, атрибут сущности - атрибут таблицы;

- задание триггеров, хранимых процедур и ограничений.

3. Генерация базы данных.

Создание логической модели БД

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

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

1. атрибуты, составляющие первичный ключ;

2. неключевые атрибуты;

3. тип сущности (независимая/зависимая).

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

1. первичный ключ не должен принимать пустые (NULL) значения;

2. первичный ключ не должен изменяться в течение времени;

3. размер первичного ключа должен быть как можно меньшим.

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

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

Рассмотрим выше сказанное на примере сущности СОТРУДНИК (рис.19).



Рис. 19. Пример сущности

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

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

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

Пример использования альтернативного ключа приведен на Рис.20. Альтернативный ключ обозначается на диаграмме символами АКп, заключенными в скобки.

Рис. 20. Пример альтернативного ключа

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

Связь в ERwin трактуется как функциональная зависимость между двумя сущностями (в частности, возможна связь сущности с самой собой).

Если рассматривать диаграмму как графическое представление правил предметной области, то сущности являются существительными, а связи -глаголами. Например, между сущностями ОТДЕЛ и СОТРУДНИК существует связь "состоит из" (ОТДЕЛ состоит из СОТРУДНИКОВ).

В ERwin связи представлены пятью основными элементами информации: тип связи;

* родительская и дочерняя (зависимая) сущности;* мощность связи;

* допустимость пустых (null) значений;

* требования по обеспечению ссылочной целостности.

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