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

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

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

По аналогии с исчислением предикатов на множестве кортежей t определим переменные-кортежи (x,y,z) и постоянные–кортежи (a,b,c).

Таким образом, если результатом алгебраической операции над отношениями является отношение, то результатом реляционного исчисления является множество кортежей t, каждый из которых определяется истинным значением некоторой логической функции F(t), т.е. r’={t’|F(t), t’Î{t}}, где F(t) – формула предиката (логическая функция); при значении F(t)=и из множества связанных переменных-кортежей t извлекается подмножество свободных переменных-кортежей t’Îr’.

Введем понятия элементарной формулы (атома) и формулы в реляционном исчислении:

• если r - отношение, а t - кортеж, то r(t) – элементарная формула,

• если x и y – переменные-кортежи и дан оператор θ сравнения значений двух (или нескольких) атрибутов A_i и A_j, то (x(A_i)θy(A_j)) - элементарная формула,

• иных элементарных формул нет,

• любая элементарная формула есть формула, т.е. F=r(t), или F=x(A_i)θk_j, или F=x(A_i)θy(A_j), где k_j – значение атрибута,

• если F₁ и F₂ -формулы, то (¬F), (F₁∨F₂), (F₁&F₂) - также формулы,

• если x – переменная-кортеж и F(x) - формула, то ∃_x(F(x)) и ∀_x(F(x)) - также формулы,

• иных формул нет.

Здесь формула ∃_x(F(x)) утверждает, что существует такое значение кортежа-переменной х, при подстановке которого эта формула становится истинной; формула ∀_x(F(x)) утверждает, что при подстановке любого кортежа подходящей арности эта формула становится истинной.

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

Если существует выражение реляционной алгебры, то существует эквивалентное ему выражение в реляционном исчислении с переменными-кортежами.

Операция выборки - имеет вид:r’={t’|∃_x(r(x)&(<условия на атрибуты переменного-кортежа>))}. Квантор существования выбирает такие переменные-кортежи, для которых формула (<условия на атрибуты переменного-кортежа>) имеет значение истины.

Примеры условий на атрибуты переменного-кортежа:

(x(A_i)θk_i),

(x(A_i)θk_i)and(x(A_s)θk_s),

(x(A_i)θk_i)or(x(A_s)θk_s),

(x(A_i)θx(A_s)).

Например, дано отношение «учебный_план1»:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Физика				Экзамен
Информатика				Зачет
Матлогика				Экзамен
Электроника				Экзамен

