Дискретная математика & математическая логика

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

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

Элементы реляционной алгебры. Основная идея реляцион-

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

Результатом любой реляционной операции является некоторое отношение, поэтому можно образовывать реляционные выражения

спомощью скобок, как в обычной алгебре:

1.Объединение.

2.Пересечение.

3.Разность.

4.Декартово произведение.

5.Селекция (ограничение по условию).

6.Проекция.

7.Соединение и др.

1. Объединение.

abc R(ABC) = daf ,

cbd

S (ABC) = bga , daf

261

получим

abc

R(ABC) S (ABC)= V (ABC)= daf . cbd

bga

У отношений должны быть одинаковые ранги и имена атрибутов. Например: R (факультет, курс, группа) = {(ММ, 3, КМБ-1), (ММ, 3, ПМИ-2), (ММ, 3, КМБ-2)},

S (факультет, курс, группа) = {(ММ, 3, ПМИ-1), (ММ, 3, ПМИ-2)}, V (факультет, курс, группа) = {(ММ, 3, КМБ-1), (ММ, 3, ПМИ-2),

(ММ, 3, КМБ-2), (ММ, 3, ПМИ-1)}. 2. Пересечение.

R(ABC ) ∩ S (ABC)= W ( ABC)= daf .

W(факультет, курс, группа) = {(ММ, 3, ПМИ-2)}.

3.Разность.

R(ABC) − S (ABC) = Q(ABC) = abc . cbd

Q (факультет, курс, группа) = {(ММ, 3, КМБ-1), (ММ, 3, КМБ-2)}. 4. Декартово произведение.

abc N (ABC) = daf ,

cbd

M (ABC) = bga , daf

262

abcbga abcdaf

N (ABC) M (ABC) = J (ABC) = dafbga . dafdaf

cbdbga cbddaf

Например, N (номерзачетной книжки, ФИО, рейтинг), M (экзамен, дата, аудитория), то J (номер зачётной книжки, ФИО, рейтинг, экзамен, дата, аудитория).

5. Селекция S (ограничение) по некоторому условию F.

Пусть F такое: значение атрибута В = b:

SF (N ) = SF:B=b (N (ABC)) = abc . cbd

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

6. Проекция П – « вертикальная вырезка» части столбцов, например столбца В:

abc

ПВ (N (ABC)) = ПВ ( daf ) = b . a

cbd

7.Соединение – по некоторому условию F – это селекция по F

кдекартовому произведению.

Эквисоединение – это такое соединение, когда условие F имеет вид А = В, где А и В – атрибуты соединяемых отношений.

Натуральное (естественное) соединение V = R*S – это эк-

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

263

– если схема R полностью совпадает со схемой S, то натуральное соединение R*S равносильно пересечению R ∩ S;

– если R и S не имеют общих атрибутов, то натуральное соединение равносильно декартову произведению R · S.

8. Результатом реляционного деления V = R / S, где R и S от-

ношения рангов k1 и k2 (k1 > k2; k2 ≠ 0) является новое отношение, состоящее из кортежей длины (k1 – k2) таких, что для всех кортежей s, принадлежащих S, кортеж ts принадлежит R. Рассмотрим алгоритм вычисления частного.

Пусть n – количество строк отношения S. А. Цикл: от i = 1 до n. Начало:

–выделитьизR всекортежисокончанием равнымi-йстрокеS,

–полученный результат сохранить в виде множества корте-

жей Qi.

Конец цикла.

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

жеств: Qi, i = 1, …, n.

Пример. Пусть R (ФИО, Язык) – содержит информацию о том, какой программист знает какой язык (имеются полиглоты). Выделим ФИО тех программистов, которые знают одновременно два заданных в отношении S (Язык) языка. Результат получим при делении R на S.

Примечание.

Фамилии: Iv – Иванов, Pet – Петров, Sid – Сидоров, Gav – Гаврилов.

Языки: C – Си, Pas – Паскаль, For – Фортран.

R = {(Iv, C) (Iv, For) (Iv, Pas) (Pet, C) (Pet, Pas) (Sid, C) (Sid, For) (Gav, For) (Gav, Pas)}.

