Краткие сведения из теории отношений

Определение. Прямым (декартовым) произведением двух множеств A и B называется множество упорядоченных пар (a,b), в которых aÎA и bÎB:

A´B={(a,b)| aÎA & bÎB}.

Степенью множества A называется его прямое произведение само на себя:

Aⁿ=A´…´A – всего n раз.

Упорядоченную пару элементов arb=(a,b), aÎA & bÎB, называют двухместным или бинарным отношением. Упорядоченный набор из n элементов (a₁, …, a_n) называют n-местным отношением или кортежем.

Пользуясь введенным понятием декартова произведения и степени множества, мы можем сказать, что бинарное отношение есть подмножество прямого произведения A´B:

R=arb={(a,b)ÎR|RÌ A´B}.

Если A=B, то есть R= a r b ={(a,b)| a ÎA& b ÎA}, то отношение R называют однородным отношением. То есть можно сказать, что однородное отношение – это отношение RÌA².

Однородные бинарные отношения – важный тип отношений для многих приложений информатики, в частности, для задач теории графов. Множество ребер любого графа задают однородное бинарное отношение на множестве его вершин V. Множество точек на плоскости с заданной системой координат (X,Y) – это тоже однородное бинарное отношение.

Пусть у нас есть два бинарных отношения: R₁Ì A´B и R₂Ì B´C (говорят так: отношение из A в B и отношение из B в C).

Композицией отношений R₁ и R₂ называется отношение R из A в C:

R= R₁° R₂ ={(a,c)|aÎA&cÎC&$bÎB: arb & brc }.

Рассмотрим пример.

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

Здесь R₁Ì A´B – «A получает специальность B», R₂Ì B´C – «на В изучается дисциплина C». Искомое отношение R – «A изучает дисциплину C» есть композиция отношений R= R₁° R₂, то есть чтобы студент aÎA изучал дисциплину cÎC нужно, чтобы он учился на специальности bÎB, что соответствует отношению arb, и на этой специальности изучалась данная дисциплина cÎC, что соответствует отношению brc. Значит, для решения задачи нам нужно посмотреть, для каких пар (a,b) имеются пары (b,c).

Составим бинарные таблицы R ₁ и R ₂ для данных отношений. Пусть r_ij(1) и r_jk(2) - элементы этой таблицы, соответствующие отношениям a_i r b_j и b_j r c_k. Одновременное выполнение этих отношений соответствует логическому произведению соответствующих элементов таблицы, и значение каждого элемента r_ik итоговой таблицы R будет зависеть от того, принимает ли хотя бы одна из этих элементарных коньюнкций значение «1», что соответствует логическому сложению. То есть при i=1,…,M, j=1,…,N, k=1,…,K мы имеем: R= R₁° R₂ = R ₁× R ₂, где R ₁× R ₂ - логическое перемножение матриц.

Степенью отношения Rⁿ называется композиция отношения R n раз с самим собой.

Ядром отношения RÌ A´B называется композиция R*= R°R^-1. Ядро отношения является отношением на A.

Проекцией (n-местного) отношения (a₁,…,a_n) называют подмножество (a_j,…,a_j+k,…,a_m), m<n.

Свойства однородных бинарных отношений – симметричность (если aRb то bRa), рефлексивность (aRa) и транзитивность (если aRb и bRc, то aRc). В графовом представлении симметричность отображается неориентированным ребром, рефлексивность означает наличие петли, а транзитивность означает достижимость вершины с из вершины а. Вес ребра или дуги может обозначать силу связи или тип отношения.

Функциональным отношением или функцией B=f(A) называется такое отношение из множества A в множество B (A®B), что каждому элементу из A соответствует ровно один элемент из B.

Реляционные модели. Название происходит от английского слова relations (отношение). Идеология реляционных бах данных основывается на теории отношений.

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

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

1) уникальность – однозначно идентифицирует объект или определенное множество объектов; в этом случае говорят, что любая проекция B отношения R функционально полно зависит от проекции A. Функциональную зависимость проекций A,B отношения R (наборов атрибутов таблицы) будем обозначать A->B.

Функциональная зависимость называется транзитивной, если существует проекция C, такая что: а) CÏA; б) BÏC; в) имеет место A->C; при этом обратной зависимости нет; г) имеет место C->B.

2) неизбыточность – ни один из атрибутов нельзя удалить, не нарушив его уникальности.

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

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

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

При проектировании реляционной БД атрибутов классов-сущностей, объединенные связью типа «агрегирование» в концептуальной модели, объединяются в единый набор атрибутов таблицы. Связи типа «обобщение» (наследование) реализуются либо на уровне мета-файла (так называемые ГИП-документы конкретного проекта в пакете ArcView) либо через таблицу атрибутов (например, в ArcView в каждом наборе атрибутов графического объекта есть поле Shape, обозначающее тип графического примитива).

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

Говорят, что отношение находится в первой нормальной форме (1NF), если в каждой ячейке таблицы содержится ровно один элемент.

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

Отношение находится в третьей нормальной форме (3NF), если оно находится в первых двух и не содержит транзитивных функциональных зависимостей.

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

Реляционные модели используются в ГИС преимущественно на уровне агрегирования пространственных и атрибутивных данных. Преобладают в векторных ГИС, хотя в растровых также применяются.

Дата добавления: 2014-01-11