Рис. 3.12. Пример инвертированного файла
Поскольку записи инвертированного файла упорядочены по значению ключа Ki, то для поиска записей можно использовать любой из рассмотренных выше методов поиска в упорядоченном файле (например, бинарный поиск или В-дерево). Чтобы выполнить многоаспектный поиск по n ключам, необходимо построить п инвертированных файлов [17].
ГЛАВА 4. МАТЕМАТИЧЕСКИЕ ОСНОВЫ МАНИПУЛИРОВАНИЯ РЕЛЯЦИОННЫМИ ДАННЫМИ
4.1. Теоретические языки запросов
Для получения информации из отношений необходим язык манипулирования данными, способный выполнять соответствующие операции над отношениями. Наиболее важной частью ЯМД является его раздел для формулировки запросов. Поскольку запросы в общем случае представляют собой произвольные функции над отношениями, необходимо решить вопрос о требуемой выразительности языка запросов. Для исследования этого вопроса были разработаны три типа теоретических языков [2, 17]:
1)реляционная алгебра;
2)реляционное исчисление с переменными-кортежами;
3)реляционное исчисление с переменными-доменами.
Языки запросов первого типа – алгебраические языки – позволяют выражать запросы средствами специализированных операторов, применяемых к отношениям.
Языки запросов второго и третьего типов – языки исчисления – позволяют выражать запросы путем спецификации предиката, которому должны удовлетворять требуемые кортежи или домены.
Теоретические языки служат эталоном для оценки существующих реальных языков запросов [17]. Они были предложены Коддом для представления минимальных возможностей любого разумного языка запросов для реляционной модели данных. По своей выразительности все три языка оказались эквивалентными между собой.
4.1.1.Реляционная алгебра
Вэтом разделе на ряде примеров рассматриваются операции реляционной алгебры [11]. Для представления каждой операции будем использовать терминологию как алгебры, так и исчисления. Последняя базируется на системе понятий, использованной Коддом. Пять операций являются
83
основными:
проекция;
объединение;
разность;
декартово произведение;
селекция.
Другие часто используемые операции пересечения, соединения и деления можно выразить через пять основных операций. Ниже представлены отношения, используемые в примерах [11].
Описание каждого отношения состоит из имени отношения, за которым в круглых скобках следует список атрибутов (это описание называется интенсивналом или схемой отношения). Под описанием приведено некоторое заполнение кортежей отношения (экстенсионал отношения). В последующих примерах буквы R и S используются для обозначения отношений, а буквы А и В – для обозначения списка атрибутов (для простоты можно считать, что список состоит из единственного атрибута).
Операция проекции представляет собой выборку из каждого кортежа отношения значений атрибутов, входящих в А, и удаление из полученного отношения повторяющихся строк. В исчислении t обозначает «кортежную» переменную, значениями которой являются кортежи исходного отношения R, a t[A] – часть кортежа R с атрибутами из А. В соответствии с определением отношения неявно предполагается удаление дубликатов кортежей результирующего отношения.
Пример
Объединение
Для того чтобы объединение было возможным, отношения-операнды (R и S) должны быть совместимы по объединению, т.е. их атрибуты должны быть определены над совместимыми доменами.
Пример
84
Пример
Декартово произведение
Из обозначений видно, что операция декартова произведения осуществляется между кортежами отношений-аргументов, а результатом является конкатенация (обозначаемая ||) соответствующих кортежей. При этом
Отсюда следует, что результирующее отношение может иметь очень большие размеры. (На практике используется ограниченный вариант этой операции, называемый соединением.) Пусть
Тогда
85
Степень результирующего отношения равна 4 (2´ 2), а мощность – 8 (2´ 4).
Селекция (Ограничение)
В приведенном определении υ обозначает константу, а В – атрибут отношения R, отличный от А. Символ 6 используется для обозначения одной из операций сравнения (<, ≤, =, ≠, ≥, >).
Примеры
P[D1>D2]=Æ (пустое множество) поскольку в отношении отсутствуют кортежи, где D1 > D2.
Пересечение
Пересечение RÇS=R-(R-S), что соответствует области, отмеченной звездочкой на диаграмме Венна для операции разности.
Пример
Соединение
Алгебра |
|
|
|
Исчисление |
|
|
|||
R[AθB]S |
|
|
|
{(r||s)| r R s S (r[А]θs[В])} |
Как видно из определения, операция соединения имеет сходство с декартовым произведением. Однако здесь добавлено условие, согласно которому вместо полного произведения всех строк в результирующее отношение включаются только строки, удовлетворяющие определенному соотношению между атрибутами соединения (А, В) соответствующих отношений. Имеется несколько вариантов операции соединения:
a) тета- и эквисоединение. При этой операции А и В являются совместимыми атрибутами
86
соединения, а степень результирующего отношения равна сумме степеней отношений-операндов. Такое соединение называется θ-соединением (тета-соединением). В случае сравнения на равенство соединение называется экви-соединением;
б) естественное соединение. В этом случае атрибуты соединения имеют общие (одинаковые) домены, и после соединения один из атрибутов отбрасывается. Степень результирующего отношения на единицу меньше суммы степеней отношений-операндов;
в) композиция. Это соединение отличается от естественного тем, что из результирующего отношения удаляются оба атрибута соединения. Поэтому степень результирующего отношения на две единицы меньше суммы степеней отношений-операндов.
Примеры
Тета-соединение R[Q > A]S
При выполнении соединения необходимо для каждого кортежа из R взять значение атрибута Q и сравнить его со значением атрибута A из каждого кортежа S. В результате получим
Следует отметить, что кортеж < ω 50 1 b > отношения R не вошел в результирующее отношение.
Естественное соединение P[D3 = D4]Q
Деление
Атрибуты А и В являются совместимыми и/или общими атрибутами деления. Для упрощения объяснения можно считать R бинарным отношением, состоящим из А и дополнения А, которое
обозначается A и содержит атрибуты, отличные от А. Для каждого раздела из R[ A ], т.е. для каждого уникального кортежа r[ A ], необходимо выполнить следующее:
выбрать допустимые строки кортежей r[ A ] из R[ A ], обозначив полученное множество кортежей через T = gR(r[ A ]). Множество Т называется также множеством-образом;
в результирующее отношение входят кортежи r, для которых выполняется S[B]HgR(r[ A ]).
Примеры
P[D3÷D4]Q= (пустое множество), так как
87