Понятие данных
 Скачать 1.56 Mb.
|
|
Теоретико-множественные: объединение, вычитание, пересечение, прямое (декартово) произведение Специальные: выбор (селекция), проекция, соединение, деление Основные операции: Операция конкатенации (CONCAT или || или +) - выполняет сцепление двух строковых операндов и образует строковое выражение. Арифметические операции можно использовать с операндами числовых типов. Префиксная операция + (унарный плюс) не изменяет значение своего операнда. Префиксная операция – (унарный минус) изменяет знак не нулевого операнда. Бинарные операции (/, *, +, -) определяют сложение, вычитание, умножение и деление, соответственно. Операции над датой и временем. Значения даты и времени можно увеличивать, уменьшать и вычитать. Эти операции могут включать десятичные числа – продолжительность. Продолжительность – это число, представляющее интервал времени. По типу производимых действий различают следующие операции: идентификация данных и нахождение их позиции в БД; выборка (чтение) данных из БД; включение (запись) данных в БД; удаление данных из БД; модификация (изменение) данных БД. Реляционное исчисление: Запрос – формула некоторой формально-логической теории; описывает свойства желаемого результата. Ответ – множество объектов из области интерпретации (базы данных), на котором истинна формула, соответствующая запросу. 11. Реляционная алгебра: теоретико-множественные операции. Реляционная алгебра предоставляет: • средства для записи и интерпретации выражений; • набор операций, использующихся в качестве операндов отношения и возвращающих в качестве результата также отношение, т.е. представляет операции над отношениями: R опц R дает R Теоретико-множественные операции: • объединение, • вычитание, • пересечение, • прямое (декартово) произведение Даны два множества S1 и S2. Объединением этих множеств является множество S, элементы которого принадлежат первому множеству S1 и (или) второму множеству S2: S = S1 U S2 = {s|s є S1 и/или s є S2} В реляционной модели данных рассматривается объединение множеств – доменов и/ или отношений. Свойство совместимости по объединению: - Простые домены считаются совместимыми по объединению, если они состоят из элементов одного типа. - Два отношения считаются совместимыми по объединению, если: • Оба отношения имеют одно и то же множество атрибутов; • Одноименные атрибуты двух отношений определены на совместимых по объединению доменах. 1) Объединением двух отношений r1(R1) и r2 (R2), совместимых по объединению, называется отношение s = r1 U r2, для которого: А) схема отношения совпадает с R1 или R2; Б) реализация отношения представляет множество кортежей, принадлежащих реализации r1 и (или) r2. Свойства операции: Коммутативна – r1 U r2 ≡ r2 U r1; Ассоциативна – r1 U (r2 U r3) ≡ (r1 U r2) U r3 ≡ r1 U r2 U r3 2) Вычитанием двух отношений r1(R1) и r2 (R2), совместимых по объединению, называется отношение s = r1-r2, для которого: А) схема отношения совпадает с R1 или R2; Б) реализация отношения представляет множество кортежей, принадлежащих реализации r1, за исключением тех, которые имеются в r2. Свойства операции: Не коммутативна, не ассоциативна 3) Пересечением двух отношений r1(R1) и r2 (R2), совместимых по объединению, называется отношение s = r1 ∩ r2, для которого: А) схема отношения совпадает с R1 или R2; Б) реализация отношения представляет множество кортежей, содержащихся и в r1 и в r2 Свойства операции: Коммутативна – r1 ∩ r2 ≡ r2 ∩ r1; Ассоциативна – r1 ∩ (r2 ∩ r3) ≡ (r1 ∩ r2) ∩ r3 ≡ r1 ∩ r2 ∩ r3 4) Декартовым произведением двух отношений r1(R1) и r2 (R2), схемы отношений которых не имеют одноименных атрибутов, т.е. R1 ∩ R2 = 0 (отношения r1 и r2 могут иметь разные схемы, не обязательно совместимые по объединению; перед выполнением операции необходимо переименовать атрибуты в схемах отношений так, чтобы имена всех атрибутов были разными), называется отношение s = r1 x r2, для которого: А) схема отношения определяется сцеплением (объединением) схем R1 и R2 Б) реализация отношения представляет множество кортежей, которое получается путем сцепления каждого кортежа из r1 с каждым кортежем из r2. Свойства операции: Коммутативна – r1 x r2 ≡ r2 x r1; Ассоциативна – r1 x (r2 x r3) = (r1 x r2) x r3 = r1 x r2 x r3 12. Реляционная алгебра: специальные операции. Специальные операции определены только для нормализованных отношений. В этих операциях наряду с самими отношениями участвуют и их атрибуты. В отношениях реляционной модели данных к атрибутам можно обращаться или по имени, или по их позиции в схеме отношений. К специальным операциям реляционной алгебры относятся: • Проекция • Выбор (селекция) • Соединение • Деление 1) Проекцией отношения r(R), R = {Ai}, на некоторый список имен атрибутов (подмножество атрибутов) L из R, L c R называется отношение s = ∏ L (R), для которого: o Схема отношения определяется списком L; o Реализация отношения есть множество кортежей, полученных из кортежей отношения r, путем вычеркивания элементов, соответствующих атрибутам R – L, и исключением дубликатов. Проекция дает вертикальное подмножество отношения. Эта операция является унарной операцией на отношениях, т.е. в этой операции участвует только одно отношение. Свойства: если Y c X c R, то ∏ Y (∏ X (r)) ≡ ∏ Y (r) 2) Выбором из отношения r(R) по условию F называется отношения s = σ F (r), для которого: • Схема отношения совпадает со схемой R; • Реализация отношения есть множество кортежей из r, удовлетворяющих условию F. Условие (предикат) F записывается в соответствии со следующими правилами: • В качестве операндов могут быть указаны атрибуты отношения и /или константы; • В качестве операция могут быть использованы операции отношения (равно, не равно и т.д.) и логические операции (^, v, ¬) Операция выбора осуществляет ограничение кортежей исходного отношения до значений, удовлетворяющих условию. Выбор дает горизонтальное подмножество отношения. Свойства: коммутативность – σ F1 (σ F2 (r)) = σ F1 (σ F1 (r)) = σ F1^ F2 (r); дистрибутивность относительно операций: γ = (∩, U, -): σ F (r γ s) = σ F (r) γ σ F (s). 3) Соединение: естественное и по условию (θ - соединение). Естественным соединением отношений r 1 (R 1 ), R 1 = XY, и r 2 (R 2 ), R 2 = YZ, где Y – общее подмножество атрибутов из R 1 и R 2 , определенных на одних и тех же доменах, называется отношение s(R) = r 1 |><| r 2 , для которого: Схема отношения R = R 1 U R 2 = XYZ Реализация отношения есть множество кортежей {t}, для которых ∏ XY (t) є r 1 и ∏ YZ (t) є r 2 Внутреннее, или замкнутое естественное соединение – такое, для которого результат операции содержит только те кортежи из двух отношений, которые имеют совпадающие значения одноименных атрибутов. Внешнее, незамкнутое естественное соединение: • Левое r 1 ><| r 2 : включает результат операции естественного соединения, дополненный и теми кортежами из r 1 , для которых нет соответствующих кортежей из r 2 ; для таких кортежей значения атрибутов, унаследованных от r 2 , устанавливаются как пустые значения. • Правое r 1 |>< r 2 : включает результат операции естественного соединения, дополненный и теми кортежами из r 2 , для которых нет соответствующих кортежей из r 1 ; для таких кортежей значения атрибутов, унаследованных от r 1 , устанавливаются как пустые значения. • Полное внешнее r 1 >< r 2 : включает результат операции естественного соединения, дополненный и кортежами из r 1 , для которых нет соответствующих кортежей из r 2 , и кортежами из r 2 , для которых нет соответствующих кортежей из r 1 , с пустыми значениями соответствующих унаследованных атрибутов. Соединением отношений r 1 (R 1 ) и r 2 (R 2 ) по условию θ называется отношение s(R) = r 1 |><| 𝐴𝐴θB r 2 , для которого: • Схема отношения R = R 1 U R 2 ; • Реализация отношения есть множество кортежей, полученных сцеплением кортежей из r 1 и r 2 , удовлетворяющих условию A θ B Если в качестве операции θ используется операция =, такое соединение по условию называется эквисоединением. 4) Деление. Даны два отношения r 1 (R 1 ) и r 2 (R 2 ), для которых R 2 c R 1 и R 2 не пусто. Частным от деления отношения r 1 на отношение r 2 называется отношение s(R) = r 1 / r 2, для которого: • Схема отношения R = R 1 – R 2 • Реализация отношения есть множество кортежей t таких, что для всех u i є r 2 существует v j є r 1 такой, что v j (R 1 – R 2 ) = t и v j (R 2 ) = u i Примеры написания запросов к БД на языке реляционной алгебры: 13. Реляционное исчисление: понятие предиката, вхождение переменных; атомы, правильно построенная функция. Выражение реляционного исчисления с переменными-кортежами. Реляционное исчисление лежит в основе декларативного подхода к формулировке запроса к БД, суть которого: • Запросу к БД соответствует формула некоторой формально-логической теории, которая описывает свойства желаемого результата. • Ответом на запрос служит множество объектов из области интерпретации (которой является БД), на котором истинна формула, соответствующая запросу. В качестве такой формально-логической теории используется теория исчисления предикатов первого порядка, в которой формула задается в виде предиката. Даны некоторые попарно не пересекающиеся произвольные множества D1, D2, …, Dn, Di ∩ Dj = 0 для любых I ≠ j, и переменные х 1 , х 2 , …, х n , принимающие значения из соответствующих множеств: x i є D i для любых i. Переменные х 1 , х 2 , …, х n называют предикатными переменными. Множества D1, D2, …, Dn образуют область интерпретации предиката. Предикатом (предикатной функцией) называется функция Р (х 1 , х 2 , …, х n ), принимающая одно из двух значений – истина (1) или ложь (0). Кванторы: X (f(x)) означает, что для всех значений икс из области интерпретации формула f(x) имеет значение «истина» X (f(x)) означает, что существует по крайней мере одно значение икс из области интерпретации, для которого формула f(x) имеет значение «истина». Использование кванторов определяет понятие свободного и связанного вхождения переменных в предикатной формуле. Вхождение переменной t в формулу ψ связано, если переменная t находится в формуле ψ в подформуле, начинающейся кванторами или , за которыми непосредственно следует переменная t; тогда о кванторе говорят, что он связывает переменную t. В остальных случаях t входит в ψ свободно. Различают два вида реляционного исчисления: 1. Реляционное исчисление с переменными-кортежами, для которого областями определения переменных являются отношения базы данных, т.е. допустимым значением каждой переменной является кортеж некоторого отношения 2. Реляционное исчисление с переменными на доменах, для которого областями определения переменных являются домены, определяющие множество допустимых значений атрибутов. Реляционное исчисление с переменными-кортежами. Переменные-кортежи должны удовлетворять определенной схеме отношения R. Правильно построенная формула (wff – well formulated formula) определяет результаты отбора: выбираются те кортежи, для которых wff дает значение 1. Правила построения wff ψ (t): 1. Основой формулы являются атомы, которые могут иметь значения 0 или 1. Существует три типа атомов формулы wff ψ(t): 1) Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; t – некоторая переменная – кортеж, удовлетворяющая схеме R. Тогда r(t) – атом; означает, что t есть кортеж в отношении r (т.е. формула истинна, если t принадлежит r). 2) Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; u и v – переменные – кортежи из отношения r(R) (т.е. и u и v принадлежат r); θ – арифметическая операция сравнения; А, В – атрибуты схемы отношения R, определенные на доменах, сравнимых по операции θ; тогда u[A] θ v [B] – атом. 3) Пусть u – переменная-кортеж из отношения r(R) (т.е. u принадлежит R); θ – арифметическая операция сравнения; А, В – атрибуты схемы отношения R, определенные на доменах, сравнимых по операции θ; с – константа из домена, на котором определен атрибут В; тогда u[A] θ с (или с θ’ u[A] ) – атом. * u[A] означает «значение переменной-кортежа u по атрибуту А». 2. Формула реляционного исчисления ψ(t), а также свободные и связанные вхождения переменных определяются по следующим рекурсивным правилам: 1) Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутых в атоме, являются свободными. Т.е. r(t) утверждает, что переменная-кортеж t является кортежем отношения r(R). 2) Если x(R) – переменная-кортеж из отношения r со схемой R; ψ(x) - формула, в которой переменная «х» имеет свободное вхождение; тогда x(R) (ψ(x)) – формула, в которой вхождение переменной «х» становится связанным квантором . Данная формула утверждает, что существует хотя бы один кортеж «х», в отношении r(R), такой, что при подстановке его в формулу ψ(x) вместо всех свободных вхождений «х» получим значение «истина». 3) Если x(R) – переменная-кортеж из отношения r со схемой R; ψ(x) - формула, в которой переменная «х» имеет свободное вхождение; тогда х (R) (ψ(x)) – формула, в которой вхождение переменной «х» становится связанным квантором . Данная формула утверждает, что для всех кортежей «х» из отношения r(R) при подстановке их в формулу ψ(x) вместо всех свободных вхождений «х» получим значение «истина». 4) Если ψ(x) и φ (х) – формулы, тогда ¬ ψ(x), ψ(x) ^ φ (х), ψ(x) v φ (х) – тоже формулы. Вхождения переменной «х» в эти формулы остаются свободными или связанными – такими, какими были в ψ(x) или φ (х) соответственно. 5) Если ψ(x) – формула, то (ψ(x)) – тоже формула; вхождение переменной «х» остается свободным или связанным – таким, каким оно было в ψ(x). 6) Ничто иное не является формулой. При вычислении формул используется порядок старшинства операций, определяемый правилами построения формулы: А) атомы, в которых могут быть использованы арифметические операции сравнения Б) кванторы В) отрицание ¬ Г) операция «И» ^ Д) операция «ИЛИ» v Скобки используются для изменения порядка вычисления формулы. Выражение реляционного исчисления с переменными-кортежами имеет вид: {t(R) | ψ(t)}, где t – переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая свободное вхождение в формулу ψ(t); ψ(t) – правильно построенная формула. Интерпретация выражения реляционного исчисления: множество кортежей t, удовлетворяющих схеме отношения R, таких, для которых правильно построенная формула ψ(t) истинна. Реляционное исчисление с переменными на доменах. Здесь также строится правильно определенная формула, основой которой являются атомы. Отличие состоит в том, что здесь областью определения являются домены. Атомы имеют следующий вид: 1) r(x 1 , x 2 , …, x n ), где r – отношение, удовлетворяющее схеме R (A 1 , A 2 , …, A n ), и каждое x i есть константа или переменная на домене; 2) u θ v, где u, v – константы или переменные, определенные на доменах, совместимых по арифметической операции сравнения θ. Формула реляционного исчисления ψ(t), а также свободные и связанные вхождения переменных определяются аналогично исчислениям с переменными-кортежами. 14. Языки манипулирования данными: общая характеристика, обзор языков, история развития SQL. Язык, в котором можно (по крайней мере) моделировать исчисление с переменными-кортежами, либо, что равносильно, реляционную алгебру или исчисление с переменными на доменах, называется полным. Обзор языков: ISBL (Information System Base Language) – «чистый» язык реляционной алгебры. Разработан в исследовательском центре фирмы IBM в Питерли (Англия) для использования в экспериментальной системе PRTV (Peterlee Relational Test Vehicle). Нет агрегатных операций, а также средств для вставки, удаления и модификации кортежей SEQUEL (Structured English Query Language) – разработан в 1974 г. в исследовательской лаборатории IBM в Сан-Хосе; использует реляционную алгебру, но имеет синтаксис, напоминающий реляционное исчисление с переменными-кортежами. В 1976 г. на базе переработанной версии языка SEQUEL/2 корпорация IBM выпустила прототип СУБД, получивший название System R. Назначение этой пробной версии состояло в проверке осуществимости реляционной модели. Помимо прочего, важнейшим из результатов выполнения этого проекта можно считать разработку собственного языка SQL (Structured Query Language). QUEL – язык реляционного исчисления с переменными-кортежами, разработан в Калифорнийском университете в Беркли в конце 70-х г.г. для реляционной СУБД INGRES. Включает широкий спектр операторов реляционного исчисления с переменными-кортежами, агрегатные функции. Более структурирован, чем SQL QBE (Query-By-Example) – язык исчисления с переменными на доменах; разработан в Исследовательском центре IBM в Йорктаун-Хейтсе. Предназначен для работы с терминала. Включены агрегатные функции SQL (Structured Query Language) – язык, ориентированный на отображение; описывается отображение известного атрибута или множества атрибутов в искомый атрибут или множество атрибутов. Первая коммерческая СУБД – ORACLE (конец 70-х г.г.) |