1) Определить формы занятий и формы отчетности по информатике и электронике. Решение: r’={t’|$_x(учебный_план1(х)&(x(дисциплина)=‘информатика’or (дисциплина)= ‘электроника’))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Информатика				Зачет
Электроника				Экзамен

2) Определить дисциплины, для которых число часов лекций превышает число часов л/з, а также формы занятий и формы отчетности для них. Решение: r’={t’|$_x(учебный_план1(х)&(x(лекции)>x(л/з)))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Информатика				Зачет
Матлогика				Экзамен
Электроника				Экзамен

Операция проекции - имеет вид: r’={t’|∀_x(r(x)&(t’[1]=x(A_i))&(t’[2]=x(A_j))&…&(t[k]= x(A_n)))}, где [] – место атрибута A_i,A_j,…A_n в кортеже t’. Квантор всеобщности использует в отношении-результате все кортежи исходного отношения, но не все его компоненты-атрибуты. Эта операция позволяет также переупорядочить расположение атрибутов в кортеже.

Например, по отношению учебный_план1 определить формы отчетности по каждой дисциплине. Решение: r’={t’|"_x(учебный_план1(х)&(t’[1]=x(дисциплина))&(t’[2]=x(отчетность)))}.

Результат:

Дисциплина	Отчетность
Физика	Экзамен
Информатика	Зачет
Матлогика	Экзамен
Электроника	Экзамен

Операция объединения – имеет вид r’={t’|∀_x∀_y(r₁(x)&r₂(y)&((t’=x)∨(t’=y)))}. Квантор всеобщности объединяет в отношении r’ все кортежи отношений r₁(x) и r₂(y). Если атрибуты кортежей не упорядочены, то атрибуты кортежа второго отношения должны быть упорядочены так же, как у кортежей первого отношения (см. операцию проекции).

Например, дано отношение учебный_план2:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Культурология				Зачет
Матанализ				Экзамен
Физика				Экзамен
Электроника				Экзамен

Выполнить объединение данного отношения и отношения учебный_план1. Решение: r’={t’|∀_x∀_y(учебный_план1(x)&учебный_план2(y)&((t’=x)∨(t’=y)))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Физика				Экзамен
Информатика				Зачет
Матлогика				Экзамен
Электроника				Экзамен
Культурология				Зачет
Матанализ				Экзамен

Операция разности – имеет вид: r’={t’|∃_x∃_y(r₁(x)&r₂(y)&(t’=x)&¬(t’=y))}. Кванторы существования накладывают условия для извлечения только таких кортежей первого отношения, которых нет во втором.

Например, даны отношения учебный_план1 и учебный_план2. Определить перечень дисциплин, отсутствующих в отношении учебный_план2. Решение: r’={t’|$_x$_y(учебный_план1(x) &учебный_план2(y)&(t’=x)&Ø(t’=y))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Информатика				Зачет
Матлогика				Экзамен

Операция пересечения – имеет вид: r’={t’|∃_x∃_y(r₁(x)&r₂(y)&(t’=x)&(t’=y))}. Кванторы существования позволяют выбрать одинаковые кортежи в первом и втором отношениях.

Например, даны отношения учебный_план1 и учебный_план2. Определить перечень дисциплин, общих для обоих отношений. Решение: r’={t’|$_x$_y(учебный_план1(x)&учебный_план2(y)&(t’=x)&(t’=y))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность
Физика				Экзамен
Электроника				Экзамен

Операция прямого произведения – имеет вид: r’={t’|∀_x∀_y(r₁(x)&r₂(y)&(t’[1]= x[1])&(t’[2]= x[2])&...&(t’[n₁]=x[n₁])&(t’[n₁+1]=y[1])&(t’[n₁+2]=y[2]) &...&(t’[n₁+n₂]=y[n₂]))}, где [] – место атрибута в кортеже t’,x или y. Кванторы всеобщности позволяют приписать каждый кортеж второго отношения к каждому кортежу первого отношения (операция конкатенации).

Например, даны отношения учебный_план1 и преподаватель1:

Фамилия И.О.	Должность	Стаж
Иванов И.И.	Доцент
Иванов В.В.	Профессор
Петров П.П.	Доцент
Сидоров С.С.	Доцент

Определить по каждой дисциплине из учебного плана список возможных преподавателей: r’={t’|∀_x∀_y(учебный_план1(x)&преподаватель1(y)&(t’[1]=x[1])&(t’[2]=x[2])&(t’[3]=x[3])&(t’[4]=х[4])&(t’[5]=x[5]) &(t’[6]=y[1])&(t’[7]= y[2])&(t’[8]=y[3]))}.

Результат:

Дисциплина	Лекции	Л/з	П/з	Отчетность	Фамилия И.О.	Должность	Стаж
Физика				Экзамен	Иванов И.И.	Доцент
Физика				Экзамен	Иванов В.В.	Профессор
Физика				Экзамен	Петров П.П.	Доцент
Физика				Экзамен	Сидоров С.С.	Доцент
Информатика				Зачет	Иванов И.И.	Доцент
Информатика				Зачет	Иванов В.В.	Профессор
Информатика				Зачет	Петров П.П.	Доцент
Информатика				Зачет	Сидоров С.С.	Доцент
Матлогика				Экзамен	Иванов И.И.	Доцент
Матлогика				Экзамен	Иванов В.В.	Профессор
Матлогика				Экзамен	Петров П.П.	Доцент
Матлогика				Экзамен	Сидоров С.С.	Доцент
Электроника				Экзамен	Иванов И.И.	Доцент
Электроника				Экзамен	Иванов В.В.	Профессор
Электроника				Экзамен	Петров П.П.	Доцент
Электроника				Экзамен	Сидоров С.С.	Доцент

Операция естественного соединения – имеет вид: r’={t’|∃_x∃_y(r₁(x)&r₂(y)&(x(A_i)=y(A_i))& (t’[1]=x[1])&…&(t’[n₁]= x[n₁])&(t’[n₁+1]=y[1])& (t’[n₁+2]=y[2])&...&(t’[n₁+n₂-1] = y[n₂]))}. Кванторы существования обусловлены выбором переменных-кортежей, имеющих одинаковые значения одноименных атрибутов двух отношений.

Например, даны отношения учебный_план2 и преподаватель2:

Фамилия И.О.	Должность	Дисциплина
Иванов И.И.	Доцент	Культурология
Иванов В.В.	Профессор	Физика
Петров П.П.	Доцент	Матанализ
Сидоров С.С.	Доцент	Электроника

Определить, какие преподаватели ведут дисциплины из учебного плана, и указать характеристики этих дисциплин. Решение: r’={t’|∃_x∃_y(преподаватель2(x)&учебный_план1(y)&(х(Дисциплина)=y(Дисциплина))& (t’[1]=x[1])& (t’[2]=x[2])&(t’[3]=х[3])& (t’[4]=y[2])&(t’[5]=y[3])& (t’[6]=y[4])&(t’[7]=y[5]))}.

Результат:

Фамилия И.О.	Должность	Дисциплина	Лекции	Л/з	П/з	Отчетность
Иванов И.И.	Доцент	Культурология				Зачет
Иванов В.В.	Профессор	Физика				Экзамен
Петров П.П.	Доцент	Матанализ				Экзамен
Сидоров С.С.	Доцент	Электроника				Экзамен

Операция θ -соединения - имеет вид: r’={t’|∃_x∃_y(r₁(x)&r₂(y)&<условие>& (t’[1]=x[1])&...&(t’[i]=x[i])&…&(t’[n₁]=x[n₁])&(t’[n₁+1]=y[1])&…& (t’[n₁+j]=y[j])&... &(t’[n₁+n₂]=y[n₂]))}.

Примеры условий:

(x(A_i)θy(f(A_i))),

(x(f(A))θy(A_i)),

((x(A_i)θy(A_i))and(x(A_u)θy(A_v))),

((x(A_i)θy(A_i))or(x(A_u)θy(A_v))).

Например, даны отношения учебный_план2 и преподаватель3:

Фамилия И.О.	Должность	Нагрузка
Иванов И.И.	Доцент
Иванов В.В.	Профессор
Петров П.П.	Доцент
Сидоров С.С.	Доцент

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

r’={t’|∃_x∃_y(преподаватель3(x)&учебный_план2(y)&(x(Нагрузка)³(y(Лекции)+y(Л/з)+y(П/з)))&(t’[1]=x[1])&(t’[2]=x[2])&(t’[3]=x[3])&(t’[4]=y[1])&(t’[5]=y[2])&(t’[6]=y[3])&(t’[7]=y[4])&(t’[8]=y[5]))}.

Результат:

Фамилия И.О.	Должность	Нагрузка	Дисциплина	Лекции	Л/з	П/з	Отчетность
Иванов И.И.	Доцент		Культурология				Зачет
Петров П.П.	Доцент		Культурология				Зачет
Петров П.П.	Доцент		Матанализ				Экзамен
Сидоров С.С.	Доцент		Культурология				Зачет

5. Нечёткая логика

Нечёткая логика была предложена американским профессором Л. Заде, который для оценки частичной истинности или частичной ложности высказывания ввел множество рациональных чисел на интервале [0,1].

Например, дано высказывание «Сидоров имеет рост 178см.» и дан предикат Р(x):=«x – высокий человек». Спрашивается: «Сидоров – высокий человек?». Некто установил значение истины высказывания Р(Сидоров)=0,75. Это означает, что высказывание «Сидоров – высокий человек» истинно на три четверти. Точно так же оно на одну четверть ложно.

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

Слабым моментом нечеткой логики является задание значения истинности на интервале [0,1]. Это - задача высококвалифицированных специалистов в конкретной отрасли знаний - экспертов. И, как правило, при разработке экспертных систем используют опыт многих специалистов.

5.1. Нечёткие множества

В основе нечеткой логики лежит понятие нечеткого множества.

Пусть дано универсальное множество U. Если на этом множестве задать подмножество X’, характеристическое свойство которого недостаточно четко определено, то принадлежность элементов u∈U множеству X’ может быть описана функцией принадлежности - μ_X’(u) как субъективная мера. Значение функции μ_X’(u) называют степенью принадлежности и определяют на интервале [0, 1], т.е. μ_X’ (u_i): U →[0, 1].

Тогда модель нечеткого множества X’ определяется следующим образом:

X’={μ_X’(u₁)/u₁, μ_X’(u₂)/u₂,..., μ_X’(u_n)/u_n},

где μ_X’(u_i)∈[0,1] – степень принадлежности каждого элемента u_i∈U нечёткому множеству X’: μ_X’(u_i): U →[0, 1],

U – универсальное множество,

μ_X’(u) – функция принадлежности.

Связь между четким и нечетким множествами выражается следующими положениями:

1) носителем нечёткого множества X’ являются элементы четкого подмножества X⊆U, т. е. X={u₁, u₂,...,u_n}⊆U, если для u_i∈X μ_X’(u_i)>0,

2) если для u_i∈U имеем μ_X’(u_i)=1, то элемент u_i четко принадлежит множеству X’,

3) если для u_i∈U имеем μ_X’(u_i)=0, то элемент u_i четко не принадлежит множеству X’,

4) если все элементы носителя X имеют значение μ_X’(u_i)=1, то дано четкое подмножество X’=X множества U,

5) если все элементы носителя X имеют значение μ_X’(u_i)=0, то дано пустое множество, т.е. X’=∅.

