Дисциплина «Базы данных» МТУСИ Практические занятия 1-3. БД (1-4). Занятие Теоретикомножественные операции реляционной алгебры
 Скачать 0.52 Mb.
|
|
1 Дисциплина «Базы данных» МТУСИ Практические занятия 1-3 Занятие 1. Теоретико-множественные операции реляционной алгебры Основной структурой данных в модели является отношение, поэтому модель получила название реляционной (от английского relation — отношение). N-арным отношением R называют подмножество декартова произведения D 1 *D 2 *…*D n множеств D 1 , D 2 , D n (n ≥ 1), необязательноразличных. Исходные множества D 1 , D 2 , D n называют доменами. R D 1 *D 2 *...*D n , где D 1 *D 2 *…*D n — полное декартово произведение. Полное декартово произведение — это набор всевозможных сочетаний из n элементов каждое, где каждый элемент берется из своего домена. R моделирует реальную ситуацию → может содержать, только некоторые строки. Графическая интерпретация отношения - таблица, столбцы которой соответствуют вхождениям доменов в отношение, а строки — наборам из n значений, взятых из исходных доменов, которые расположены в строго определенном порядке в соответствии с заголовком. Такие наборы из n значений часто называют n-ками. R Фамилия Дисциплина Оценка Иванов ТА 4 ….. ….. ….. Степанов БД 5 Вхождение домена в отношение принято называть атрибутом . Строки отношения называются кортежами . Количество атрибутов в отношении называется степенью, или рангом , отношения. в отношении не может быть одинаковых кортежей: отношение — это множество! Операции над отношениями Теоретико-множественные операции реляционной алгебры Объединением двух отношений называется отношение, содержащее множество кортежей, принадлежащих либо первому, либо второму исходным отношениям, либо обоим отношениям одновременно. Пусть заданы два отношения R 1 = { r 1 } , R 2 = { r 2 }, где r 1 и r 2 — их соответственные кортежи, то объединение R 1 U R 2 = { r | r R 1 r R 2 }. Здесь r — кортеж нового отношения, — операция логического сложения «ИЛИ». Пересечением отношений называется отношение, которое содержит множество кортежей, принадлежащих одновременно и первому и второму отношениям R 1 и R 2 : R 3 = R 1 R 2 ={ r | r R 1 r R 2 }, 2 здесь — операция логического умножения (логическое «И»). Разностью отношений R 1 и R 2 называется отношение, содержащее множество кортежей, принадлежащих R 1 и не принадлежащих R 2 : R 5 = R 1 \ R 2 = { r | r R 1 r R 2 } Операции объединения, пересечения и разности применимы только к отношениям с эквивалентными схемами Пример 1. Исходные отношения R 1 и R 2 содержат перечни товаров, находящихся соответственно на первом и втором складах. R1 R2 Артикул Товар Артикул Товар 01 Сервер Gelios 01 Сервер Gelios 02 Сервер Dell 03 Сервер NPort 03 Сервер NPort 08 Сервер HP 04 ПЛК ICP 09 ПЛК VIPA 05 ПЛК ОВЕН 05 ПЛК ОВЕН 06 Роутер Huawei 07 Роутер Netis При выполнении каждого задания написать соответствующие формулы в общем виде! Задание 1. 1 Объединение Построить отношение R 3 содержащее общий перечень товара на складах, то есть характеризует общую номенклатуру складов. Задание 1. 2 . Пересечение Построить отношение R 4 содержащее перечень товара, который есть в наличии одновременно на двух складах. Задание 1.3. Разность Построить отношение R 5 содержащее перечень товара, находящегося только на складе 1 и отношение R 6 содержащее перечень товара, находящегося только на складе 2 и написать соответствующие формулы. --------------------------------------------------------------------------------------------------------------- Пример 2. Рассмотрим пример из другой предметной области. Исходными являются три отношения R21, R22 и R23- Все они имеют эквивалентные схемы. ❑ R21= (ФИО, Паспорт, Школа); ❑ R22= (ФИО, Паспорт, Школа); ❑ R23= (ФИО, Паспорт, Школа). 3 Ситуация была характерна для периода, когда были разрешены так называемые репетиционные вступительные экзамены, которые сдавались раньше основных вступительных экзаменов в вуз. Отношение R21 содержит список абитуриентов, сдававших репетиционные экзамены. Отношение R22 содержит список абитуриентов, сдававших экзамены на общих условиях. И наконец, отношение R23 содержит список абитуриентов, принятых в институт. При неудачной сдаче репетиционных экзаменов абитуриент мог делать вторую попытку и сдавать экзамены в общем потоке, поэтому некоторые абитуриенты могут присутствовать как в первом, так и во втором отношении. Задание. Записать формулы, дающие ответы на следующие вопросы: 2.1. Список абитуриентов, которые поступали два раза и не поступили в вуз. 2.2. Список абитуриентов, которые поступили в вуз с первого раза, то есть они сдавали экзамены только один раз и сдали их так хорошо, что сразу были зачислены в вуз. 2.3. Список абитуриентов, которые поступили в вуз только со второго раза. 2.4. Список абитуриентов, которые поступали только один раз и не поступили. Расширенное декартово произведение Кроме перечисленных трех теоретико-множественных операций в рамках реляционной алгебры определена еще одна теоретико-множественная операция — расширенное декартово произведение. Эта операция не накладывает никаких дополнительных условий на схемы исходных отношений, поэтому операция расширенного декартова произведения, обозначаемая R 1 R 2 , допустима для любых двух отношений. Но прежде чем определить саму операцию, введем дополнительно понятие конкатенации, или сцепления, кортежей. Сцеплением, или конкатенацией, кортежей с = 1 с 2 , ..., с n > и q = 1 q 2 , ..., q m > называется кортеж, полученный добавлением значений второго в конец первого. Сцепление кортежей с и q обозначается как (с , q). (с, q) = <с 1 с 2 , ... , c n , q 1 , q 2 , ... q m >, Здесь n — число элементов в первом кортеже с, m — число элементов во втором кортеже q. Все предыдущие операции не меняли степени или арности отношений — это следует из определения эквивалентности схем отношений. Операция декартова произведения меняет степень результирующего отношения. Расширенным декартовым произведением отношения R 1 = { r } степени n со схемой S R1 = (А 1 , А 2 , ... , А n ) и отношения R 2 = { q } степени m со схемой S R2 = (В 1 , В 2 , ... , В n ) называется отношение R 3 степени n+m со схемой S R3 = (А 1 А 2 , ... , А n , В 1 В 2 , ..., В n ), 4 содержащее кортежи, полученные сцеплением каждого кортежа r отношения R 1 с каждым кортежем q отношения R 2 То есть R 1 R 2 = {(r, q) | r R 1 ^ q R 2 } Операцию декартова произведения с учетом возможности перестановки атрибутов в отношении можно считать симметричной. Она используется для получения универсума — отношения, которое характеризует все возможные комбинации между элементами отдельных множеств. Однако самостоятельного значения этот результат обычно не имеет, он участвует в дальнейшей обработке. Получаются очень «большие» отношения. Используют для ситуации, которая х-ся словом «все». Задание 1.4. Пусть в отношении R7 задана обязательная номенклатура товаров для всех складов, а в отношении R8 дан перечень всех складов. R7 R8 Артикул Товар Склад 01 Сервер Gelios Склад 1 02 Сервер Dell Склад 2 03 Сервер NPort Склад 3 04 ПЛК ICP 05 ПЛК ОВЕН 06 Роутер Huawei 07 Роутер Netis 08 Сервер HP 09 ПЛК VIPA 11 ПЛК SIEMENS 10 Роутер Tenda Построить отношение R9, которое соответствует ситуации, когда каждый склад хранит все товары из перечня (Какая это операция?) Задание 1.5 Пусть отношение R10, характеризует реальное хранение товаров на каждом складе. В отношении R11 отобразить какие товары на каких складах из общей обязательной номенклатуры не хранятся. R10 Артикул Товар Склад 01 Сервер Gelios Склад 1 02 Сервер Dell Склад 1 03 Сервер NPort Склад 1 04 ПЛК ICP Склад 1 5 05 ПЛК ОВЕН Склад 1 06 Роутер Huawei Склад 1 07 Роутер Netis Склад 1 08 Сервер HP Склад 1 09 ПЛК VIPA Склад 1 11 ПЛК SIEMENS Склад 1 10 Роутер Tenda Склад 1 05 ПЛК ОВЕН Склад 2 06 Роутер Huawei Склад 2 07 Роутер Netis Склад 2 08 Сервер HP Склад 2 09 ПЛК VIPA Склад 2 10 Роутер Tenda Склад 2 01 Сервер Gelios Склад З 02 Сервер Dell Склад З 03 Сервер NPort Склад З 04 ПЛК ICP Склад З 05 ПЛК ОВЕН Склад 3 06 Роутер Huawei Склад 3 07 Роутер Netis Склад З 08 Сервер HP Склад З 11 ПЛК SIEMENS Склад З Задание 1.6 . Группа теоретико-множественных операций избыточна. Как можно записать операцию пересечения через объединение и разность? (или показать взаимосвязь любых других операций) Домашнее задание. Придумать 2 теста (содержит 3-4 вопроса). Занятие 2-3. Специальные операции реляционной алгебры Горизонтальный выбор, или операция фильтрации, или операция ограничения отношений (унарная операция) R[α (r)] = {r|r R α (r) = "Истина"} Задание 1.7 . В отношение R12 выбрать из R10 детали с шифром «05». Операция проецирования (унарная операция) Проекцией R[B] отношения R на набор атрибутов В, называется отношение со схемой, соответствующей набору атрибутов В S R[B] = В, содержащему кортежи, получаемые из кортежей исходного отношения R путем удаления из них значений, не принадлежащих атрибутам из набора В. Пусть R = { r } — отношение, со схемой S R = (A 1, A 2, … , A n ), Пусть В подмножество { A i }; В { A i }. При этом пусть В ’ — множество атрибутов из { А i }, не вошедших в В. В ’ ={ A ' i }. 6 Если В = {A 1 i , A 2 i ,…,A k i }, B ’ = {А 1 j , А 2 j ,..., А m j } и s = 1 i , a 2 i ,..., a k i >; a k i A k i ; q = < a 1 j , a 2 j , ... , a m j > ; a m j A m j то r[B] = s , причем r=(s,q) R[B] = {r[B]} – обозначение операции !!! все дублирующие кортежи удаляются из результирующего отношения.(!!!) Задание 1.8. Выбрать все склады, которые хранят деталь «ПЛК ICP». (Построить отношения R13, R14) Задание 1.9-1.11. Даны отношения RD1-RD4 Задание 1.9. Найти подразделения, находящиеся западнее Москвы. Задание 1.10. Найти пользователей из Москвы, имеющих задания. Задание 1.11. Найти пользователей, имеющих срочные задания, у которых в данный момент столько же времени, что и у вас. RD2 Пользователи Номер ФИО Подраз деление 00011073 Качалов В.И. 1 00011075 Дуров Ю.В. 1 00011076 Папанов А.Д. 2 00011004 Ермолаев Г.О. 1 00013062 Янковский К.О. 3 00011003 Нечаев А.С. 4 00011005 Бортников Ю.И. 2 RD1 Задания № Текст Пользо ватель Сроч ное 1 Задание 1 00011076 1 2 Задание 2 00011075 0 3 Задание 3 00011073 0 4 Задание 4 00013062 1 5 Задание 5 00011003 1 6 Задание 6 00013062 1 7 Задание 7 00011075 0 RD3 Подразделения № Название Город 1 Главный офис Москва 2 Московский филиал Москва 3 Филиал на Неве Санкт- Петербург 4 Филиал в Англии Лондон 5 Филиал в США Нью-Йорк 6 Восточный филиал Владивосток RD4 Часовые пояса Город Часовой пояс (UTC+X) Москва 4 Санкт-Петербург 4 Лондон 0 Нью-Йорк -5 Владивосток 11 7 Операция условного соединения (бинарная операция) В отличие от рассмотренных специальных операций реляционной алгебры: фильтрации и проектирования, которые являются унарными, то есть производятся над одним отношением, операция условного соединения является бинарной, то есть исходными для нее являются два отношения, а результатом — одно. Одна из наиболее важных операций реляционной алгебры. Она имеет большое практическое значение. На самом деле выделяют несколько ее разновидностей, которые мы рассмотри дальше. Операцию соединения можно рассматривать как декартово произведение с последующей операцией выборки. Общий подход: Пусть R = {r}, Q = {q} — исходные отношения, со схемами S R , S Q S R =(A 1 , A 2 , … ,A m ); S Q = (B 1 B 2 , ... , B n ), где А m , B n — имена атрибутов Заданы наборы -сравнимых атрибутов А и В A { A i }; B { B i }, i=1,k (!!!) Соединение отношений R и Q при условии это подмножество декартова произведения отношений RQ, кортежи которого удовлетворяют условию . R[ ]Q = { (r,q) | r[A i ] q[B i ]= «Истина», i=1,k } Эта операция определяет отношение, которое содержит кортежи из декартова произведения отношений R Q , удовлетворяющие условию . Условие (предикат) имеет вид r[A i ] q[B i ] где вместо может быть указан один из операторов сравнения ( > , >= , < , <= , = , <> ). Наиболее распространены два типа операций соединения: операция соединения по условию(1) и операция естественного соединения(2). (1) При выполнении операции соединения по условию двух отношений происходит конкатенация строк отношений-операндов, затем полученная сцепленная строка проверяется на соответствие заданному условию. Если строка удовлетворяет условию, она включается в отношение-результат. (2) Если отношения обладают общим атрибутом (возможно составным), то условие соединения может быть опущено, при этом подразумевается, что сравнение производится на равенство общих атрибутов. Задание 1.12. Пусть отношение R 15 содержит перечень товаров с указанием упаковки. Получить перечень товара, которые находятся на складе 1 в упаковке «OEM» R15 Артикул Товар Упаковка 0001 Сервер Gelios OEM 0002 Сервер Dell ODM 0003 Сервер NPort OEM 0004 ПЛК ICP Full 0005 ПЛК ОВЕН Full 0006 Роутер Huawei OEM 0007 Роутер Netis OEM 0008 Сервер HP ODM 0009 ПЛК VIPA Full 0011 ПЛК SIEMENS Full 0010 Роутер Tenda OEM 8 Операция деления. Операция деления удобна тогда, когда требуется сравнить некоторое множество характеристик отдельных атрибутов. Она «обратна» операции умножения. Описать ее в «житейских» терминах довольно сложно, поэтому прибегнем к некоторым упрощениям. Пусть даны два отношения: делимое R со схемой (А 1 , А 2 ,…,А n , В 1 ,В 2 ,…В m ) и делитель T со схемой (В 1 ,В 2 ,…В m ). Атрибут В i определен на одном и том же домене и имеет одинаковое имя. Результат деления R на T – отношение С с атрибутами (А 1 , А 2 ,…,А n ). С= R:T Формируется результат так. Если в строке отношения R значения атрибутов В 1 ,В 2 ,…В m совпадают с одной из строк отношения T, то эти значения отсекаются и строка без них включается в отношение-результат С. Пример R (делимое) T (делитель) Частное (A)Job (A1)Chair (B)Chair (C)Job Зав.каф. 22 22 Зав.каф. Проф. 22 Проф. Доц. 22 Доц. Зав.каф. 23 Доц. 23 Ст.преп. 24 22 Зав.каф. ассист 24 23 Доц Результат операции деления R:T - набор кортежей отношения R , определенных на множестве атрибутов C, которые соответствуют комбинации всех кортежей отношения T причем B A и C=A\B . T1=R[C]; (Зав.каф.,Проф.,Доц.,Ст.преп.,ассист) T2=((T T1)-R)[C]; (Ст.преп. 22,ассист 22) R[А:В]Т = T1 - T2. (Зав.каф.,Проф.,Доц) Задание 1.10. Используя отношения R 7 , и R 10 определить перечень складов (отношение R17), в которых хранится вся номенклатура деталей. Операция деления достаточно сложна для абстрактного представления. Она может быть заменена последовательностью других операций. Задание 1.11. Выполним тот же запрос с использованием других операций. Для этого определим последовательность промежуточных запросов, которая приведет нас к конечному результату: 1. Построим отношение, которое моделирует ситуацию, когда на каждом складе хранится вся номенклатура, это уже построенное нами ранее расширенное декартово произведение отношений R 7 и R 8 . Это отношение R 9 : 2. Теперь найдем перечень того, что из обязательной номенклатуры не хранится на некоторых складах 3. Далее найдем те склады, в которых не все товары хранятся, для этого нам надо отношение R 11 спроецировать на столбец «склад»: 4. А теперь из перечня всех складов вычтем те, где хранятся не все детали, и получим ответ на запрос, и это будет тот же результат, что и в отношении R 17 9 Задание 2.4. Посмотрим, как работают операции реляционной алгебры для другого примера. Возьмем набор отношений, которые моделируют сдачу сессии студентами некоторого учебного заведения. R 1 =(ФИО, Дисциплина, Оценка); R 2 = (ФИО, Группа); R 3 = (Группы, Дисциплина) где R 1 — информация о попытках (как успешных, так и неуспешных) сдачи экзаменов студентами; R 2 — состав групп; R 3 — список дисциплин, которые надо сдавать каждой группе. S – отношение, содержащее требуемую информацию. □ Список студентов, которые сдали экзамен по БД на «отлично». Результат может быть получен применением операции фильтрации по сложному условию к отношению R 1 и последующим проектированием на атрибут «ФИО» (нам ведь требуется только список фамилий). S=… □ Список тех, кто должен был сдавать экзамен по БД, но пока еще не сдавал. Сначала найдем всех, кто должен был сдавать экзамен по БД. В отношении R 3 находится список всех дисциплин, по которым каждая группа должна была сдавать экзамены, ограничим перечень дисциплин только «БД». "Для того чтобы получить список студентов, нам надо соединить отношение R 3 с отношением R 2 , в котором определен список студентов каждой группы . R 4=… □ Теперь получим список всех, кто сдавал экзамен по «БД» (нас пока не интересует результат сдачи, а интересует сам факт попытки сдачи, то есть присутствие в отношении R 1 ): R 5 = и, наконец, результат — все, кто есть в первом множестве, но не во втором: S = □ Список несчастных, имеющих несколько двоек: S = (R 1 [R 1 .ФИО = R' 1 .ФИО R 1 .Дисциплина R' 1 .Дисциплина R 1 .Оценка 2 R' 1 .Оценка 2]R' 1 )[ФИО] Этот пример весьма интересен: для поиска строк, удовлетворяющих в совокупности условию больше одного, применяется операция соединения отношения с самим собой. Поэтому мы как бы взяли копию отношения R 1 и назвали ее R' 1 □ Список круглых отличников. Строим список всех пар <студент—дисциплина>, которые в принципе должны быть сданы: R 4 =… Строим список пар <студент—дисциплина>, где получена оценка «отлично»: R 5 =… Строим список студентов, что-либо не сдавших на «отлично»: R 6 = Наконец, исключив последнее отношение из общего списка студентов, получаем результат: S= … Обратите внимание, что для получения множества студентов, что-либо не сдавших на «отлично» (R 6 ), мы осуществили «инверсию» множества всех отлично сданных пар <студент—дисциплина> (R 5 ) путем вычитания его из предварительного построенного универсального множества (R 4 ). Рекомендуется очень внимательно разобрать этот пример и вникнуть в смысл каждого действия — это пригодится для понимания реляционной алгебры. 10 Занятие 4 Задания для самостоятельной работы Задание 1 Даны отношения, моделирующие работу банка и его филиалов. Клиент может иметь несколько счетов, при этом они могут быть размещены как в одном, так и в разных филиалах банка. В отношении R 1 содержится информация обо всех клиентах и их счетах в филиалах нашего банка. Каждый клиент, в соответствии со своим счетом, может рассчитывать на некоторый кредит от нашего банка, сумма допустимого кредита также зафиксирована. R 1 ФИО клиента № филиала № счета Остаток Кредит С использованием языка реляционной алгебры составить запросы, позволяющие выбрать: 1. Филиалы, клиенты которых имеют счета с остатком, превышающим $1000. 2. Клиентов, которые имеют счета во всех филиалах данного банка. 3. Клиентов, которые имеют только по одному счету в разных филиалах банка. То есть в общем у этих клиентов может быть несколько счетов, но в одном филиале не более одного счета. 4. Клиенты, которые имеют счета в нескольких филиалах банка, расположенных только в одном районе. 5. Филиалы, которые не имеют ни одного клиента. 6. Филиалы, которые имеют клиентов с остатком на счету 0 (ноль). 7. Филиалы, у которых есть клиенты с кредитом, превышающим остаток на счету в 2 раза. Задание 2 Даны отношения, моделирующие работу международной фирмы, имеющей несколько филиалов. Филиалы фирмы могут быть расположены в разных странах, это отражено в отношении R 1 .Клиенты фирмы также могут быть из разных стран, и это отражено в отношении R 4 . По каждому конкретному заказу клиент мог заказать несколько разных товаров. R 3 N заказа Товар Количество С использованием реляционной алгебры составить запросы, позволяющие выбрать: 1. Заказчиков, которые работают со всеми филиалами фирмы, но покупают только один товар. 2. Филиалы фирмы, которые торгуют всеми товарами. 3. Товары, которые фирма продает только в одной стране. 4. Заказчиков, которые работают с филиалами фирмы, которые расположены только в R 2 № филиала Район R 1 Филиал Страна R 2 Филиал Заказчик № заказа R 4 Заказчик Страна 11 одной стране. 5. Филиалы, с которыми не работает ни один заказчик. 6. Заказчиков, которые работают только с филиалами, расположенными в той же стране, что и заказчик. 7. Заказчиков, которые покупают все товары, представленные в отношении R 3 Задание 3 Даны отношения, моделирующие работу фирмы, занимающейся разработкой программных систем. Каждый сотрудник административно закреплен только за одним отделом. Файлы хранятся на разных серверах. На разных серверах файлы могут иметь одинаковые имена. Создатель файла является его владельцем, поэтому у каждого файла только один владелец, но владелец файла может разрешить пользоваться файлом другим сотрудникам. Существует множество системного программного обеспечения, каждая программа может работать с одним или с несколькими файлами, расположенными на одном или нескольких серверах: R 1 R 4 Название файла Имя владельца файла Сотрудник Отдел R 2 Название программы Название файла Сервер R 3 Название файла Название сервера С использованием реляционной алгебры и языка составить запросы, позволяющие выбрать: 1. Файлы, которые имеют нескольких пользователей из разных отделов. 2. Программы, которые работают только с одним файлом. 3. Файлы, которые имеют одно и тоже имя, но расположены на различных серверах и используются сотрудниками разных отделов. 4. Файлы, с которыми работают сотрудники всех отделов. 5. Файлы, пользователями которых являются сотрудники только одного отдела. 6. Программы, которые работают со всеми серверами. 7. Отделы, сотрудники которых не работают ни с одним файлом. То есть отделы, в которых нет ни одного сотрудника, работающего с каким-нибудь файлом. 8. Отделы, сотрудники которых работают со всеми серверами. 9. Серверы, с которыми работают сотрудники только одного отдела. |