Что называется разностью отношений r1 и r2

Презентация была опубликована 8 лет назад пользователемВалерий Савельев

Похожие презентации

Презентация на тему: » 1 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность.» — Транскрипт:

1 1 Свойства отношений R 1 содержится в R 2 (R 1 R 2 ), если любая пара (x, y), которая принадлежит отношению R 1 также принадлежит и отношению R 2 Рефлексивность xM (xRx) Антирефлексивность xM ¬(xRx)

2 2 Рефлексивность отношений Обозначим через Ix отношение на множестве X, состоящее из пар вида (a, a), где a X: Ix = <(a, a)| a X>. Отношение Ix обычно называют диагональю множества X или отношением тождества на X. Очевидно, что отношение R на множестве X рефлексивно, если диагональ Ix является подмножеством множества a: Ix R. Отношение антирефлексивно, если диагональ Ix и отношение R не имеют ни одного общего элемента: Ix R = Ø.

6 6 Нетранзитивное отношение Отношение R, определенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz. Пример нетранзитивного отношения: «x отец y» Нетранзитивным является отношение » «. Пусть x=2, y=3, z=2, тогда справедливо x y и y z, но x=z, т.е. (x, z) R.

8 8 Свойства бинарных отношений Полнота (x, y) X либо xRy либо yRx, либо и то и другое одновременно – полносвязное или связное отношение Ацикличность Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы ). n x 1 Rx 2 x 2 Rx 3 x 3 Rx 4 … x n-1 Rx n но не наоборот.

9 Транзитивное замыкание Для произвольного отношения A можно найти минимальное транзитивное отношение a такое, что ab. Минимальность отношения понимается в том смысле, что для любого транзитивного отношения g из a g следует b g. Таким отношением является транзитивное замыкание отношения a. Если X это множество аэропортов, а xRy эквивалентно «существует рейс из x в y», и транзитивное замыкание R равно P, то xPy эквивалентно «можно долететь из x в y самолётом» (хотя иногда придётся лететь с пересадками).

10 Транзитивное замыкание Транзитивным замыканием отношения R называется бинарное отношение R такое, что x R y тогда и только тогда, когда существует такая цепочка элементов из X: z 0 = x, z 1, z 2. z n = y, что между соседями в этой цепочке выполнено отношение R: z 0 Rz 1, z 1 R z 2. z n-1 Rz n.

12 Отношения эквивалентности (подобия, равносильности) Отношение R на множестве A 2 называется отношением эквивалентности, если оно обладает следующими свойствами: рефлексивность симметричность транзитивность Обозначается =,,

13 Отношение эквивалентности Условия 1-3 в таких обозначениях выглядят более естественно: x=x для всех x A (рефлексивность) Если x=y, то y=x (симметричность) Если x=y и y=z, то x=z (транзитивность)

14 Примеры отношение тождества I X = <(a, a)|a X>на непустом множестве X; отношение параллельности на множестве прямых плоскости; отношение подобия на множестве фигур плоскости; отношение равносильности на множестве уравнений; отношение «иметь одинаковые остатки при делении на фиксированное натуральное число m» на множестве целых чисел. Это отношение в математике называют отношением сравнимости по модулю m и обозначают ab (mod m); отношение «принадлежать одному виду» на множестве животных; отношение «быть родственниками» на множестве людей; отношение «быть одного роста» на множестве людей; отношение «жить в одном доме» на множестве людей.

15 Классы эквивалентности Система непустых подмножеств множества M называется разбиением этого множества, если M = M 1 M 2 … и при ij M i M j =Ø. Сами множества M 1, M 2, … называются при этом классами данного разбиения.

18 Пример 2 А и B равны по модулю n, если их остатки при делении на n равны. Например по модулю 5 равны 2, 7, 12 … [0] = <0, n, 2n, …>[1] = <1, n+1, 2n+1, …>… [n-1] =

19 Класс эквивалентности Классом эквивалентности C(a) элемента a называется подмножество элементов, эквивалентных a. Из вышеприведённого определения немедленно следует, что, если и bC(a), то C(a) = C(b). Теорема: отношение эквивалентности, заданное между элементами базового множества х, определяет разбиение множества х на непересекающиеся классы эквивалентности базового множества (в каждый из классов входят взаимно эквивалентные отношения).