Например, дано 10 предметов. Требуется сформировать множество подмножеств, удовлетворяющих предикату «несколько предметов». Иначе, надо определить нечеткое понятие «несколько предметов».

Решение:

Пусть U={1, 2, 3, …, 10} – универсальное множество. Эксперт, пользуясь своим знанием языка, так определил понятие «несколько предметов» - Х’: X’={0.6/3, 0.8/4, 0.8/5, 0.8/6, 0.6/7, 0.6/8, 0.6/9}, т.е. подмножества из 3, 4 и т.д. (до 9 включительно) предметов могут соответствовать понятию «несколько предметов» с определенной в формуле степенью принадлежности. Для подмножеств, содержащих один, два или все 10 предметов, эксперт определил степень принадлежности, равную нулю. Носитель нечеткого множества X’ – четкое множество: X={3,4,5,6,7,8,9}.

5.2. Нечёткая алгебра

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

Пусть Т’(U)={X’₁,X’₂,…} – множество нечетких подмножеств универсального множества U, F={Ø,È,Ç} – множество операторов. Тогда нечеткая алгебра определяется как:

A=<T’(U), F, m(u_i)>,

где m(u_i) – функция принадлежности элементов (u_i) универсального множества U нечеткому подмножеству X’.

Определим синтаксические правила для формул нечеткой алгебры:

1) любое нечеткое подмножество универсального множества есть элементарная формула, т.е. X’_i=F’_i;

2) других элементарных формул нет;

3) любая элементарная формула есть формула,

4) если F’₁ и F’₂ – формулы, то ØF’, (F’₁ÈF’₂), (F’₁ÇF’₂) – также формулы;

5) других формул нет.

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