Эволюция систем баз данных
 Скачать 236.08 Kb.
|
|
1. Унарные операции В терминах таблиц отношение включает строки, столбцы и строку заголовков столбцов. Поэтому естественными унарными операциями, преобразующим отношение-операнд в отношение-результат, являются операции 1) выборки (выборки строк), 2) проекции (выборки столбцов), 3) переименования атрибутов (переименования столбцов). Дадим формальные определения операций выборки, проекции и переименования атрибутов: σ〈P〉r(S)={t(S)|t∈r&P〈S〉t} π〈S' 〉r(S)≡r[S' ]={t' (S' )|∃t∈r(t[S' ]=t')},S'⊆S ρ〈φ〉r(S)={t ̃(S ̃ ) | ρ〈φ-1〉 t ̃∈r},φ:S→S ̃,φ-1: S ̃→S Из определений операций следуют следующие свойства. Группа 1. Соотношения мощностей: 1) | σ〈P〉r| ≤ |r| 2) | π〈S' 〉r| ≤ |r| 3) | ρ〈σ〉r| = |r| Примечание. Операция выборки связана с вычеркиванием кортежей. Из результата проекции дубликаты кортежей исключаются. Переименование атрибутов не изменяет числа кортежей • Группа 2. Свойства идемпотентности: 1) σ〈P〉σ〈P〉r = σ〈P〉r 2) π〈S'〉 π〈S'〉r= π〈S'〉r 3) ρ〈φ2〉 ρ〈φ1〉r(S) = ρ〈 φ2 ◦ φ1〉r, φ1 : S → S1 , φ2: S1 → S2 , φ2 ◦ φ1: S → S2 Примечание. Все кортежи результата однократной выборки удовлетворяют условию выборки. Повторная проекция не связана с вычеркиванием столбцов. Двукратное переименование атрибутов сводится к однократному переименованию с функцией переименования, равной композиции исходных функций переименования (аналог свойства идемпотентности) • Группа 3. Свойства монотонности: 1) r1 ⊆ r2 ⇒ σ〈P〉r1 ⊆ σ〈P〉r2 2) r1 ⊆ r2 ⇒ π〈S'〉r1 ⊆ π〈S'〉r2 3) r1 ⊆ r2 ⇒ ρ〈φ〉r1 ⊆ ρ〈φ〉r2 Примечание. Все три унарных оператора монотонны • 2. Бинарные операции Бинарные теоретико-множественные операции объединения, пересечения и разности применяются к двум отношениям с одной и той же схемой. Результатом является отношение с той же схемой, что и у операндов (табл. 2.6): 1) r1(S) ∪ r2(S) = {t(S) | t ∈ r1 ∨ t ∈ r2} – объединение 2) r1(S) ∩ r2(S) = {t(S) | t ∈ r1 &t ∈ r2} – пересечение 3) r1(S) \ r2(S) = {t(S) | t ∈ r1 &t ∉ r2 } – разность Бинарными операциями типа произведения являются операции декартова произведения и естественного соединения: r1(S1) × r2(S2) = {t(S1 ∪ S2) | t[S1] ∈ r1 & t[S2] ∈ r2}, S1 ∩ S2 = ∅ Операции возвращают отношение со схемой, равной объединению схем операндов. В декартово произведение попадают комбинации всевозможных пар кортежей, так как схемы операндов не пересекаются. В естественное соединение попадают лишь те кортежи операндов, которые совпадают на пересечении схем отношений. Такие кортежи называются соединимыми. Декартово произведение является частным случаем естественного соединения в случае непересекающихся схем отношений. Из определений операций следуют следующие свойства. Группа 1. Соотношения мощностей: 1) |r1 ∪ r2| ≤ |r1| + |r2| 2) |r1 ∩ r2| ≤ min(|r1|, |r2|) 3) |r1 \ r2| ≤ |r1| 4) |r1 × r2| = |r1| · |r2| 5) |r1 ⋈ r2 | ≤ |r1| · |r2| Примечание. При объединении отношений дубликаты кортежей исключаются. При декартовом произведении все кортежи соединимы, так как схемы операндов не пересекаются. При естественном соединении в общем случае не все кортежи соединимы • Группа 2. Свойства группы представлены в табл. 2.9. Знаками «+» и «−» обозначены случаи, когда операция обладает и не обладает соответствующим свойством. Для декартова произведения обладание свойством идемпотентности не формулируется (что обозначено знаком «⊖»), так как в этом случае декартово произведение не определено. 9. Внутреннее соединение Увы 10. Левое, правое и полное внешние соединения. Их основное свойство. Увы 11. Реляционное исчисление и полнота реляционной алгебры. Полнота реляционной алгебры. Сигнатура реляционной алгебры, так, как она была введена выше, содержала операции, производные от других операций, и в этом смысле была избыточной. Если из сигнатуры алгебры исключить операции типа произведения (× и ⋈), то в результате запроса, формулируемого в виде выражения реляционной алгебры над отношениями базы данных с оставшимися операциями (σ, π, ρ,∪,∩, \) могут быть получены результирующие отношения со схемами, с точностью до переименования атрибутов являющимися подмножествами или совпадающими со схемами исходных отношений. Такого ограниченного набора операций для практики явно не достаточно. Возникает вопрос о полноте набора операций реляционной алгебры. Если проанализировать определения операций реляционной алгебры, то можно заметить, что все они с точностью до обозначений определяются в виде выражений вида «множество кортежей над такой-то схемой, удовлетворяющих такому-то предикату»: {t(S) | f(t)} Здесь f – некоторый предикат над переменным кортежем t. Это выражение обозначает отношение r(S), которое состоит из всех кортежей t(S), для которых f(t) истинно. Можно задаться вопросом, не будут ли получены новые запросы-отношения из базы данных, если в качестве предиката f в таких выражениях использовать произвольный предикат, включающий логические связки ∀ (квантор общности, или всеобщности), ∃ (квантор существования) и ¬,&,∨ (отрицание, конъюнкция, дизъюнкция)? (Такие выражения с произвольным предикатом f , выраженным в элементарных высказываниях, использованных при определении операций реляционной алгебры, называются выражениями исчисления кортежей.) Можно показать, что нет. Таким образом, полнота реляционной алгебры понимается в том смысле, что система запросов, построенная на основе реляционной алгебры (запрос – это выражение реляционной алгебры над множеством отношений базы данных D), приводит к тому же множеству допустимых запросов D+, что и система запросов, построенная на основе исчисления кортежей (запрос – это выражение исчисления кортежей над D). 12. Базовая структура оператора select. Оператор select – один из наиболее важных и самых распространенных операторов SQL. Он позволяет производить выборки данных из таблиц и преобразовывать к нужному виду полученные результаты. При его помощи можно реализовать сложные и громоздкие условия отбора данных из различных отношений. Оператор select – средство, которое полностью абстрагировано от вопросов представления данных, что помогает сконцентрировать внимание на проблемах доступа к данным. Операции над данными производятся в масштабе наборов данных, а не отдельных записей. Оператор select реализует вычисление выражений как реляционной, так и псевдореляционной алгебры. В последнем случае в результирующем отношении могут появляться дублирующиеся кортежи. Потенциально опасными с точки зрения возникновения дубликатов кортежей являются операции проекции и объединения. Поэтому в этих операциях вводятся специальные опции, управляющие режимом исключения дубликатов. Базовая структура оператора select включает следующие фразы и достаточно проста: select выбрать такие-то атрибуты from из таких-то отношений where с таким-то условием выборки кортежей В самом общем случае базовая структура Select должна выглядеть следующим образом: Select выбрать такие-то атрибуты From из таких-то отношений Where с такими-то условиями выборки кортежей Таким образом, выбираем мы атрибуты из схемы отношений (заголовки некоторых столбцов), при этом указывая, из каких отношений (а их, как видно, может быть несколько) мы производим нашу выборку и, наконец, на основании каких условий мы останавливаем свой выбор на тех или иных кортежах. Важно заметить, что ссылки на атрибуты происходят с помощью их имен. Таким образом, получается следующий алгоритм работы этого базового оператора Select: 1) запоминаются условия выборки кортежей из отношения; 2) проверяется, какие кортежи удовлетворяют указанным свойствам. Такие кортежи запоминаются; 3) на выход выводятся перечисленные в первой строчке базовой структуры оператора Select атрибуты со своими значениями. (Если говорить о табличной форме записи отношения, то выведутся те столбцы таблицы, заголовки которых были перечислены как необходимые атрибуты; разумеется, столбцы выведутся не полностью, в каждом из них останутся только те кортежи, которые удовлетворили названным условиям.) Рассмотрим пример. Пусть нам дано следующее отношение r1, как фрагмент некой базы данных книжного магазина:
 Пусть также нам дано следующее выражение с оператором Select: Select Название книги, Автор книги From r1 Where Цена книги > 200; Результатом этого оператора будет следующий фрагмент кортежа: (Мобильник, С. Кинг). 13. Выражение операций реляционной алгебры. Операция выборки Операция выборки реализуется оператором select * from имя_отношения where условие_выборки Здесь звездочка означает выбор всех атрибутов из схемы отношения. Условие выборки записывается в виде логического выражения со связками not, and, or. Ссылки на атрибуты производятся по их именам. Условие выборки может содержать предикаты в следующих формах: 1) выражение {< | <= | = | < > | >= | >} выражение 2) выражение [not] between выражение1 and выражение2 3) выражение is [not] 4) строковое_выражение [not] like шаблон [escape ′escape_символ′] 5) выражение [not] in (выражение,..) 6) выражение [not] in (подзапрос) 7) выражение {< | <= | = | < > | >= | >} {all | any} (подзапрос) 8) exists (подзапрос) Форма 1 предиката применяется для выражений любого типа, за исключением BLOB – крупных двоичных объектов. Форма 2 предиката с оператором [not] between (между) является сокращением следующего условия: [not] (выражение1 <= выражение and выражение <= выражение2) Форма 3 предиката предназначена для тестирования null-значений. Форма 4 предиката с оператором like (похожий) позволяет отбирать строки по шаблону с использованием следующих символов замещения. 1. % – любая строка из нуля или более символов. Например, конструкция like ′%t%′ соответствует любым строкам, содержащим хотя бы один символ ′t′. 2. _ – любой одиночный символ. Например, конструкция like ′a_′ соответствует двухсимвольным строкам, начинающимся с символа ′a′. 3. {[символ-символ] | [символ. . . ]} – любой одиночный символ, содержащийся в указанном диапазоне или последовательности символов. Например, конструкция like ′ [b-d]at′, как и like ′bcd]at′, соответствует строкам ′bat′, ′cat′, ′dat′. Конструкция like ′[ [ ]′ соответствует символу ′[′. 4. {[^символ-символ] │ [^символ…]} – любой одиночный символ, не содержащийся в указанном диапазоне или последовательности символов. Например, конструкция like ′[^0-9]%′ соответствует любым строкам, первый символ которых не является цифрой. Если символ замещения ′%′ или ′_′ необходимо сам по себе включить в шаблон, то следует или заключить его в квадратные скобки, или определить escape-символ (то есть символ перехода) и использовать его перед символом замещения. Например, следующие конструкции соответствуют двухсимвольным строкам, начинающимся с символа подчеркивания: like ′[_]_′ like ′/_ _′ escape ′/′ like ′!_ _′ escape ′!′ Форма 5 предиката соответствует предикату принадлежности элемента списку. Форма 6 предиката отличается от формы 5 тем, что вместо списка задается подзапрос, возвращающий один столбец (но не одну строку, так как требуется однотипность данных). Например, следующий запрос выводит список студентов, получивших к моменту запроса хотя бы одну оценку отлично: Студенты(NЗК, Ф, И, О) Сессия(NЗК, МнемоП, Оценка) select * from Студенты where NЗК in (select NЗК from Сессия where Оценка = 5) Здесь в результирующем запросе поля из таблицы Сессия не используются и поэтому можно использовать подзапрос, а не соединение. Форма 7 предиката позволяет сравнивать выражения со всеми (all) или некоторыми (any) значениями, возвращаемыми в подзапросе. В частности, следующие предикаты эквивалентны: выражение in (подзапрос)выражение = any (подзапрос) Форма 8 предиката проверяет подзапрос на пустоту. С помощью этого предиката последний пример может быть записан в виде Студенты(NЗК, Ф, И, О) Сессия(NЗК, МнемоП, Оценка) select * from Студенты where exists(select * from Сессия where NЗК = Студенты.NЗК and Оценка = 5) Здесь подзапрос является примером так называемого коррелированного подзапроса, поскольку условие выборки в подзапросе зависит от текущей анализируемой записи внешнего запроса. Указывать конкретные столбцы в подзапросе предиката exists смысла не имеет. Операция проекции Операция проекции реализуется оператором select [distinct] список_имен_атрибутов from имя_отношения Здесь необязательная опция distinct задает режим исключения дубликатов кортежей. Если результат проекции гарантированно не содержит дубликатов кортежей или дубликаты допустимы, то из соображений производительности опцию distinct лучше не указывать, например: Успеваемость(NЗК, Семестр, МнемоП, Оценка, Дата) select NЗК, Семестр, МнемоП, Оценка from Успеваемость Здесь первые три возвращаемые атрибута образуют ключ отношения. Поэтому опция distinct становится излишней. Запрос возвращает исходное отношение Успеваемость, в котором опущен атрибут Дата. Операция переименования атрибутов Операция переименования атрибутов на языке структурированных запросов осуществляется довольно просто. А именно воплощается в действительность следующим алгоритмом: 1) в списке имен атрибутов фразы Select перечисляются те атрибуты, которые необходимо переименовать; 2) к каждому указанному атрибуту добавляется специальное ключевое слово as; 3) после каждого вхождения слова as указывается то имя соответствующего атрибута, на которое необходимо поменять имя исходное. Таким образом, с учетом всего вышесказанного, оператор, соответствующий операции переименования атрибутов, будет выглядеть следующим образом: Select имя атрибута 1 as новое имя атрибута 1, … From имя отношения; Операция переименования атрибутов заключается в добавлении ключевого слова as и нового имени атрибута после исходного имени атрибута в списке имен атрибутов фразы select, например Успеваемость(NЗК, Семестр, МнемоП, Оценка, Дата) select NЗК as [№ зачетки], Семестр, МнемоП as МнемоПредмета, Оценка, Дата from Успеваемость Имена атрибутов, содержащие не буквенно-цифровые символы, в частности пробелы, заключаются в квадратные скобки (в некоторых СУБД). Как и унарные операции, операции бинарные также имеют свою реализацию на языке структурированных запросов или SQL. Итак, рассмотрим осуществление на этом языке уже пройденных нами бинарных операций, а именно – операций объединения, пересечения, разности, декартового произведения, естественного соединения, внутреннего и левого, правого, полного внешнего соединения. |