Логическое программирование

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

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

Пролог-программа состоит из предложений трех типов: факты, правила и вопросы.

Факты есть высказывания, которые заканчиваются точкой и имеют значение только “истины”. Структура такого предложения описана предикатом или n-местным отношением, все аргументы которого есть предметные постоянные. Предметные постоянные всегда начинаются со сточной буквы латинского алфавита и представляют собой последовательность букв, цифр и знака подчеркивания.

Например,

· простое_число (3).

Это - высказывание, структура которого описана предикатом

P₁(x):=”x - простое число”.

· частное_от_деления(6, 2, 3).

Это - высказывание, структура которого описана предикатом

P₃(x, y, z):=”z есть частное от деления числа x на y”.

· студент_университета,_обучающийся_по_специальности (Петров, КГТУ, прикладная информатика").

Это - высказывание, структура которого описана предикатом

P₆(x, y, z):= "студент x университета y, обучающийся по специальности z”.

·:

отец (игорь, святослав).

отец (святослав, владимир).

отец (владимир, борис).

отец (владимир, глеб). / родословная русских

дед (игорь, владимир). князей X века /.

дед (святослав, борис).

дед (святослав, глеб).

брат (борис, глеб).

Это - высказывания, структура которых описана предикатами

P₄(X, Y):=”X – отец Y”, P₅(X, Y):=”X – дед Y”, P₆(X, Y):=”X – брат Y”.

Структуру высказывания или функциональную зависимость между предметными постоянными описывают термы.

Множество фактов формирует базу данных о предметной области.

Правила есть суждения, истинность которых зависит от истинности условий: “если истинны условия (посылки, цели), то истинно и заключение (вывод)”. Это – известное правило m.p.

На языке Prolog правила записывают так:

<заключение>:-

<условия>”.”

Символ “:-“ соответствует символу обратной импликации ””.

Левую часть правила называют головой предложения, а правую – телом предложения. В теле предложения перечисляют условия, а в голове - заключение.

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

<условие>{“,”<условие>}”.”,

если дизъюнктивную, - так:

<условие>{“;”<условие>}”.”.

Голова предложения всегда сдвинута влево относительно перечня условий. Каждое условие начинается с новой строки.

На языке Prolog эти правила записывают так:

<заключение>:-

<условие_1>”,”

<условие_2>”;”

<условие_3>”.”

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

Например, в базе знаний могут быть правила:

дед(X, Y):-

отец(X, Z),

отец (Z, Y).

брат(X, Y):-

отец (Z, X),

отец(Z, Y).

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

Пример:

?-дед (святослав, Y). /“Кому Святослав является дедом?”/.

В базе знаний есть правило:

дед(X, Y):-

отец(X, Z),

отец (Z, Y).

Выполняя подстановку в условия фактов из базы данных, получим:

отец (святослав, владимир).

отец (владимир, борис).

отец (владимир, глеб).

Следовательно, ответ на поставленный вопрос:

дед (святослав, борис, глеб). /”Святослав дед Борису и Глебу”/

Пример:

?-брат(X, Y). /”Есть ли братья среди русских князей X века”/.

В базе знаний есть правило:

брат(X, Y):-

отец (Z, X),

отец(Z, Y).

Выполняя подстановку в условия фактов из базы данных, получим:

отец (владимир, борис).

отец (владимир, глеб).

Следовательно, ответ на поставленный вопрос:

брат (борис, глеб). /”Борис и Глеб – братья”/.

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

Например, для родословной русских князей X века имеем:

· дед (игорь, владимир):-

отец (игорь, святослав),

отец (святослав, владимир).

Это - высказывание о том, что если ‘игорь’ был отцом ‘святослава’, а ‘святослав’ – отцом ‘владимира’, то ‘игорь’ был дедом ‘владимиру’.

· дед (святослав, борис), дед(святослав, глеб):-

отец (святослав, владимир),

отец (владимир, борис);

отец (святослав, владимир),

отец (владимир, глеб).

Это есть высказывание о том, что ‘святослав’ был отцом ‘владимира’ и дедом ‘борису’ и ‘глебу’.

· брат(борис, глеб):-.

родитель(владимир, борис),

родитель(владимир,глеб).

Это есть высказывание о том, что если ‘владимир’ был отцом ‘бориса’ и отцом ‘глеба’, то ‘борис’ и ‘глеб’ были братьями.

Логика реляционная

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

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

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

Между таблицей, отношением и файлом есть соответствие:

ТАБЛИЦА ® ОТНОШЕНИЕ ® ФАЙЛ

строка ® кортеж ® запись

имя столбца ® имя атрибута ® имя поля

тип атрибута ® тип домена ® тип поля

 

Верхняя строка таблицы формирует “шапку”, а остальные строки – “тело” таблицы. Ниже, как пример таблицы, дан фрагмент учебного плана.

 

дисциплина	лекции (ч)	лаб.зан-я (ч)	практ.зан-я (ч)	отчетность (зач., экз.)
физика				экз
информа-тика				зач.

...............

Эта таблица (отношение) отражает связи между наименованием учебной дисциплины, видом и числом часов аудиторных занятий и формой отчетности. Именами атрибутов отношения являются: ”дисциплина”, “лекции_(ч)”, “лаб.занятия_(ч)”, “практ.занятия_(ч)”, “отчетность_(зач., экз.)”. Значением атрибута “дисциплина” являются слова {физика, информатика,..}, “отчетность” – {зач., экз.}. Тип этих атрибутов - <слово>, а тип домена – CHAR (строковое). Значением атрибутов “лекции_(ч)”, “лабораторные занятия_(ч)” и “практические занятия_(ч)” являются целые числа {17, 34, 51, 68}. Тип этих атрибутов - <целое_число>, а тип домена –INTEGER (целое). Кортежами этого отношения являются: (физика, 34, 34, 17, экз.), (информатика 51, 34, 0, зач.).

Таким образом, если дано множество атрибутов A ={A₁, A₂,...A_n} и множество доменов D ={D₁, D₂,...D_m}, то кортеж отношения есть t=(d₁, d₂,...d_n) где d_iÎ D.

Так как отношение есть множество совместимых кортежей, то

r={t| t=(d₁, d₂,...d_n), d_iÎ D }.

Отношение, заданное на множестве упорядоченных кортежей, есть подмножество n-арного прямого произведения доменов, т.е.

r={t| t=(d₁, d₂,...d_n), d_iÎ D }Í ₁Äⁿ D.

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

rel(r)=(A₁, A₂,¼, A_n).

Например,

rel(уч_план_1)=(дисциплина, лекции_(ч), лаб_занятия_(ч),

практ_занятия_(ч), отчетность_(зач.,экз.)).

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

REL (R)={rel(r)}.

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

Например, запись файла “уч_план_1” может быть (дисциплина=физика, лекции_(ч)=34, лаб.занятия_(ч)=34, практ.занятия_(ч)=17, отчетность_зач., экз.=экз.) или такой (практ.занятия_(ч)=17, дисциплина=физика, отчетность_ (зач., экз.)=экз., лаб.занятия_(ч)=34, лекции_(ч)=34).

Для каждого отношения должен быть задан ключ.

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

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

1) все атрибуты кортежа должны быть элементарными (или каждое поле записи должно иметь один тип: INTEGER (целые), REAL (вещественные), CHARACTER (строковые) или BOOLEAN (булевские)) и не должны быть функционально связаны между собой;

