7. Данные и модели данных

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

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

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

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

Приведем пример данной модели.

Ф.И.О.	Рост	Вес
Иванов Иван Иванович	180	75
Петров Пётр Петрович	190	100

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

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

M = {G, R, O},

где G – множество правил порождения структур данных (схемы), R – множество правил порождения ограничений целостности, О – множество допустимых операций над данными.

Примечание. Определение порождающих правил, на которые ссылается данное определение, дано в теории формальных языков и формальных грамматик [42].

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

Рассмотрим подробнее подходы к определению каждой из составляющих модели данных,

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

Абстракция.

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

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

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

Агрегация – абстракция, посредством которой объект конструируется из других базовых объектов. Операция, обратная агрегации называется декомпозицией.

Простейший пример структуризации данных приведен на схеме (рис. 1):

Иванов Петров Сидоров

очник вечерник заочник 1

студент 2

факультет группа стипендия 3

1.классификация/экземпляризация

2.обобщение/специализация

3.декомпозиция/агрегация

Рис. 1. Способы абстракции

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

Основные формы хранения данных.

Данные, в соответствии с определением, должны быть формализованы. Рассмотрим наиболее часто применяемые формы хранения данных.

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

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

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

Примеры.

{1¹,5¹,6²,7²,9²,14³} – комплекс,

{1¹,5¹,6¹,7¹,9¹,14¹}={1,5,6,7,9,14} – множество,

{1¹,5²,6³,7⁴,9⁵,14⁶}=<1,5,6,7,9,14> - кортеж.

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

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

Отношение – это некоторое подмножество декартова произведения одного или более множеств.

Например: СТУДЕНТЫ ФИО номер_зачетки стипендия

(фактически СТУДЕНТЫ – это таблица с тремя атрибутами (полями) – «ФИО», «номер_зачетки» и «стипендия»).

ФИО	Номер_зачетки	Стипендия

Интенсионал отношения определяется интенсионалами, входящих в него множеств и общими свойствами собственно отношения.

Экстенсионал отношения определяет одну из возможных его реализаций.

Таким образом, интенсионал БД определяет структуру, а экстенсионал – конкретное содержание БД.

Табличное представление структур данных.

Наиболее часто в моделях данных приходится иметь дело с табличным представлением данных.

Интенсионал БД

Студенты Преподаватели

ФИО преп.	Стаж	З/п
Айдахов	8	3500
Бызанов	22	6000

ФИО студ.	Ном зач.	Стип.
Иванов	18/322	250
Петров	19/324	250
Сидоров	19/325	400

Учебный курс

ФИО студ	ФИО преп.	Назв. курса	Кол-во ч	Оценка
Иванов	Айдахов	ТОИ	36	5
Петров	Айдахов	ТОИ	36	3
Сидоров	Бызанов	Осн.иск.инт.	72	4
Петров	Бызанов	Осн.иск.инт.	72	5

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

На примере видно, что фактически схему данных (интенсионал) БД в данном представлении определяют названия полей (столбцов, атрибутов) таблиц и названия самих таблиц. Содержимое таблиц определяет экстенсионал БД. Важным аспектом является связи между таблицами, реализованные путем копирования значений полей из одной таблицы в другую. Так, таблица «уч. курс» фактически содержит ссылки на таблицы «студенты» и «преподаватели», так как поле «ФИО студ.» связано с полем «ФИО» таблицы «студенты», а поле «ФИО преп.» с полем «ФИО» таблицы «преподаватели».

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

Свойства ограничений целостности (ОЦ).

Рассмотрим произвольное ограничение C_i в схеме данных.

1. Произвольное ограничение C_i правильно построено, если оно соответствует синтаксическим правилам R определения ОЦ. Формально только правильно построенное ОЦ имеет право называться ОЦ.

2. Произвольное ограничение C_i удовлетворяет состоянию БД DBS_k, если оно истинно для него (под состоянием БД понимается конкретный вариант наполнения данными).

3. Произвольное ограничение C_i удовлетворяемо, если существует соcтояние БД DBS_m, которому оно удовлетворяет и неудовлетворяемо (недостоверно), если не существует такого состояния.

Примечание. Недостоверные ОЦ приводят к невозможности построения БД, фактически из-за несовместимости требований. К таковым относятся внутренне противоречивые ограничения (например возраст<30 /\ возраст>40), а также ОЦ, несовместимые с реальными данными (например возраст<0).

4. Произвольное ограничение является логическим следствием ограничений C₁..C_m, если ограничение C_i удовлетворяет всем состояниям базы данных, которым удовлетворяют ограничения С₁..C_m.

Схема S называется удовлетворяемой, если существует состояние DBS_k, удовлетворяющее ей, иначе схема называется противоречивой.

Типы ограничений целостности.

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

1. Ограничения на значение атрибутов.

Эти ограничения могут быть заданы следующим образом:

A) принадлежностью к определенному типу или домену (например возраст – целое число);

B) операциями сравнения (например возраст>0);

C) диапазоном допустимых значений (например оценка=2..5);

D) перечислением допустимых значений (например пол={‘M’,’Ж’};

E) более общим логическим выражением

(например (оценка>=2)and(оценка<=5));

Е) с использованием функций агрегирования. Count - количество, avg - среднее значение, sum – сумма. Например:

Sum (БОЛЬНИЦЫ. число_коек) > 500 – cуммарное число коек в больницах больше 500;

AVG (СОТРУДНИКИ. з/п) 5000..10000 – средняя з/п сотрудников от 5000 до 10000 руб.;

Count (ПРЕПОДАВАТЕЛИ.стаж>10)>=100 – число преподавателей со стажем больше 10 лет больше или равно 100.

Ограничения на отображения.

Выделяют следующие разновидности данного ограничения.

А) Между атрибутами одного отношения (ключи).

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

Пример ключа – ФИО для таблицы ПРЕПОДАВАТЕЛИ (см. пример в пункте 1.2.3)

Б) Между атрибутами разных отношений.

Приведем несколько определений.

Пусть даны множества A и B. F: A->B – отображение тогда и только тогда, когда f – подмножество декартового произведения A B (f A B)

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

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

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

Различают два вида операций.

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

Примерами могут служить операции реляционной алгебры, определенные над множеством отношений.

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

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

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

Допы:

«сущность-связь»(ER-модель), реляционные модели, сетевые, иерархические