S = {(C) (For) }.

Q1 = {Iv, Pet, Sid} знают С, Q2 = {Iv, Sid, Gav} знают For.

V = R / S = {(Iv) (Sid)} знают оба языка.

Пример. Задана база данных с двумя отношениями:

–Студенты (номер, имя, рейтинг, группа);

–Группа (группа, староста, телефон, численность).

264

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

A. V1 = селекция отношения Группы по условию «Численность < 20».

B. V2 = натуральное соединение отношений Студенты и V1 по условию Студенты. группа = V1. группа;

C. V3 = проекция V2 на атрибут «Имя».

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

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

Основная идея состоит в том, чтобы любую операцию над отношениями описать в виде правильной формулы.

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

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

Базисными понятиями реляционного исчисления являются:

– понятие переменной с определенной для нее областью допустимых значений;

– понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы.

Вреальных языках БД вместо математических обозначений кванторов и логических связок используют, как правило, словесные обозначения:

265

Теоретико-множественные операторы реляционной алгебры также выражаются словесно:

–объединение: A UNION B,

–пересечение: A INTERSECT B,

–вычитание: A MINUS B,

–декартово произведение: A TIMES B. Специальные реляционные операторы:

–выборка (ограничение): A WHERE c,

–проекция: A[X, Y, …, Z] или PROJECT A{x, y, …, z},

–соединение: (A TIMES B) WHERE c,

–деление: A DIVIDEBY B.

266

12. ЗАДАЧИ

Задачи для коллективного решения

1.Построить граф машины Тьюринга для вычисления дизъюнкции двух переменных х1х2. Алфавит А = {λ, 0, 1, *}.

2.Написать программу для машины Поста, распознающей последовательность 3210. Алфавит А = {λ, 0, 1, 2, 3, *}.

Задачи для самостоятельной работы

1. Написать программу вычисление заданной функции двух переменных ab для машин Тьюринга и Поста.

Алфавит А = {λ, 0, 1, *}.

2. Написать программу вычисления заданной функции трёх переменных abс для машин Тьюринга и Поста. Алфавит А = {λ, 0, 1, *}. Сначала выполнить минимизацию по кубу соседних чисел. Затем решить задачу, предварительно построив граф вычислений.

Варианты заданий соответствуют номеру по списку группы:

267

СПИСОК ЛИТЕРАТУРЫ

1.Аляев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 357 с.

2.Тюрин С.Ф., Аляев Ю.А. Дискретная математика: практическая дискретная математика и математическая логика. – М.: Финансы и статистика, 2010. – 394 с.

3.Тюрин С.Ф., Аляев Ю.А. Дискретная математика: Тестдрайв по дискретной математике и математической логике. – М.: Финансы и статистика, 2011. – 134 с.

4.Новиков Ф.А. Дискретная математика для программиста. –

СПб.: Питер, 2001. – 502 с.

5.Дискретная математика [Электронный ресурс]. – URL: http: //

ru.wikipedia.org/wiki (датаобращения: 15.04.2012).

6.Канцедал С.А. Дискретная математика: учеб. пособие. – М.: ФОРУМ: ИНФРА-М, 2007. – 224 с. – ( Профессиональное образование).

7.Осипова В.А. Основы дискретной математики: учеб. посо-

бие. – М.: ФОРУМ: ИНФРА-М, 2006. – 160 с.

8.Коршунов Ю.М. Математические основы кибернетики. – М.: Энергоатомиздат, 1987. – 496 с.

9.Теория графов [Электронный ресурс]. – URL: http: //

rain.ifmo.ru/cat/view.php/theory/graph-general/enumeration-2005 (дата обращения: 15.04.2012).

10.Харченко В.С., Лысенко И.В., Тарасюк О.М. Надёжность

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

бие. – Харьков, 2007. – 44 с.

11.Карпов Ю.Г. Теория автоматов. – СПб.: Питер, 2003. – 208 с.

12.Дискретная математика: конечные автоматы, рекурсивные функции: метод. рекомендации / сост. В.В. Морозенко; Перм. ун-т. –

Пермь, 2005. – 72 с.

269