2) все кортежи должны быть упорядоченными и иметь одинаковое число компо­нент в одном отношении (или все записи в файле должны иметь оди­наковое число полей);

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

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

Реляционная алгебра

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

Пусть дано множество отношений R ={r},

где r={t| t=(d₁, d₂,...d_n), d_iÎ D }- отношение,

t=(d₁, d₂,...d_n) – кортеж отношения,

d_iÎD_i- значение компоненты кортежа,

D_i – домен i-го атрибута,

D ={D₁, D₂,¼, D_m} – множество доменов,

A ={A₁, A₂,...A_k} - множество атрибутов,

rel(r)= (A₁, A₂,...A_n) - схема отношения,

REL (R)={rel(r)} - множество схем отношений,

множество алгебраических операторов:

S ={È, Ç, \, Ä, ù, d_B(r), p _rel(r), ><, > ^q <}, где

È - оператор объединения отношений;

Ç - оператор пересечения отношений;

\ - оператор разности отношений;

Ä - оператор прямого произведения отношений;

ù - оператор дополнения отношения;

d_B(r) - оператор выбора кортежа по условию B;

p _rel’(r) - оператор проекции отношения на новую схему rel;

>< - оператор естественного соединения отношений;

>^q< - оператор q - соединения отношений,

: - оператор деления отношений.