20 Фактор-множество Получающееся при этом множество классов называется фактор- множеством .или X / ˜. Для класса эквивалентности элемента используются следующие обозначения: : [a], a / ˜, a.

Источник

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

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

Пусть заданы два отношения где r1и r2 – соответственно кортежи отношений R1 и R2, то объединение

Здесь r – кортеж нового отношения, Ú – операция логического сложения «ИЛИ».

Пример применения операции объединения приведен на рис. 2.7.

Рис. 2.7. Пример применения операции объединения

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

Пересечением отношений называется отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям. R1 и R2:

здесь ^ – операция логического умножения (логическое «И»).

В отношении R4 содержатся перечень деталей, которые выпускаются одновременно на двух участках цеха (рис. 2.8).

Рис. 2.8. Пример применения операции пересечения

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

Отношение R5 содержит перечень деталей, изготавливаемых только на участке 1, отношение R6 содержит перечень деталей, изготавливаемых только на участке 2 (рис. 2.9).

Рис. 2.9. Пример применения операции разности отношений

Следует отметить, что первые две операции, объединение и пересечение, являются коммутативными операциями, то есть результат операции не зависит от порядка аргументов в операции. Операция же разности является принципиально несимметричной операцией, то есть результат операции будет различным для разного порядка аргументов, что и видно из сравнения отношений R5 и R6.

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

Для демонстрации возможностей трех первых операций реляционной алгебры рассмотрим еще один пример – уже из другой предметной области. Исходными являются три отношения R1, R2 и R3. Все они имеют эквивалентные схемы.

Рассмотрим ситуацию поступления в высшие учебные заведения, которая была характерна для периода, когда были разрешены так называемые репетиционные вступительные экзамены, которые сдавались раньше основных вступительных экзаменов в вуз. Отношение R1 содержит список абитуриентов, сдававших репетиционные экзамены. Отношение R2 содержит список абитуриентов, сдававших экзамены на общих условиях. И наконец, отношение R3 содержит список абитуриентов, принятых в институт. Будем считать, что при неудачной сдаче репетиционных экзаменов абитуриент мог делать вторую попытку и сдавать экзамены в общем потоке, поэтому некоторые абитуриенты могут присутствовать как в первом, так и во втором отношении.

Ответим на следующие вопросы:

1. Список абитуриентов, которые поступали два раза и не поступили в вуз.

2. Список абитуриентов, которые поступили в вуз с первого раза, то есть они сдавали экзамены только один раз и сдали их так хорошо, что сразу были зачислены в вуз.

3. Список абитуриентов, которые поступили в вуз только со второго раза.

Прежде всего, это те абитуриенты, которые присутствуют в отношениях R1 и R2, потому что они поступали два раза, и присутствуют в отношении R3, потому что они поступили.

4. Список абитуриентов, которые поступали только один раз и не поступили.

Это, прежде всего, те абитуриенты, которые присутствуют в R1 и не присутствуют в R2, и те, кто присутствуют в R2 и не присутствуют в R1. И, разумеется, никто из них не присутствует в R3.

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

Операции объединения, пересечения и разности применимы только к отношениям с эквивалентными схемами.

Сцеплением, или конкатенациейкортежей и называется кортеж, полученный добавлением значений второго в конец первого. Сцепление кортежей с и q обозначается как (с, q).

Здесь n – число элементов в первом кортеже с, m – число элементов во втором кортеже q.

Источник

Свойства бинарных отношений

1. Рефлексивность. Отношение R называется рефлексивным, если (х, х)ÎR для любого хÎA. Примеры рефлексивных отношений: отношения «³», «£» на множестве R.

2. Антирефлексивность. Отношение R называется антирефлексивным, если (х, х)ÏR для любого хÎA. Примеры антирефлексивных отношений: отношения » » на множестве R.

