Лекция 20. Отношения на множестве
1. Отношения на множестве. Бинарные отношения.
2. Свойства отношений
§10. ОТНОШЕНИЯ НА МНОЖЕСТВЕ
В математике изучают не только связи между элементами двух множеств, т.е. соответствия, но и связи между элементами одного множества. Называют их отношениями.
Отношения многообразны. Между понятиями - это отношения рода и вида, части и целого; между предложениями - отношения следования и равносильности; между числами - «больше», «меньше», «равно», «больше на...», «меньше на...», «следует» и др.
Если рассматривают отношения между двумя элементами, то их называют бинарными; отношения между тремя элементами - тернарными; отношения между п элементами - n -арными. Все названные выше отношения являются бинарными. Примером тернарного отношения может служить отношение между точками прямой - «точка х лежит между точками у и 2».
Изучение отношений между объектами важно для познания как самих объектов, так и для познания реального мира в целом. В нашем курсе мы будем рассматривать в основном бинарные отношения, но чтобы увидеть общность методических подходов к изучению в начальном курсе математики конкретных отношений, понять важнейшие математические идеи, связанные с отношениями, учителю надо знать, какова математическая сущность любого отношения, какими свойствами они могут обладать, какие основные виды отношений изучает математика.
Чтобы определить общее понятие бинарного отношения на множестве, поступим так же, как и в случае с соответствиями, т.е. рассмотрим сначала конкретный пример. Пусть на множестве X = {2, 4, 6, 8} задано отношение «меньше». Это означает, что для любых двух чисел из множества X можно сказать, какое из них меньше: 2 < 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения Х х Х , поэтому об отношении «меньше», заданном на множестве X , можно сказать, что оно является подмножеством множества Х х X .
Вообще бинарные отношения на множестве X определяют следующим способом:
Определение. Бинарным отношением на множестве X называется всякое подмножество декартова произведения Х х Х.
Так как в дальнейшем мы будем рассматривать только бинарные отношения, то слово «бинарные», как правило, будем опускать.
Условимся отношения обозначать буквами R, S, T, P и др.
Если R - отношения на множестве X , то, согласно определению, R с X х X . С другой стороны, если задано некоторое подмножество множества X х X , то оно определяет на множестве X некоторое отношение R .
Утверждение о том, что элементы х и у находятся в отношении R , можно записывать так: (х, у ) € R или хRу . Последняя запись читается: «Элемент х находится в отношении R с элементом у ».
Отношения задают так же, как соответствия. Отношение можно задать, перечислив пары элементов множества X , находящиеся в этом отношении. Формы представления таких пар могут быть различными - они аналогичны формам задания соответствий. Отличия касаются задания отношений при помощи графа.
Построим, например, граф отношений «меньше», заданного на множестве X
= {2, 4, 6, 8}. Для этого элементы множества X
изобразим точками (их называют вершинами графа), а отношение «меньше» - стрелкой (рис. 93).
На том же множестве X можно рассмотреть другое отношение - «кратно». Граф этого отношения будет в каждой вершине иметь петлю (стрелку, начало и конец которой совпадают), так как каждое число кратно самому себе (рис. 94). Отношение можно задать при помощи предложения с двумя переменными. Так, например, заданы рассмотренные выше отношения «меньше» и «кратно», причем использована краткая форма предложений «число x меньше числа у» и «число х кратно числу у». Некоторые такие предложения можно записывать, используя символы. Например, отношения «меньше» и «кратно» можно было задать в таком виде: «x < у», «х: у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или x - у = 3).
Для отношения R , заданного на множестве X, всегда можно задать отношение R -1 , ему обратное, - оно определяется так же, как соответствие, обратное данному. Например, если R - отношение «х меньше y », то обратным ему будет отношение «у больше x ».
Понятием отношения, обратного данному, часто пользуются при начальном обучении математике. Например, чтобы предупредить ошибку в выборе действия, с помощью которого решается задача: «У Пети 7 карандашей, что на 2 меньше, чем у Бори. Сколько карандашей у Бори?» - ее переформулируют: «У Пети 7 карандашей, а у Бори на 2 больше. Сколько карандашей у Бори?» Видим, что переформулировка свелась к замене отношения «меньше на 2» обратным ему отношением «больше на 2».
Лекция 3.
п.3. Отношения на множествах. Свойства бинарных отношений.
3.1. Бинарные отношения .
Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).
В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A ´B ) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S ´K можно выделить большое подмножество упорядоченных пар (s , k ), обладающих свойством: студент s слушает курс k . Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.
Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.
Определение 3.1. Бинарным (или двухместным ) отношением r между множествами A и B называется произвольное подмножество A ´B , т. е.
В частности, если A= B (то есть rÍA 2), то говорят, что r есть отношение на множестве A.
Элементы a и b называются компонентами (или координатами ) отношения r.
Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит : r, t, j, s, w и т. д.
Определение 3.2. Областью определения D r={a | $ b , что a rb } (левая часть). Областью значений бинарного отношения r называется множество R r={b | $ a , что a rb } (правая часть).
Пример 3. 1. Пусть даны два множества A ={1; 3; 5; 7} и B ={2; 4; 6}. Отношение зададим следующим образом t={(x ; y )ÎA ´B | x+ y =9}. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t={(3; 6), (5; 4), (7;2)}. В данном примере D t={3; 5; 7} и R t= B ={2; 4; 6}.
Пример 3. 2. Отношение равенства на множестве действительных чисел есть множество r={(x ; y ) | x и y – действительные числа и x равно y }. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, D r= R r.
Пример 3. 3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j={(x ; y )ÎA ´B | y – цена x } – отношение множеств A и B .
Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t={(x ; y )ÎA ´B | x+ y =9}, а потом записано в виде t={(3; 6), (5;4), (7;2)}. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.
Способы задания отношений:
1) с помощью подходящего предиката;
2) множество упорядоченных пар;
3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом , точки же, изображающие элементы множеств, принято называть вершинами графа .
4) в виде матрицы: пусть A ={a 1, a 2, …, an } и B ={b 1, b 2, …, bm }, r – отношение на A ´B . Матричным представлением r называется матрица M =[mij ] размера n ´m , определенная соотношениями
.
Кстати, матричное представление является представлением отношения в компьютере.
Пример 3. 4. Пусть даны два множества A ={1; 3; 5; 7}и B ={2; 4; 6}. Отношение задано следующим образом t={(x ; y ) | x+ y =9}. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.
Решение. 1) t={(3; 6), (5; 4), (7; 2)} - есть задание отношения как множества упорядоченных пар;
2) соответствующий ориентированный граф показан на рисунке.
https://pandia.ru/text/78/250/images/image004_92.gif" width="125" height="117">. ,
Пример 3. 5 . Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M :
,
где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.
Рассмотрим информационный обмен между устройствами mi и mj , которые находятся в отношении r, если из устройства mi поступает информация в устройство mj .
Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:
Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:
Матричное представление этого бинарного отношения имеет вид:
. ,
Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.
Введем обобщенное понятие отношения.
Определение 3.3. n-местное (n -арное ) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей )
rÍA 1´…´An ={(a 1, …, an )| a 1ÎA 1Ù … Ùan ÎAn }
Многоместные отношения удобно задавать с помощью реляционных таблиц . Такое задание соответствует перечислению множества n -к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных . Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.
Слово «реляционная » происходит от латинского слова relation , которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).
Определение 3.4. Пусть rÍA ´B есть отношение на A ´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A ´B , которое определяется следующим образом:
r-1={(b , a ) | (a , b )Îr}.
Определение 3.5. Пусть r ÍA ´B есть отношение на A ´B, а s ÍB ´C – отношение на B ´C. Композицией отношений s и r называется отношение t ÍA ´C ,которое определяется следующим образом:
t=s◦r= {(a , c )| $ b Î B, что (a , b )Îr и (b , c )Îs}.
Пример 3. 6 . Пусть , и C ={, !, d, à}. И пусть отношение r на A ´B и отношение s на B ´C заданы в виде:
r={(1, x ), (1, y ), (3, x )};
s={(x ,), (x , !), (y , d), (y , à)}.
Найти r-1 и s◦r, r◦s.
Решение. 1) По определению r-1={(x , 1), (y , 1), (x , 3)};
2) Используя определение композиции двух отношений, получаем
s◦r={(1,), (1, !), (1, d), (1, à), (3,), (3, !)},
поскольку из (1, x )Îr и (x ,)Îs следует (1,)Îs◦r;
из (1, x )Îr и (x , !)Îs следует (1, !)Îs◦r;
из (1, y )Îr и (y , d)Îs следует (1, d)Îs◦r;
из (3, x )Îr и (x , !)Îs следует (3, !)Îs◦r.
Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:
2) 
;
3) 
- ассоциативность композиции.
Доказательство. Свойство 1 очевидно.
Докажем свойство 2. Для доказательства второго свойства покажем, что множества, записанные в левой и правой частях равенства, состоят из одних и тех же элементов. Пусть (a ; b ) Î (s◦r)-1 Û (b ; a ) Î s◦r Û $ c такое, что (b ; c ) Î r и (c ; a ) Î s Û $ c такое, что (c ; b ) Î r-1 и (a ; c ) Î s-1 Û (a ; b ) Î r -1◦s -1.
Свойство 3 доказать самостоятельно.
3.2. Свойства бинарных отношений .
Рассмотрим специальные свойства бинарных отношений на множестве A .
Свойства бинарных отношений.
1. Отношение r на A ´A называется рефлексивным , если (a ,a ) принадлежит r для всех a из A .
2. Отношение r называется антирефлексивным , если из (a ,b )Îr следует a ¹b .
3. Отношение r симметрично , если для a и b , принадлежащих A , из (a ,b )Îr следует, что (b ,a )Îr.
4. Отношение r называется антисимметричным , если для a и b из A , из принадлежности (a ,b ) и (b ,a ) отношению r следует, что a =b .
5. Отношение r транзитивно , если для a , b и c из A из того, что (a ,b )Îr и (b ,c )Îr, следует, что (a ,c )Îr.
Пример 3. 7. Пусть A ={1; 2; 3; 4; 5; 6}. На этом множестве задано отношение rÍA 2, которое имеет вид: r={(1, 1), (2, 2), (3, 3), (4; 4), (5; 5), (6; 6), (1; 2), (1; 4), (2; 1), (2;4), (3;5), (5; 3), (4; 1), (4; 2)}. Какими свойствами обладает данное отношение?
Решение. 1) Это отношение рефлексивно, так как для каждого a ÎA , (a ; a )Îr.
2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.
3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:
(a , b )Îr | (b , a ) | (b , a )Îr? |
|
4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.
5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.
(a , b )Îr | (b , c )Îr | (a , c ) | (a , c )Îr? |
|
Как по матрице представления
определить свойства бинарного отношения
1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.
.
2. Антирефлексивность: на главной диагонали все нули.
3. Симметричность: если .
4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.
. Отношение равенства на множестве целых чисел есть отношение эквивалентности.Пример 3. 9 . Отношение «одного роста» есть отношение эквивалентности на множестве людей X .
Пример 3. 1 0 . Пусть ¢ - множество целых чисел. Назовем два числа x и y из ¢ сравнимыми по модулю m (m Î¥) и запишем , если равны остатки этих чисел от деления их на m , т. е. разность (x -y ) делится на m .
Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:
это отношение рефлексивно, т. к. для "x ΢ имеем x -x =0, и, следовательно, оно делится на m ;
это отношение симметрично, т. к. если (x -y ) делится на m , то и (y -x ) тоже делится на m ;
это отношение транзитивно, т. к. если (x
-y
) делится на m
, то для некоторого целого t
1 имеем https://pandia.ru/text/78/250/images/image025_23.gif" width="73" height="24 src=">, отсюда 
, т. е. (x
-z
) делится на m
.
Определение 3.7. Отношение r на A есть отношение частичного порядка , если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.
Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.
Пример 3. 11 . Отношение x £y на множестве действительных чисел есть отношение частичного порядка. ,
Пример 3. 1 2 . Во множестве подмножеств некоторого универсального множества U отношение A ÍB есть отношение частичного порядка.
Пример 3. 1 3 . Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.
Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта .
Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.
Отношение предпочтения P , которое можно определить как «aPb , a , b ÎA Û объект a не менее предпочтителен, чем объект b » является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a , то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.
Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование , т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.
Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.
relatio - «отношение», «зависимость», «связь»).Энциклопедичный YouTube
-
1 / 5
Отношение R состоит из заголовка (схемы ) и тела . Заголовок представляет собой множество атрибутов (именованных вхождений домена в заголовок отношения), а тело - множество кортежей , соответствующих заголовку . Более строго:
- Заголовок (или схема) H отношения R - конечное множество упорядоченных пар вида (A i , T i ), где A i - имя атрибута , а T i - имя типа (домена), i =1,…, n . По определению требуется, чтобы все имена атрибутов в заголовке отношения были различными (уникальными).
- Тело B отношения R - множество кортежей t . Кортеж t , соответствующий заголовку H , - множество упорядоченных триплетов (троек) вида <A i , T i , v i >, по одному такому триплету для каждого атрибута в H , где v i - допустимое значение типа (домена) T i . Так как имена атрибутов уникальны, то указание домена в кортеже обычно излишне. Поэтому кортеж t , соответствующий заголовку H , нередко определяют как множество пар (A i , v i ).
Количество кортежей называют кардинальным числом отношения (кардинальностью ), или мощностью отношения.
Количество атрибутов называют степенью , или «арностью » отношения; отношение с одним атрибутом называется унарным, с двумя - бинарным и т.д., с n атрибутами - n -арным. С точки зрения теории вполне корректным является и отношение с нулевым количеством атрибутов, которое либо не содержит кортежей, либо содержит единственный кортеж без компонент (пустой кортеж) .
Основные свойства отношения:
- В отношении нет двух одинаковых элементов (кортежей).
- Порядок кортежей в отношении не определён.
- Порядок атрибутов в заголовке отношения не определён.
Подмножество атрибутов отношения, удовлетворяющее требованиям уникальности и минимальности (несократимости), называется потенциальным ключом . Поскольку все кортежи в отношении по определению уникальны, в любом отношении должен существовать по крайней мере один потенциальный ключ.
Отношения и таблицы
Отношение обычно имеет простую графическую интерпретацию в виде таблицы, столбцы которой соответствуют атрибутам, а строки - кортежам, а в «ячейках» находятся значения атрибутов в кортежах. Тем не менее, в строгой реляционной модели отношение не является таблицей , кортеж - это не строка , а атрибут - это не столбец . Термины «таблица», «строка», «столбец» могут использоваться только в неформальном контексте, при условии полного понимания, что эти более «дружественные» термины являются всего лишь приближением и не дают точного представления о сути обозначаемых понятий .
В соответствии с определением К. Дж. Дейта , таблица является прямым и верным представлением некоторого отношения, если она удовлетворяет следующим пяти условиям:
Пример
Пусть заданы следующие типы (домены):
Тогда декартово произведение T 1 × T 2 × T 3 {\displaystyle T_{1}\times T_{2}\times T_{3}} состоит из 18 кортежей, где каждый кортеж содержит три значения: первое - одна из фамилий, второе - учебная дисциплина, а третье - оценка.
Пусть отношение R имеет заголовок H : { (Фамилия, T 1), (Дисциплина, T 2), (Оценка, T 3)}.
Тогда тело отношения R может моделировать реальную ситуацию и содержать пять кортежей, которые соответствуют результатам сессии (Петров экзамен по Физике не сдавал). Отобразим отношение в виде таблицы:
Операции над отношениями
Любая операция, результатом которой является отношение , подпадает под понятие реляционной операции и может использоваться в реляционной теории и практике. Ниже приведён список из восьми операций, изначально предложенных создателем реляционной модели Эдгаром Коддом . Все операции из списка, кроме деления, по-прежнему широко востребованы, однако список не является исчерпывающим, то есть по факту используется гораздо большее число реляционных операций.
- Объединение - тело отношения-результата является объединением тел отношений-операндов; схема не изменяется.
- Пересечение - тело отношения-результата является пересечением тел отношений-операндов; схема не изменяется.
- Вычитание - тело отношения-результата получено вычитанием тел отношений-операндов; схема не изменяется.
- Проекция - схема отношения-результата является подмножеством схемы отношения-операнда; тело отношения-результата является нестрогим подмножеством тела отношения-операнда вследствие возможного удаления кортежей-дубликатов.
- Декартово произведение - тело отношения-результата является декартовым произведением тел отношений-операндов; схема результата является конкатенацией схем операндов.
- Выборка - тело отношения-результата является подмножеством тела отношения-операнда: отбираются лишь те кортежи, которые удовлетворяют заданному предикату (условию выборки); схема не изменяется.
- Соединение - выборка над декартовым произведением.
- Деление - делитель является унарным отношением, частное - совпадающие части кортежей делимого, перед которыми стоит делитель.
Примечания
Литература
- Когаловский М.Р. Энциклопедия технологий баз данных. - М. : Финансы и статистика, 2002. - 800 с. - ISBN 5-279-02276-4 .
- Кузнецов С. Д. Основы баз данных. - 2-е изд. - М. : Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007. - 484 с. -
Способы задания бинарного отношения
Определение бинарного отношения
Бинарные отношения
Пусть среди трех людей: Андрей (А), Василий (В) и Сергей (С) двое знакомы друг с другом (Андрей и Василий) и знают третьего – Сергея, но Сергей их не знает. Как описать отношения между этими людьми?
Имеем исходное множество Х = {А, В, С}. Далее из элементов множества Х составим упорядоченные пары:
(А, В), (В, А), (А, С), (В, С). Это множество пар и описывает связи между элементами множества X. Кроме того, множество этих пар есть подмножество декартова произведения X ´ X.Определение. На множестве X задано бинарное отношение R, если задано подмножество декартова произведения X ´ X (т. е. R Ì X ´ X).
Пример 1 . Пусть X = {1, 2, 3, 4}. Зададим на X следующие отношения:
Т = {(х, у) | х, у Î Х; х = у} – отношение равенства;
Р = {(х, у) | х, у Î Х; х = у - 1} – отношение
предшествования;
Q = {(х, у) | х, у Î Х; х делится на у} – отношение
делимости.
Все эти отношения заданы с помощью характеристического свойства. Перечислим элементы этих отношений для заданного множества X = {1,2,3,4}:
Т = {(1,1), (2,2), (3,3), (4,4)};
P = {(1,2), (2,3), (3,4) };
Q = {(4,4), (4,2), (4,1), (3,3), (3,1), (2,2), (2,1), (1,1)}.
Тот факт, что пара (х, у) принадлежит данному отношению R, будем записывать: (х, у) Î R или xRy. Например, для отношения Q запись 4Q2 означает, что 4 делится на 2 нацело, т. е. (4,2) Î Q.
Областью определения D r бинарного отношения R называется множество D R = {x | (х, у) Î R}.
Областью значений Е R бинарного отношения R называется множество Е R = {у| (х, у) Î R}.
В примере для отношения Р областью определения является множество D R = {1,2,3}, а областью значений является множество Е R = {2,3,4}.
Бинарное отношение можно задать, указав характеристическое свойство или перечислив все его элементы. Существуют и более наглядные способы задания бинарного отношения: график отношения, схема отношения, граф отношения, матрица отношения.
График отношения изображается в декартовой системе координат: на горизонтальной оси отмечается область определения, на вертикальной - область значений отношения. Элементу отношения (х, у) соответствует точка плоскости с этими координатами.
Рис. 1.8. График отношения Q (а) и схема отношения Q (б)
Схема отношения изображается с помощью двух вертикальных прямых, левая из которых соответствует области определения отношения, а правая – множеству значений отношения. Если элемент (х, у) принадлежит отношению R, то соответствующие точки из D R и Е R соединяются прямой.
Граф отношения R Ì X ´ X строится следующим образом. На плоскости в произвольном порядке изображаются точки - элементы множества X. Пара точек х и у соединяется дугой (линией со стрелкой) тогда и только тогда, когда пара (х, у) принадлежит отношению R.
Матрица отношения R Ì X ´ X – это квадратная таблица, каждая строка и столбец которой соответствует некоторому элементу множества X. На пересечении строки х и столбца у ставится 1, если пара (х, у) Î R; все остальные элементы матрицы заполняются нулями. Элементы матрицы нумеруются двумя индексами, первый равен номеру строки, второй – номеру столбца.
Пусть X = {х 1 , х 2 , …, х n } . Тогда матрица отношения
Тесты по основным понятиям реляционной модели баз данных
Что представляет собой домен отношения?
Множество, представляющее собой все текущие значения одного из атрибутов отношения.
Что представляет собой отношение?
Множество, элементами которого являются упорядоченные последовательности. Каждая последовательность состоит из N значений, которые принадлежат соответствующим N доменам.
Изменяется ли смысл отношения от перестановки его атрибутов и кортежей?
Не изменяется.
Почему в отношении не может быть двух одинаковых кортежей?
Отношение - это множество, элементами которого являются кортежи. А элементы множества должны быть различимы, т. е. отличаться друг от друга.
Какие термины используются на практике вместо термина «отношение»?
1. Столбец.
2. Таблица.
3. Строка.
5. Запись.
Какие термины используются на практике вместо термина «кортеж»?
Какие термины используются на практике вместо термина «атрибут»?
Что такое степень отношения?
Количество атрибутов(столбец, поле) отношения.
Что такое мощность отношения?
Текущее количество строк отношения.
Текущее количество записей в таблице, у которой нет записей-дубликатов.
Отношение находится в первой нормальной форме, если
1. количество столбцов отношения равно количеству строк отношения.
2. элементами доменов отношения являются простые неделимые значения.
3. кортежами отношения являются простые неделимые (атомарные) значения.
4. значения атрибутов принадлежат доменам, содержащим только атомарные значения.
5. первичный ключ отношения является простым и атомарным.
6. все поля всех кортежей отношения являются атомарными.
7. Правильные ответы 1, 6.
8. Правильные ответы 2, 4, 6.
9. Правильные ответы 3, 5.
Система управления базами данных - это
программный продукт (программное обеспечение), с помощью которого пользователи могут определять, создавать и поддерживать базу данных в актуальном состоянии, а также осуществлять к ней контролируемый доступ.
12 Первичным ключом отношения (таблицы) может быть:
атрибут, значения которого в кортежах отношения не повторяются.
одно поле или минимальный набор полейтаблицы, который используется дляоднозначной идентификации конкретной строки таблицы.
Простой первичный ключ отношения - это
первичный ключ, состоящий из одного атрибута.
Составной первичный ключ отношения - это
первичный ключ, состоящий из двух или более атрибутов.
15 Чтобы отношение удовлетворяло условию целостности сущности необходимо, чтобы:
не было отсутствующих значений у атрибутов, входящих в первичный ключ отношения.
не было атрибутов, обозначенных определителем Null.
16 Внешний ключ отношения - это:
атрибут или набор атрибутов, который является первичным ключом в другом отношении.
17 Главное отношение (главная таблица) - это
таблица, у которой поля первичного ключа соответствуют полям внешнего ключа другой (подчиненной) таблицы.
отношение, у которого множество атрибутов внешнего ключа является подмножеством атрибутов первичного ключа.
Ссылочная целостность означает, что
значение внешнего ключа должно выбираться таким, чтобы в главной таблице имелась строка с таким же значением первичного ключа.
Означает, что если в отношении имеется внешний ключ, то его значение должно соответствовать значению первичного ключа в каком-либо кортеже главного отношения.
Требует, чтобы в отношении не было таких значений атрибутов, входящих во внешний ключ, которых нет в первичном ключе главного отношения
Главная функция СУБД - это
давать средства, обеспечивающие возможность получения ответов на поступающие от пользователей запросы
выдавать ответы на поступающие запросы
Селективная мощность реляционного языка - это
относительная (сравнительная) характеристика языка, определяющая ее
возможности по получению требуемой информации из базы данных.
21 Реляционная алгебра Кодда содержит:
восемь операций: четыре теоретико-множественные операции (объединения, пересечения, разности и декартова произведения) и четыре специальные реляционные операции (выборки, проекции, соединения и деления).
22 Язык является реляционно-полным, если:
1. позволяет для любого конечного набора отношений R1, R2,…, Rn в первой нормальной форме определить любое отношение, выводимое из R1, R2,…, Rn с помощью выражений реляционной алгебры Кодда.
2. его выразительная мощность не уступает реляционной алгебре Кодда.
23 Наиболее часто используются при выполнении запросов к реляционной базе данных операции:
1. выборки, проекции, соединения и декартова произведения.
R S T пфам город пфам дкод шт R.пфам Город S.пфам дкод шт Грис Лондон Джонс д1 Смит Лондон Джонс д1 Джонс Париж Джонс д2 Джонс Париж Джонс д1 Смит Лондон Смит д1 Грис Лондон Джонс д1 Смит д2 Смит Лондон Джонс д2 Смит д3 Джонс Париж Джонс д2 Грис Лондон Джонс д2 Смит Лондон Смит д1 Джонс Париж Смит д1 Грис Лондон Смит д1 Смит Лондон Смит д2 Джонс Париж Смит д2 Грис Лондон Смит д2 Смит Лондон Смит д3 Джонс Париж Смит д3 Грис Лондон Смит д3 Результатом какой операции над отношениями R и S является отношение T?
R S T дкод дназв цвет Вес пфам дкод шт R.дкод дназв цвет вес пфам S.дкод шт д1 болт черный Джонс д1 д1 болт черный Джонс д1 д2 гайка черный Джонс д2 д1 болт черный Смит д1 д3 гайка красный Смит д1 д2 гайка черный Джонс д2 д4 винт зеленый Смит д2 д2 гайка черный Смит д2 Смит д3 д3 гайка красный Смит д3 1. экви соединение дкод.
Результатом какой операции над отношениями R и S является отношение T?
R S T дкод дназв цвет вес пфам дкод шт дкод дназв цвет вес пфам шт д1 болт черный Джонс д1 д1 болт черный Джонс д2 гайка черный Джонс д2 д1 болт черный Смит д3 гайка красный Смит д1 д2 гайка черный Джонс д4 винт зеленый Смит д2 д2 гайка черный Смит Смит д3 д3 гайка красный Смит Результатом какой операции над отношениями R и S является отношение T?
R S T дкод дназв цвет вес пфам дкод шт R.дкод дназв цвет вес пфам S.дкод шт д1 болт черный Джонс д1 д1 болт черный Джонс д1 д2 гайка черный Джонс д2 д1 болт черный Смит д1 д3 гайка красный Смит д1 д2 гайка черный Джонс д2 д4 винт зеленый Смит д2 д2 гайка черный Смит д2 Смит д3 д3 гайка красный Смит д3 д4 винт зеленый Null Null Null 1. Естественное соединение по полю дкод.
3. Экви-соединение соединение по полю дкод.
4. Проекция по всем атрибутам отношений R и S.
5. Правое внешнее соединение таблиц R и S по полю дкод.
6. Левое внешнее соединение таблиц R и S по полю дкод.
Результатом какой операции над отношением R является отношение T?
R T дкод дназв цвет вес пфам шт цвет пфам д1 болт черный Джонс черный Джонс д1 болт черный Смит черный Смит д2 гайка черный Джонс красный Смит д2 гайка черный Смит д3 гайка красный Смит 1. Выборка кортежей, у которых атрибут цвет принимает значение черный или красный.
2. Естественное соединение полей цвет и пфам.
3. Экви-соединение соединение полей цвет и пфам.
4. Проекция по полям цвет и пфам.
6. Выборка первых трех записей.