множество логических операторов:

Y={&, Ú, ù}, где

& - оператор конъюнкции условий и/или отношений,

Ú - оператор дизъюнкции условий и/или отношений,

ù - оператор отрицания условий и/или отношений,

множество операторов сравнения:

q={=, ¹, >, ³, <, £}.

 

 

Множество отношений R и операторов формируют реляционную алгебру

. A_p=< R, å, Y, q >.

Рассмотрим исполнение алгебраических операций над пятью отношениями r₁, r₂, r₃, r₄ и r₅. Поскольку наиболее удобно представление отношений таблицами, то исполнение операций проследим в графической форме. Имена атрибутов в таблицах обозначены прописными буквами латинского алфавита с индексами А₁, А₂, A₃, A₄, A₅ и А₆, а значения атрибутов - строчными буквами латинского алфавита с индексами {a₁, a₂, a₃, a₄, b₁, b₂, b₃, b₄, c₁, c₂, d₁, d₂, d₃} и цифрами {1, 2, 3}.

 

r1,

A1

A2

A3

r2

A1

A2

A3

r5

A1

A2

A3

A4

A5

A6

a1

b1

a2

b3

a1

b1

c2

d3

ккк

a2

b2

a1

b1

a2

b2

c2

d2

a3

b3

a2

b4

a1

b1

c3

d3

a4

b1

a1

b2

a2

b2

c2

d2

a1

b1

c1

d1

r3

A1

A4

A5

r4

A4

A5

A6

a3

b3

c3

d3

a1

c2

d3

c2

d3

a3

b3

c3

d3

a2

c1

d1

c1

d1

a4

b1

c2

d3

a3

c1

d2

c2

d2

a1

c2

d1

c3

d3

 

Пусть даны ключи отношений: r₁ – (A ₁), r₂ - (A ₂), r₃ - (A ₁, A ₅),

r₄- (A ₄, A ₅, A ₆). В шапках таблиц ключи выделены полужирным шрифтом.

Операторы d_B(r), p_rel'(r) и ùr есть унарные операторы, а операторы È(r₁, r₂), Ç(r₁, r₂), \(r₁, r₂), Ä(r₁, r₂), ><(r₁, r₂), >q<(r₁, r₂) и:(r1,r₂)} – бинарные.

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

 

Унарные операции

Оператор выбора d_B(r) позволяет извлекать из отно­шения r кортежи, удовлетворяющие условию В, и формировать новое отношение r’. Условия выбора задаются, как правило, операторами сравнения {=, ¹, >, ³, <, £} и/или логическими связками {&, Ú, ù}. Например, B=(А_i=k_di); B=(А_i¹k_di); B=(А_i>k_di); B=(А_i<k_di); B=(А_i³k_di);

B=(А_i£k_di); B=((A₁, A₂,...A_n)=k_ti); B=((A₁, A₂,...A_n)¹k_ti); B=((A₁, А₂,...A_n)>k_ti); B=((A₁, A₂,...A_n)<k_ti); B=((A₁, A₂,...A_n)³k_ti); B=((A₁, A₂,...A_n)£k_ti); B=B_i &B_j; B=B_i ÚB_j; B=ù B_j и т. п..

Результатом исполнения этой операции будет новое отношение r’, т.е.

r^’= d_B(r)={ t’| t^’ Í r; B, rel(r’)=rel(r)}Í r.

