![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Специальные реляционные операцииСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
1. Выборка (сокращенное название операции - Θ (тета) - выборка):
Θ - выборкой из отношения S по атрибутам X и Y называется отношение, имеющее тот же заголовок, что и отношение S, и тело, содержащее множество всех кортежей отношения S таких, для которых проверка условия "XΘY" дает значение "истина". Ясно,что атрибуты X и Y должны быть определены на одном и том же домене, а операция на этом домене должна иметь смысл. На практике эта операция используется, как правило, в модификации, когда вместо X или Y указано скалярное значение, чаще всего в форме S WHERE XΘC, где C - литеральная константа. В результате выполнения этого оператора получается "горизонтальное" подмножество исходного отношения. Пример 3. Пусть задано отношение S (поставщики) S
Результатом выполнения операции S WHERE Город = "Томск", будет отношение
В указанной форме оператор выборки включает только простое сравнение. Однако, благодаря тождествам: 1. S WHERE Q1 AND Q2 ≡ (S WHERE Q1) INTERSECT (S WHERE Q2) 2. S WHERE Q1 OR Q2 ≡ (S WHERE Q1) UNION (S WHERE Q2) 3. S WHERE NOT Q ≡ S MINUS (S WHERE Q) оператор выборки можно расширить до формы, в которой условие в выражении WHERE будет содержать произвольное число логических сочетаний простых сравнений. 2. Проекция. Проекцией отношения S по атрибутам X1, X2, …, Xn и обозначаемой как S[X1, X2, …, Xn], называется отношение с заголовком {X1, X2, …, Xn}и телом, содержащим множество всех кортежей {X1:x1, X2:x2, …, Xn:xn} таких, для которых в отношении S значение атрибута X1 равно x1, атрибута X2 равно x2, …, атрибута Xn равно xn. Пример 4. Результатом выполнения операции S[Фио] для отношения S предыдущего примера будет отношение
Таким образом, операция проекции строит "вертикальное" подмножество искомого отношения, то есть, подмножество, получаемое исключением всех атрибутов, не указанных в операторе, с последующим удалением дублируемых кортежей. Замечание. Некорректное применение операции проекции может привести к потере информации; для нашего примера такая ситуация могла бы возникнуть, если в отношении S хранились бы сведения о двух разных поставщиках с одинаковой фамилией.
3. Естественное (экви) соединение. Пусть отношения S и P имеют заголовки{X1, X2, …, Xm, Y1, Y2, …, Yn} и {Y1, Y2,…, Yn, Z1, Z2, …, Zp, соответственно, причем атрибуты {Y1, Y2, …, Yn}по именам и доменам в обоих отношениях совпадают. Рассмотрим три совокупности {X1, X2, …, Xm}, {Y1, Y2, …, Yn} и { Z1, Z2, …, Zp} как три составных атрибута {X}, {Y} и {Z}. Тогда естественным соединением отношений S и P S JOIN P называется отношение с заголовком {X, Y, Z} и телом, содержащим множество всех кортежей {X:x, Y:y, Z:z} таких, для которых в отношении S значение атрибута X равно x, атрибута Y равно y, а в отношении P значение атрибута Y равно y, а атрибута Z равно z. Замечание. При отсутствии общих атрибутов у исходных отношений S и P естественное соединение эквивалентно декартовому произведению. Пример 5. Пусть заданы два отношения S (поставщики) и P (детали) S
P
Результатом (S JOIN P) соединения этих двух отношений будет отношение
Очевидно, что соединение может производиться не по одному, а по нескольким атрибутам. Пример 6. Пусть заданы два отношения R1
R2
Результатом выполнения операции (R1 JOIN R2) будет являться отношение
Операция естественного соединения применяется к паре отношений R1 и R2, обладающих (возможно составным) общим атрибутом S (т.е. атрибутом с одним и тем же именем и определенным на одном и том же домене). Пусть AB обозначает объединение заголовков отношений R1 и R2. Тогда естественное соединение R1 и R2 - это спроецированный на AB результат эквисоедиения R1 и R2 по A.S и B.S. Если вспомнить определение внешнего ключа отношения, то должно стать понятно, что основной смысл операции естественного соединения - возможность восстановления сложной сущности, декомопозированной (расчлененной) по причине требования первой нормальной формы. Операция естественного соединения не включается прямо в состав набора операций реляционной алгебры, но имеет очень важное практическое значение. 4. Θ-соединение (условное соединение). Это операция соединения двух отношений на основе некоторых условий, отличных от эквивалентности. Пусть отношения S и P не имеют общих имен атрибутов и условие Θ определяется аналогично операции выборки. Тогда Θ-соединением отношения S по атрибуту X с отношением P по атрибуту Y называется результат вычисления выражения (S TIMES P) WHERE XΘY, то есть, результирующее отношение строится путем выполнения операции выборки по условию для декартова произведения исходных отношений. Очевидно, что атрибуты X и Y должны быть определены на одном и том же домене и операция Θ должна иметь на этом домене смысл. Пример 7. Пусть имеются два отношения S (потоки студенческих групп) и P (аудитории). S
P
Результатом выполнения операции Θ-соединения отношений S и P по условию ВМЕСТ_АУД > КОЛ_СТУД (вместимость аудитории должна быть больше количества студентов в потоке) будет отношение
5. Деление. Пусть заголовки отношений S (делимое) и P (делитель) имеют вид{X1, X2, …, Xm, Y1, Y2, …, Yn}и {Y1, Y2, …, Yn},соответственно, причем атрибуты {Y1, Y2, …, Yn}в обоих отношениях представлены одинаковыми именами и определены на одних и тех же доменах. Будем рассматривать выражения{X1, X2, …, Xm} и {Y1, Y2, …, Yn}как два составных атрибута {X} и {Y}. Тогда результатом деления отношения S на отношение P, обозначаемое как S DEVIDEBY P, называется отношение с заголовком {X} и телом, содержащим множество всех кортежей{X:x} таких, что для каждого xЄX существует множество кортежей {X:x, Y:y} отношения S таких, у которых множество составляющих {Y:y} включает все кортежи {Y:y} отношения P. Или нестрого: результат содержит такие X-значения из отношения S, для которых соответствующие Y-значения включают все Y-значения из отношения P. Пример 8. Пусть заданы следующие отношения SP
P1
P2
P3
Результатами выполнения операций деления будут следующие отношения:
SP DIVIDEBY P1:
SP DEVIDEBY P2:
SP DEVIDEBY P3:
Пример использования операций реляционной алгебры
Пусть заданы отношения S (поставщики), P (детали) и SP (поставки):
S
P
SP
Запросы к базе данных, включающей отношения S, P, и SP, могут быть реализованы следующими цепочками операций реляционной алгебры. Запрос 1. Получить имена поставщиков, поставляющих деталь "Колено" (((SP JOIN P) WHERE Назв_дет = "Колено") JOIN S) [Фио] Запрос 2. Получить имена поставщиков, поставляющих все детали. (((SP[Ном_пост, Ном_дет]) DEVIDEBY (P[Ном_дет])) JOIN S) [Фио] Запрос 3. Получить имена поставщиков, которые не поставляют деталь "Кран". (S[Ном_пост,Фио]MINUS(((SP JOIN P) WHERE Назв_дет="Кран")JOIN S) [Ном_пост,ФИО]) [Фио] Учитывая, что каждый экземпляр схемы отношения можно представить как значение некоторой переменной, выполнение этого запроса может быть реализовано следующей иллюстративной программой:
T1 = S[Ном_пост, Фио]; T2 = SP JOIN P; T3 = T2 WHERE Назв_дет = "Кран"; T4 = T3 JOIN S; T5 = T4[Ном_пост, Фио]; T6 = T1 MINUS T5; T7 = T6[Фио]. Замечание. Если посмотреть на общий обзор реляционных операций, то видно, что домены атрибутов результирующего отношения однозначно определяются доменами отношений-результатов. Однако с именами атрибутов результата не всегда бывает все так просто. Например, представим себе, что у отношений-операндов операции прямого произведения имеются одноименные атрибуты с одинаковыми доменами. Каким должен был бы быть заголовок результирующего отношения? Поскольку заголовок - это множество, в нем не должны содержаться одинаковые элементы. Но и потерять атрибут в результате недопустимо. А это значит, что в этом случае вообще невозможно корректно выполнить операцию прямого произведения. Аналогичные проблемы могут возникать и в случаях других двуместных операций. Для их разрешения в состав операций реляционной алгебры вводится операция переименования. Ее следует применять в любом случае, когда возникает конфликт именования атрибутов в отношениях-операндах одной реляционной операции. Тогда к одному из операндов сначала применяется операция переименования, а затем основная операция выполняется уже безо всяких проблем.
Реляционное исчисление Реляционная алгебра и реляционное исчисление представляют собой два альтернативных подхода. Принципиальное различие между ними состоит в следующем: алгебра представляет в явном виде набор операций, которые можно использовать, чтобы сообщить системе, как из определенных в базе данных отношений построить необходимое отношение, в то время как исчисление представляет собой просто систему обозначение для определения необходимого отношения в терминах имеющихся отношений. Пример. Пусть к базе данных, содержащей отношения S, P и SP (точнее, к СУБД, в рамках которой реализована данная база данных) поступил запрос: "Получить номера и города поставщиков, поставляющих деталь "Смеситель". Реализация запроса в рамках аппарата реляционной алгебры могла бы включать следующие шаги: П1. Образовать естественное соединение отношений SP и P по атрибуту Ном_дет. П2. Выбрать из результата этого соединения кортежи, у которых Назв_дет= "Смеситель". П3. Образовать естественное соединение результирующего отношения П2 и отношения S по атрибуту Ном_пост. П4. Спроецировать результирующее отношение по атрибутам Ном_пост и Город. В терминах реляционного исчисления формулировка искомого выражения могла бы выглядеть следующим образом: “Получить атрибуты Ном_пост и Город для таких поставщиков отношения S, для которых существует поставка в отношении SP детали со значением атрибута Ном_дет таким, что значение атрибута Назв_дет в соответствующих кортежах отношения P равно " Смеситель ". Реляционное исчисление основано на разделе математической логики, который называется исчислением (или логикой) предикатов. Существуют две версии реляционного исчисления – исчисление кортежей и исчисление доменов. В исчислении кортежей основным является понятие переменной кортежа, то есть, переменной, в качестве допустимых значения которой выступают кортежи некоторого отношения. В исчислении доменов основным является понятие переменной домена. Обе эти версии реляционного исчисления эквивалентны. Рассмотрим в самом общем виде механизм использования аппарата исчисления кортежей. Рассмотрим основные понятия данного инструментария: · переменная кортежа, · правильно построенная формула, · выражение исчисления кортежей. Пусть переменная кортежа определяется (описывается) выражением [3] RANGE OF T IS V1, V2, …, Vn, где T – переменная кортежа, V i (i =1, …, n) – имя отношения либо выражение исчисления кортежей. Пусть каждое из Vi (i =1, …, n) является отношением, причем все отношения должны быть совместимыми по типу. Тогда областью значений переменной кортежа T является множество кортежей объединения отношений Vi (i =1, …, n). Примеры определения переменной кортежа: RANGE OF TS IS S; RANGE OF TP IS P; RANGE OF T1 IS TS WHERE S.Город = "Томск". Замечание. В третьем примере значениями переменной Т1 являются все кортежи отношения S, для которых выполняется указанное в определении условие.
Правильно построенная формула (ППФ). Понятие ППФ является одним из центральных в логике предикатов, следовательно, и в реляционном исчислении. ППФ служат для выражения условий, накладываемых на кортежные переменные. Базовым при построении ППФ является определение атома. Применительно к исчислению кортежей выделяют два типа атомов: Тип 1. T.X Θ U.Y, где T,U – переменные-кортежи, X,Y – атрибуты, Θ = {<, ≤, =, ≠, ≥,>}. Тип 2. С Θ T.X, T.X Θ С, где C – литеральная константа. Таким образом, основой ППФ являются простые сравнения, представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или литерально заданных констант). Например, конструкция S.Город ="Томск" является простым сравнением. По определению, простое сравнение является ППФ. Итак, Правило 1. Каждый атом есть ППФ. Более сложные варианты ППФ строятся с помощью логических связок NOT, AND, OR и IF... THEN. Правило 2 (введение логических формул). Если φ и ψ – суть ППФ, то - NOT φ, - φ AND ψ, - φ OR ψ, - IF Q THEN φ, (где Q – логическая формула), - (φ), тоже суть ППФ. Наконец, допускается построение ППФ с помощью кванторов. Правило 3 (введение кванторов). Обозначим через EXISTS квантор с уществования и через FORALL – квантор всеобщности. Пусть φ есть ППФ и T – переменная. Тогда - EXISTS T(φ), - FORALL T(φ) - суть ППФ. Здесь первая формула означает: "Существует по крайней мере одно такое значение переменной T (по крайней мере один кортеж соответствующего отношения), на котором результат вычисления ППФ φ равен булевому значению True ". Трактовка второй формулы очевидна: "Для всех значений переменной T (на всех кортежах соответствующего отношения) вычисление значения ППФ φ дает значение True. " Переменные, входящие в ППФ, могут быть свободными или связанными. Все переменные, входящие в ППФ, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении ППФ получено значение истина, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной Т использовано сразу после квантора при построении ППФ вида EXISTS или FORALL, то в этой ППФ и во всех ППФ, построенных с ее участием, Т - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной ППФ, связавшей эту переменную. При вычислении значения такой ППФ используется не одно значение связанной переменной, а вся ее область определения. Пусть СОТР1 и СОТР2 - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, ППФ EXISTS СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп) для текущего кортежа переменной СОТР1 принимает значение истина в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется хотя бы один кортеж (связанный с переменной СОТР2) такой, что значение его атрибута СОТР_ЗАРП удовлетворяет внутреннему условию сравнения. В свою очередь, ППФ FORALL СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп) для текущего кортежа переменной СОТР1 принимает значение истина в том и только в том случае, если для всех кортежей отношения СОТРУДНИКИ (связанных с переменной СОТР2) значения атрибута Сотр_зарп удовлетворяет условию сравнения. На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Легко видеть, что если переменная T является связанной в ППФ φ, то во всех ППФ, включающих φ, может использоваться имя переменной T, которая может быть свободной или связанной, но в любом случае не имеет никакого отношения к вхождению переменной T в ППФ φ. Пример. Пусть ППФ F1 и F2 имеют следующий вид: F1 - EXISTS СОТР2 (СОТР1.Сотр_отд_ном = СОТР2.Сотр_отд_ном) F2 - FORALL СОТР2 (СОТР1.Сотр_зарп > СОТР2.Сотр_зарп) Очевидно, что в ППФ (F1 AND F2) два связанных вхождения переменной СОТР2 имеют совершенно разный смысл. Сформулируем данные понятия более точно. Под экземпляром переменной кортежа в ППФ будем понимать наличие имени переменной: a) в строке T.X, b) в строках EXISTS T и FORALL T. Заметим, что здесь понятие экземпляра переменной рассматривается в чисто синтаксическом аспекте. Каждый экземпляр переменной кортежа T в ППФ является или свободным, или связанным в зависимости от выполнения следующих условий: · в атомах все экземпляры свободны; · экземпляры переменной T, которые в формуле φ, связаны в формулах EXISTS T(φ) и FORALL T(φ); · в логических ППФ экземпляры свободны или связанны в зависимости от того, свободны или связаны они в формулах φ и ψ. Примеры: Атомы: 1) TS.Ном_пост=”S1” 2) TS.Ном_пост ≠ TSP.Ном_пост Экземпляры TS и TSP в обоих примерах свободны. Логические формулы: 1) NOT (TS.Город = “Томск”) 2) (TS.Ном_пост = TSP.Ном_пост) AND (TSP.Ном_дет ≠ T.Ном_дет) Экземпляры TS и TSP в обоих примерах свободны. Кванторные формулы: 1) EXISTS TSP ((TSP.Ном_пост = TS.Ном_пост) AND (TSP.Ном_дет = TP.Ном_дет) AND (TP.Назв_дет ≠ “Смеситель”)) 2) FORALL TP (TP.цвет = “Белый”) В первом примере все три экземпляра TSP связаны, а экземпляры TS и TP – свободны; во втором примере оба экземпляра TP связаны. Еще раз отметим, что понятие связности необходимо для определения истинности или ложности формулы (соответствующего утверждения): связность принципиальным образом уточняет сформулированное утверждение. Выражения исчисления кортежей. В общем виде выражение исчисления кортежей имеет вид: <список_целевых_элементов> [WHERE ППФ], где: - целевой элемент - имя простой переменной (T) или выражение вида (T.A), - WHERE – условие. Результатом выполнения выражения является удовлетворение запроса к базе данных. Примеры. Реализовать в виде выражений следующие запросы: 1) "Определить имена поставщиков, поставляющих деталь "Кран": TS.ФИО WHERE EXISTS TSP ((EXISTS TS(TSP.Ном_пост = TS.Ном_пост)) AND (EXISTS TP ((TS.Ном_дет = TP.Ном_дет) AND (TP.Ном_дет = “Кран”))) 2) "Определить имена поставщиков, поставляющих все детали": TS.ФИО WHERE FORALL TP (EXISTS TSP)(EXITS TS (TSP.Ном_пост = TS.Ном_пост)) AND (TSP.Ном_дет = TS.Ном_дет))) Очевидно, что при использовании механизма исчисления пользователь лишь устанавливает определенные характеристики необходимого отношения, оставляя СУБД решать, что необходимо соединять, выбирать, проецировать и т.д. для получения требуемого результата. Таким образом, можно сказать, что, по крайней мере внешне, формулировка удовлетворения запроса в терминах реляционной алгебры носит предписывающий (процедурный) характер, а реляционного исчисления – описательный (декларативный). В алгебре описывается решение проблемы, запрос, представленный на языке реляционной алгебры, может быть вычислен на основе вычисления элементарных алгебраических операций с учетом их старшинства и возможного наличия скобок. В исчислении предикатов описывается, в чем проблема заключается; формула только устанавливает условия, которым должны удовлетворять кортежи результирующего отношения. Эти отличия, однако, существуют только внешне. Доказано, что механизмы реляционной алгебры и реляционного исчисления эквивалентны, то есть для любого допустимого выражения реляционной алгебры можно построить эквивалентную (т.е. производящую такой же результат) формулу Различия связаны с разными стилями выражения: алгебра ближе к языкам программирования, а исчисление – естественному языку. Обычно (как, например, в случае языка SQL) язык основывается на некоторой смеси алгебраических и логических конструкций. Тем не менее, знание алгебраических и логических основ языков баз данных часто бывает полезно на практике. Подробно реляционная модель данных рассмотрена в [2].
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-07-16; просмотров: 483; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.216.0.219 (0.014 с.) |