Представление предметной области и модели данных

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

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

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

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

1. способ, с помощью которого внешние пользователи представляют (описывают) объекты и связи;

2. форму и методы внутримашинного представления элементов данных и взаимосвязей;

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

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

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

 

Соотношение понятий модель данных и модель базы данных приведено на слайде.

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

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

- как средство спецификации типов данных и их организации, разрешенных в конкретной БД;

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

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

- как основа разработки семейства языков запросов и языков манипулирования данных;

- как основа архитектуры СУБД;

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

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

 

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

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

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

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

 

ТУТ

Лекция 4 (DB _ l 04. ppt)

Теоретические основы фактографических БД. Реляционная алгебра и реляционное исчисление. Основные операции реляционной алгебры

и реляционного исчисления при обработке данных

Основные понятия реляционной модели данных

Реляционная модель является удобной и наиболее привычной формой представления данных в виде таблицы. Такой способ представления 

1) понятен пользователю-непрограммисту;

2) позволяет легко изменять схему – присоединять новые элементы данных и записи без изменения соответствующих подсхем; 

3) обеспечивает необходимую гибкость при обработке непредвиденных запросов.

В математических дисциплинах понятию «таблица» соответствует понятие «отношение» (relation). Отсюда и произошло название модели – реляционная. Т.е., применительно к базам данных понятия «реляционная БД» и «табличная БД» по существу являются синонимами.

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

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

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

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

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

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

Остальные ключи, которые можно также использовать в качестве первичных, называются потенциальными или альтернативными ключами.

Модель предъявляет к таблицам следующие требования:

1. данные в ячейках таблицы должны быть структурно неделимыми;

2. данные в одном столбце должны быть одного типа;

3. каждый столбец должен быть уникальным (недопустимо дублирование столбцов);

4. столбцы размещаются в произвольном порядке;

5. строки размещаются в таблице также в произвольном порядке;

6. столбцы имеют уникальные наименования.

Основы реляционной алгебры

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

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

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

К числу операций реляционной алгебры (в том виде, в котором она была определена Э.Ф. Коддом) относят следующие: 

- бинарные операции:

   - объединение

   - пересечение

\      - разность

    - декартово произведение

J      - соединение

/      - деление

- унарные операции:

S     - выборка

Pr    - проекция.

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

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

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

 

Рассмотрим подробнее операции реляционной алгебры.

Объединение возвращает отношение, содержащее все кортежи, которые принадлежат либо одному из двух заданных отношений, либо им обоим.

Пересечение возвращает отношение, содержащее все кортежи, которые принадлежат одновременно двум заданным отношениям.

Разность возвращает отношение, содержащее все кортежи, которые принадлежат первому из двух заданных отношений и не принадлежат второму.

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

Выборка. Пусть задано логическое выражение – условие отбора F с атрибутами некоторой реляционной таблицы R. Тогда результатом выборки S_F (R) будет подмножество множества записей R, для которых F имеет значение истина.

Проекция. Пусть реляционная таблица R имеет n атрибутов. Зададим подмножество атрибутов a ₁, a ₂, …, a_m (m ≤ n). Тогда результатом проекции  будет реляционная таблица, имеющая m атрибутов из n атрибутов таблицы R. Следует отметить, что в результате операции количество кортежей может уменьшиться, т.к. по определению отношение не может содержать одинаковые кортежи.

Соединение. Рассмотрим вариант так называемого естественного соединения двух реляционных таблиц по равенству значений заданных атрибутов. Будем считать, что в отношениях сравниваются одноименные атрибуты. Тогда естественным соединением отношений R и P по равенству атрибутов a₁, a₂, …, a_m (каждый из которых присутствует в обоих отношениях) будет отношение, полученное после выборки из декартового произведения отношений R и P только тех кортежей, на которых значения заданных в операции атрибутов совпадают. При этом значения одноименных атрибутов в результирующем кортеже появляются один раз, а не дважды.

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

 

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

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

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

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

- области выборки, т.е. тех данных, которые должны быть дос­тавлены в результате выполнения операции выборки;

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

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

- производные переменные-отношения, т.е. те данные, которые должны быть включены в представления базы данных;

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 5 (DB _ l 05)

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

 

5.1. Документальные информационные системы, основанные на концепции БД

Элементом информационного массива АИС является документ. Документом при этом можно считать как всю совокупность записей (обычно текстов), хранящихся в БД, так и отдельные фрагменты текста - заголовки разделов, абзацы и т. д. при этом большую проблему представляет учет контекста употребления слова, зависящий больше не от синтаксических, а от семантических критериев. При поиске может использоваться сходство внутренней структуры отдельных документов, представленной, например, средствами формального языка типа SGML (Standard Generalized Markup Language). Помимо текста, для поиска могут использоваться содержащиеся в статьях уравнения, таблицы и графики, хотя пока такие средства поиска разрабатываются только для узких специализированных применений (поиск  по структурным химическим формулам, элементам электронных схем и т. д.). В более широком смысле, объектами текста могут являться заголовки или абзацы, примечания, ссылки, названия таблиц и т. п. В некоторых системах применяются свернутые (сигнатурные) образы документов.

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

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

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

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

1) сравниваются не сами объекты (они, как отмечалось, не очень удобны для сравнения), а описания - так называемые «поисковые образы»; 

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

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

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

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

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

Первая аналогична табличному способу представления данных о свойствах некоторого множества объектов: отдельному i -ому атрибуту соответствует i -я колонка, каждая ячейка которой содержит значение этого атрибута, свойственное отдельному объекту. Характерными чертами такого способа являются: 1) атомарность, т. е. отдельный атрибут отдельного объекта имеет строго одно значение; 2) предопределенность набора атрибутов – все существенные атрибуты объектов, информация о которых должна быть внесена в такую форму, должны быть определены на шаге, предшествующем построению таблицы и внесению в неё значений атрибутов.

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

Безусловно, в качестве поискового образа (ПО) может выступать и полное, «аналитическое» описание. Однако такое решение также имеет недостатки: 1) технические возможности для создания полнотекстовых баз данных появились сравнительно недавно, причем содержание, по которому возможен поиск, представлено, в основном, в форме текстов; 2) свободная лексика, авторская точка зрения и стиль изложения, свойственные первичным документам, затрудняют для пользователя нахождение общего с автором лексического пространства.

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

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