Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Основы реляционной алгебры




 

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

1. C = A U B- объединение (UNION). Результат образуют кортежи, входящие в A или B без дублирования. Отношения A и B должны иметь одинаковое количество атрибутов и соответствие их типов, то есть атрибуты с одинаковыми порядковыми номерами в отношениях A и B должны быть совместимы по типам данных. Например, таблицы A и B могут представлять собой данные о студентах, получивших зачет по двум разным предметам. Тогда в объединении таблиц будут представлены студенты, получившие хотя бы один зачет.

2. C = A - B- разность (MINUS). Результат образуют кортежи, входящие как в A, но не входящие в B. Операция корректна при тех же требованиях к отношениям A и B, что и предыдущая операция. Для предыдущего примера в C окажутся только те студенты, которые получили зачет по первому, но не по второму предмету.

3. C = A ∩ B- пересечение (INTERSECT). Результат образуют кортежи, входящие как в A, так и в B. Требования к операндам такие же, как и ранее. Пересечение выражается через разность: A ∩ B = A - (A –B). Для того же примера в C попадут обладатели зачетов по обоим предметам.

4. C = A ´ B – декартово произведение (TIMES). Результат образуют все упорядоченные кортежи, образованные сцеплением (конкатенацией) кортежей из отношений A и B. Число атрибутов декартова произведения равно сумме числа атрибутов A и B, а число кортежей определяется как произведение числа кортежей A и B. Эта операция трудоемка и требует больших затрат памяти, поэтому служит в большей степени для теоретических, а не практических целей. Например, если в таблице A (Stud, Gr) представлены студенты разных групп потока, а в B (Prep, Kaf) преподаватели разных кафедр, которые могут принимать экзамены сессии, то в C (Stud, Gr, Prep, Kaf) окажутся все возможные пары студент-преподаватель.

5. C = σF (A) - селекция или выборка (SELECT). Результатом является множество кортежей, для которых логическое выражение или условие F устанавливается в истину. Это первая рассматриваемая операция, присущая именно реляционной алгебре, а не теории множеств. Логическое выражение строится на основе атрибутов отношения A. Например, операция селекции для таблицы A из предыдущего примера по условию Gr=’ПС-12’ определит таблицу C (Stud, Gr), в которой останутся только студенты группы ПС-12.

6. C = πS (A) - проекция (PROJECT). Здесь список S является подмножеством атрибутов A и задает атрибуты результата операции. Кортежами результата являются “урезанные” кортежи отношения A с исключением дублирования одинаковых кортежей. Пусть, например, в таблице А (Stud, Gr, St) поле St определяет старосту группы. Проекция A по атрибутам Gr, St даст перечень групп с их старостами. Число записей в результате окажется меньше, чем в A, поскольку в каждой группе может быть много студентов, а информация о группе появится в единственной записи.

7. C = AB - соединение (JOIN). Операция соединения имеет несколько видов. Наиболее общий из них представляет θ-соединение. Результат образуют все упорядоченные кортежи, образованные сцеплением (конкатенацией) тех кортежей из отношений A и B, для которых выполняется условие Ai θ Bj, где Ai и Bj – значения i-го и j-го атрибутов A и B, а θ – одна из операций сравнения (‘=’, ‘<’, ‘>’, ‘≠’, ‘≤’, ‘≥’). Таким образом, θ-соединение представляет собой декартово произведение с условием. В подавляющем большинстве случаев θ задает операцию равенства, и такое соединение называется эквисоединением. Если атрибуты Ai и Bj имеют одинаковое наименование, то оно появится в результате дважды, и во всех кортежах будут повторяться одинаковые значения. Это, конечно, неудобно, поэтому чаще используют естественное соединение, в котором все одноименные атрибуты отношений A и B встречаются один раз. Легко заметить, что естественное соединение теоретически сводится к последовательности таких операций, как декартово произведение, селекция и проекция. Однако практически оно реализуется гораздо эффективнее.

Пусть, например, таблица A (Stud, Gr) содержит данные о студентах факультета X, а B (Stud, Room) – данные о студентах разных факультетов, проживающих в общежитии Y. Операция естественного соединения C = AB определит таблицу C (Stud, Gr, Room), в которой окажутся данные о студентах факультета X, проживающих в общежитии Y.

В переводной литературе соединение часто неправильно называют объединением. Нужно четко понимать разницу между этими операциями.

Как описывалось выше, семантическое моделирование и нормализация данных из рассматриваемой проблемной области позволяют получить в итоге структуру БД в виде набора связанных друг с другом таблиц. Операция соединения позволяет в процессе работы связать разные таблицы для получения необходимых данных.

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

Представленный набор операций фигурировал в ранних статьях Э.Кодда. Многие авторы предлагали и другие операции, ориентированные для удобства использования и связи исходных операций. Обоснование и подробное обсуждение различных вариантов дополнительных операций имеет в большей степени теоретический интерес. Приведем в качестве примера несколько таких операций [2].

1. Переименование (RENAME). Операция позволяет присвоить другое имя атрибуту отношения.

2. Полусоединение (SEMIJOIN). Операция определяется выражением

C = π<A> (AB), где <A> - список атрибутов отношения A. Иными словами, выделяются кортежи A, нашедшие соответствие в отношении B.

3. Полувычитание (SEMIMINUS). Операция определяется выражением

C = A -π<A> (AB), где <A> - список атрибутов отношения A. В противоположность полусоединению находятся те кортежи отношения A, которые не нашли соответствия в отношении B.

4. Расширение (EXTEND). Операция позволяет добавить новое поле в отношение, определяя его значение выражением над другими полями.

5. Обобщения (SUMMARIZE). Для каждой группы кортежей с одним и тем же значением некоторых атрибутов создается результирующий кортеж (например, сумма числовых значений).

Операции реляционной алгебры могут использоваться последовательно. Рассмотрим снова отношения по поставщикам S (S#, Sn, Scity), изделиям P (P#, Pn, Pcity, W) и поставкам SP (S#, P#, Q). Здесь S# - номер поставщика, Sn – его имя, Scity – место проживания, P# - номер изделия, Pn – его наименование, Pcity – место хранения, W – вес, Q – объем поставки. Требуется найти имена и места проживания поставщиков, поставляющих детали веса более 10.

Можно получить результат следующими операциями:

A = σ W>10 (P)

B = ASP

C = BS

R = π Sn, Scity (C)

Здесь оба соединения – естественные, то есть первое производится по атрибуту P#, а второе по атрибуту S#. Мы получили пример “программы” в виде последовательности операций реляционной алгебры.

На основе операций реляционной алгебры были предложены и реализованы такие экспериментальные языки запросов, как IS/1 и PRTV. Языки реляционной алгебры являются процедурными языками, так как реализуют заданную последовательность операций, приводящих к результату. Вместе с тем эти языки более высокоуровневые по сравнению с языками, ориентированными на обработку отдельных записей.

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

 




Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 753; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.