3. Симметричность. Отношение R называется симметричным, если для любых x, yÎA из того, что (x, y)ÎR следует (y, x)ÎR и обратно. Примеры симметричных отношений: отношения «=» и «¹».

Если отношение R симметрично, то для любого хÎA

4. Антисимметричность. Отношение R называется антисимметричным, если для любых x и y из A из одновременного выполнения условий (x, y)ÎR и (y, x)ÎR следует, что x = y. Пример антисимметричного отношения. Пусть А – множество людей в данной очереди. Отношение R – «не стоять за кем-то в очереди» будет антисимметричным.

Пусть х = ВАСЯ, а y = ИВАНОВ. Тот факт, что (x, y)ÎR означает, что «ВАСЯ не стоит в очереди за ИВАНОВЫМ», (y, x)ÎR – «ИВАНОВ не стоит за ВАСЕЙ». Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y.

Отношение «³» также антисимметрично: если x ³ y и y ³ x, то x = y.

Эквивалентное определение асимметричности: из двух отношений (x, y) Î R и (y, x)ÎR одно не выполняется.

Примеры. Если R – «³», то R –1 – » s – «=», R a – «>».

6. Транзитивность. Отношение R транзитивно, если для любых x, y, zÎA из того, что (x, y)ÎR и (y, z)ÎR следует (x, z)ÎR.

Свойства транзитивного отношения:

б) для любого хÎA из yÎG_R(x) следует, что G_R(y) Í G_R(x).

Не транзитивным является отношение «¹». Пусть x = 2, y = 3, z = 2, тогда справедливо x ¹ y и y ¹ z, но x = z, т.е. (x, z)ÏR.

Отношение R₁ называется транзитивным относительно отношения R₂, если:

а) из (x, y)Î R₁ и (y, x)Î R₂ следует, что (x, z)Î R₁;

б) из (x, y)Î R₂ и (y, x)Î R₁ следует, что (x, z)Î R₁.

7. Негатранзитивность. Отношение R называется негатранзитивным, если`R транзитивно.

8. Полнота. Отношение R полно, если для любых x, yÎА либо (x, y)ÎR, либо (y, x)ÎR, либо оба отношения выполняются одновременно.

Свойства полных отношений:

а) G_R(x) È H_R(x) = А для любого хÎA;

б) полное отношение рефлексивно.

9. Слабая полнота. Отношение R называется слабо полным, если для любых х ¹ y из А или (x, y)ÎR, или (y, x)ÎR.

Пример слабо полного отношения. Пусть А – множество предприятий, «неблагополучных» в смысле своего бюджета. Отношение R «быть должным» является слабо полным, так как каждое из этих предприятий или кому-либо должно, или ему кто-то должен, но быть должным самому себе нельзя и (x, x)ÏR.

Источник

Реляционная модель данных

Операции над отношениями. Реляционная алгебра

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

.

Здесь r — кортеж нового отношения, — операция логического сложения «ИЛИ».

здесь — операция логического умножения (логическое «И»).

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

Отношение R₅ содержит перечень деталей, изготавливаемых только на участке 1, отношение R₆ содержит перечень деталей, изготавливаемых только на участке 2.

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

Рассмотрим ситуацию поступления в высшие учебные заведения, которая была характерна для периода, когда были разрешены так называемые репетиционные вступительные экзамены, которые сдавались раньше основных вступительных экзаменов в вуз. Отношение R₁ содержит список абитуриентов, сдававших репетиционные экзамены. Отношение R₂ содержит список абитуриентов, сдававших экзамены на общих условиях. И наконец, отношение R₃ содержит список абитуриентов, принятых в институт. Будем считать, что при неудачной сдаче репетиционных экзаменов абитуриент мог делать вторую попытку и сдавать экзамены в общем потоке, поэтому некоторые абитуриенты могут присутствовать как в первом, так и во втором отношении.

Ответим на следующие вопросы:

Операции объединения, пересечения и разности применимы только к отношениям с эквивалентными схемами.

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

Расширенным декартовым произведением отношения R₁ степени n со схемой

и отношения R₂ степени m со схемой

называется отношение R₃ степени n+m со схемой

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

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

Источник