Пример: выбрать кортежи отношения r₁ по ключу А₁=а₂, т.е. r’₁={t’| B:=(A₁=a₂}, r₂ - по значению атрибута A₃=1, т.е. r’₂={t’| B:=(A₃=1}, r₅ – по значениям атрибутов {A₁=a₁, A₂=b₁, A₃=1}, т.е. r’₅={t’| B:=(A₁=a₁)&, (A₂=b₁)&(A₃=1)}. Ниже приведены отношения в результате исполнения этих операций.

 

r’1

A1

A2

A3

r’2

A1

A2

A3

r5

A1

A2

A3

A4

A5

A6

a2

b2

a2

b3

a1

b1

c2

d3

a1

b1

a1

b1

c3

d3

a1

b1

c1

d1

В нотации компьютерных языков операцию выбора запи­сывают так:

SELECT (отношение; УСЛОВИЯ).

Для данного примера это будет описано так:

r’₁=SELECT(r₁, A₁=’a₂’); r’₂=SELECT(r₂, A₃=’1’);

r’₅=SELECT(r₅; A1=’a₁’ AND A₂=’b₁’ AND A₃=’1’).

Значения атрибутов заключены в апострофы. Это озна­чает, что строка символов является значением поля записи. Данное правило относится к любым одиночным символам и строкам, представляющим значение атрибута. Это делается для того, чтобы отличить значение от имени атрибута, переменных параметров и числовых констант.

При программировании на алгоритмических языках логические связки {&,Ú,ù} замещаются операторами AND, OR, NOT соответственно.

Например, необходимо выбрать кортежи отношения r₁ по значению атрибута A₃=ù3, т.е. r’₁={t’| B:=(A₃=ù3}, r₂ - по значению атрибутов A₃=1 или A₂=b₁, т.е. r’₂={t’| B=(A₃=1ÚA₂=b₁}, r₅ – по значению атрибутов (A₁=a₁, A₂=b₁, A₃=1и A₄¹c₂), т.е. r’₅={t’| B=((A₁=a₁)&(A₂=b₁)&(A₃=1)&(A₄¹c₂)}.

Ниже приведены отношения в результате исполнения этих операций.

 

r’1

A1

A2

A3

r’2

A1

A2

A3

r5

A1

A2

A3

A4

A5

A6

a1

b1

a2

b3

a1

b1

c3

d3

a3

b3

a1

b1

a1

b1

c1

d1

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

В нотации компьютерных языков оператор выбора опи­сывают так:

r’₁=SELECT(r₁; A₃=NOT’3’); r’₂=SELECT(r₂; A₃=’1’OR A₂=’b₁’);

r’₅=SELECT(r₅; A₁=’a₁’AND A₂=’b₁’AND A₃=’1’AND A₄=NOT’c₂’).

При задании нескольких операторов выбора допускается их композиция, т. е.d_{В1В2…Вь}=.d_В1×d_В2×_…×d_Вь.

Оператор проекции p_rel(r) позволяет формировать из данного отношения r со схемой rel(r)=(A₁, A₂,..A_n) новое отношение r’ со схемой rel(r’)=(A_i, A_j,.. A_k), где 1£i, j,k£n, путем удаления и (или) переупорядочения атрибутов.

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

r’=p_rel(r)={ t’| |rel(r’)|£|rel(r)|}.

Следует обратить внимание, что число атрибутов схемы формируемого отношения меньше или равно числу атрибутов схемы исходного отношения, т.е. |rel(r’)|£|rel(r)|, а число кортежей формируемого отношения равно числу кортежей исходного отношения, т.е. |r’|=|r|.

Например, необходимо выбрать значения ключей отношений r₁ и r₃, т.е. rel(r’₁)= (A₁), rel(r’₃)= (A₁, A₅).

 

r’1	A1		r’3	A1	A5
	a1			a1	d3
	a2			a2	d1
	a3			a3	d2
	a4			a1	d1

При задании нескольких операторов проекции допускается их композиция, т. е. p_{rel1 rel2} … _relь (r)= p_rel(r)×p_re2(r)×…×p_re(r).

В нотации компьютерных языков операцию проекции запи­сывают так:

PROJECT(отношение, СПИСОК AТРИБУТОВ).

Для приведенных примеров имеем:r’₁=PROJECT(r₁, A₁); r’₃=PROJECT(r₃, A₁, A₅); r’₅=PROJECT(r₅, A₁, A₂, A₃).

Оператор дополнения ùr. Для формирования дополнения отношения необходимо найти множество всех кортежей со схемой заданного отношения rel(r) на области определения D, т. е. найти размещение всех значений домена отношения | D |= n на число компонент -k схемы отношения rel(r), т.е. найти

dom(r)=(n)_k=n_*(n-1)_*(n-2)_*..._*(n-k+1)

и удалить из этого множества кортежи исходного отношения r.

Множество таких кортежей очень большое. Если хотя бы один атрибут отношения счетный, но не конечный, то |dom(r)|=¥.

Например, для r₃ имеем D₁={a₁, a₂, a₃}, D₄={c₁, c₂}, D₅={d₁, d₂, d₃}, т. е. n=|D|=|D₁ÈD₄ÈD₅|=8 и к=3. Следовательно, число кортежей дополнения равно |dom(r₃)|=(8)₃=8_*7_*6_*5_*4=6720.

Если значения атрибутов находятся в пределах своих доменов, то |dom(r)|=|D₁|_*|D₂|_*..._*|D_m|. Например, для r₃ имеем |dom(r)|=3_*2_*3=18, а |ùr|=14.

Чтобы получить кортежи отношенияùr₃ следует из множества кортежей dom(r₃) удалить кортежи r₃, т. е. ùr₃= dom(r₃)\ r₃).

Ниже двумя таблицами представлены dom(r₃) и ùr_3..

 

dom(r3)	A1	A4	A5		ùr3	A1	A4	A5
	a1	c1	d1			a1	c1	d1
	a1	c1	d2			a1	c1	d2
	a1	c1	d3			a1	c1	d3
	a1	c2	d1			a1	c2	d2
	a1	c2	d2			a2	c1	d2
	a1	c2	d3			a2	c1	d3
	a2	c1	d1			a2	c2	d1
	a2	c1	d2			a2	c2	d2
	a2	c1	d3			a2	c2	d3
	a2	c2	d1			a3	c1	d1
	a2	c2	d2			a3	c1	d3
	a2	c2	d3			a3	c2	d1
	a3	c1	d1			a3	c2	d2
	a3	c1	d2			a3	c2	d3
	a3	c1	d3
	a3	c2	d1
	a3	c2	d2
	a3	c2	d3

Бинарные операции

Все множество бинарных операторов удобно разбить на два подмножества: основные и дополнительные. Основные - это объединения, разности и прямого произведения, а дополнительные - пересечения, соединения и деления.

Оператор объединения È(r₁, r₂) двух отношений, имеющих оди­наковые схемы, формирует новое отношение r’,

r1Èr2	A1	A2	A3		объединяя все кортежи первого и второго отношений. При этом одинаковые кортежи отно­шений по правилу идемпотентности "сливаются” в один кортеж. Например, r’={t’| t’=t1Î r1 или t’=t2Î r2, rel(r’)=rel(r1)=rel(r2)}. В нотации компьютерных языков это: r’= UNION(r1, r2).
	a1	b1
	a2	b2
	a3	b3
	a4	b1
	a2	b3
	a2	b4
	a1	b2

Оператор прямого произведения Ä(r₁, r₂) формирует из двух отношений арности n₁ и n₂ новое отношение r’ ар­ности (n₁+n₂).

При этом первые n1 компонентов кортежа отношения r’ образованы отношением r1, а последние n2 - отношением r2. В результате формируется множество кортежей: r`={t`=<t1,t2>| t1Îr1; t2Îr2; rel(r’)=<rel(r1)rel(r2)>}. В нотации компьютерных языков это: PRODUCT(r1, r2). Для таблицы r’ число строк равно произведению числа строк таблиц r1 и r2, т.е. |r’|=|r1|*|r2|, а число столбцов равно сумме числа столбцов таблиц r1 и r2, т.е. rel(r’)=<rel(r1)rel(r2)>. Справа приведена таблица для (r1Är4).		r1Är4	A1	A2	A3	A4	A5	A6
	a1	b1		c2	d3
	a1	b1		c1	d1
	a1	b1		c2	d2
	a1	b1		c3	d3
	a2	b2		c2	d3
	a2	b2		c1	d1
	a2	b2		c2	d2
	a2	b2		c3	d3
	a3	b3		c2	d3
	a3	b3		c1	d1
	a3	b3		c2	d2
	a3	b3		c3	d3
	a4	b1		c2	d3
	a4	b1		c1	d1
	a4	b1		c2	d2
	a4	b1		c3	d3

Оператор разности \(r₁, r₂) двух отношений, имеющих одинаковые схемы, формирует новое отношение r’, выбирая из первого отно­шения только те кортежи, которых нет во втором отношении.

В результате выполнения этой операции формируется множество кортежей по правилу: r’={t’| t = t₁Î r₁ и t₁Ïr₂, rel(r₁)=rel(r₂)}.

 

В нотации компьютерных языков это: MINUS(r1, r2) или DIFFERENCE(r1, r2).	r1\ r2	A1	A2	A3
	a2	b2
	a3	b3
	a4	b1

Оператор пересечения Ç(r₁, r₂), имеющих одинаковые схемы, формирует новое отношение из кортежей первого и второго отношений, имеющих одинаковые значения всех одноименных атрибутов.

В результате выполнения этой операции:

r`= {t’| t’=t₁Îr₁ и t’=t₂Îr₂ , rel(r₁)=rel(r₂)}.

В нотации компьютерных языков оператор пересечения записывают так:

r’=INTERSECT(r₁, r₂).

Операция пересечения может быть реализована оператором разности: r₁Çr₂=r₁\(r₁\r₂).

В таблице приведены результаты операции пересечения (r1Ç r2).		r1Ç r2	A1	A2	A3
	a1	b1	c1

Оператор естественного соединения ><(r₁, r₂) фqqормирует из r₁ и r₂, имеющих один или несколько одинаковых имен атрибутов, новое отношение r’, схема которого есть объеди­нение схем двух отношений, а кортежи формируются из кортежей первого отношения путем присоединения кортежей второго отно­шения при одинаковых значениях одноименных атрибутов.

В результате выполнения этой операции:

r’={t’=<t₁t₂>| t₁Î r₁; t₂ Î r₂; rel(r₁)Çrel(r₂)¹Æ; rel(r’)=rel(r₁)È rel(r₂)}.

В нотации компьютерных языков оператор соединения есть:

JOIN (r₁, r₂).

В таблицах приведены результаты r₁><r₂ и r₃><r₄.

r1><r2	A1	A2	A3	A4	A5		r3><r4	A1	A4	A5	A6
	a1	b1		c2	d3			a1	c2	d3
	a1	b1		c2	d1			a2	c1	d1
	a2	b2		c1	d1
	a3	b3		c1	d2

Оператор q-соединения >^q<(r₁, r₂) формирует из r₁ и r₂ арности n₁ и n₂ новое отношение r’ арности (n₁+n₂) при выполнении некоторого условия В=(d_1iqd_2j), где q={=, ¹, >, ³, <, £}; первые n₁ компо­нентов кортежа образованы кортежами, принадлежа­щими отношению r₁, а последние - кортежами, принадлежащими отношению r₂.

В результате исполнения этой операции:

r’={t`=<t₁t₂>| <t₁t₂>Î(r₁Är₂), В=(d_1iqd_2j), rel(r’)=<rel(r₁), rel(r₂)>}.

В нотации компьютерных языков это:

JOIN (r₁, r₂, УСЛОВИЕ).

r’

A1

A2

A3

A4

A5

A6

a1

b1

c1

d1

Например, q-соединение r1 и r4 при условии A6>A3, r’=JOIN (r1, r4, A6>A3). Результаты этой операции представлены таблицей.

a1

b1

c2

d2

a1

b1

c3

d3

a3

b3

c2

d2

Частным случаем q-соединения является эквисоединение, когда формируется новая таблица, для которой различные атрибуты различных отношений имеют одинаковое значение. Например, <имя_порт_приписки>=<имя_порт_назначения>.

Пример: r’=JOIN (r₁, r₄, r₁.A₃=r₄.A₆).

r’	r1.A1	r1.A2	r1.A3	r2.A4	r2.A5	r2.A6
	a1	b1		c2	d3
	a3	b3		c1	d1
	a3	b3		c

⇐ Предыдущая19202122232425262728Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: