Шпоры по БД

1. Данные. Источники данных. Предметная область, объект, атрибуты, ключевой элемент, запись, файл.

Данные – это представление фактов и идей в формализованном виде, пригодном для передачи и переработки в некотором процессе, информация – это смысл, который придается данным при их представлении. Обработка данных – выполнение систематических последовательных действий с данными.

Предметная область (ПО) – совокупность информационной среды и технологии обработки информации, ориентированная на конечного пользователя.

Объект – понятие, характеризующееся данными предметной области.

Атрибут – элемент данных объекта.

Ключевой атрибут – тот, по которому можно определить другие (ассоциативная память).

Запись данных – совокупность связанных атрибутов.

Файл данных – упорядоченная совокупность записей (плоский файл – однородные записи).

2. Файловая система. Универсальные методы доступа. Примеры. Недостатки.

В нач. стадии развития инф-ки прикладные инф-ые системы работали напрямую с файлами данных. Программы об-ки занимались ведением конкретных файлов, т.е. в основном, доб-ем, уд-ем, корр-ой данных, сорт-ой и выдачей. Шагом вперед стало использование унив. методов доступа к данным, которые опр-ли их структуру на нижнем уровне. Системы, поддер-е эти методы, называются Системами Управления Файлами – СУФ, они вкл-ся в ОС. Но унив. прогр. работают с ! пред-ем данных или же с фикс. числом представлений. Пример: СУФ в ОС RTE фирмы HP, где исп-ся 6 форматов файлов (типы 1-6).

Гл. недостаток файловой сист.: короткие записи, ориен-ые на решение частных задач, приводят к избыточности, возн-ей из-за повт-я одних и тех же данных в разн. файлах. Это приводит к противоречивости данных, кот-я усугубл. слабым контролем дост-ти данных. Также к недостаткам ФС отн-ся: огр-е разделения данных, огр-е по доступности, сложность в управлении.

Попытка борьбы с прот-ю путем объединения записей приводит к сл. Непр-ям: ведение длинных записей - трудоемкая задача, система данных на длинных записях отличается крайне низкой гибкостью, при недостаточности средств защиты возможен несанкционированный доступ к данным, процесс восстановления данных сложен и требует значительного времени, стоимость и сложность в эксплуатации таких систем крайне высока.

3. База данных (БД). Достоинства и недостатки по сравнению с файловой системой.

Df: Под базой данных (БД) будем понимать совокупность связанных данных конкретной предметной области, в которой определения данных и отношений между ними отделены от процедур.

Основное отличие баз данных от систем на основе файлов состоит в том, что эти системы имеют несколько назначений и несколько представлений о данных, а базы данных – несколько назначений и одно представление о данных.

Базы данных призваны ликвидировать неприятности, присущие системам на основе файлов, и они это успешно делают, но по сравнению с ними они тоже имеют некоторые недостатки. Объективно – это довольно высокая стоимость и необходимость специальной подготовки, что в простейших случаях хранения данных представляется излишним. Субъективно – пользователь нередко хочет видеть данные в своих файлах без посредников в виде СУБД. Кроме того, при переходе к использованию БД наблюдается снижение ответственности исполнителя, что влияет на достоверность данных. В свою очередь, достоверность трудно контролировать из-за отсутствия избыточности. Возникают проблемы и с защитой данных, для этого требуются специальные мероприятия.

4. Систмы управления базами данных. Требования к СУБД.

Df: Система управления данными (СУБД) – комплекс программно-аппаратных средств, обеспечивающих доступ к БД и управление данными.

Требования к СУБД

• Эффективное выполнение функций ПО.

• Минимизация избыточности.

• Предоставление непротиворечивой информации.

• Безопасность.

• Простота в эксплуатации.

• Простота физической реорганизации.

• Возможность централизованного управления.

• Упрощение приложений.

5. Администратор БД.

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

Администратор БД – это сотрудник, выполняющий следующие функции:

• координация проектирования, реализации и ведения БД;

• обслуживание пользователей БД;

• определение структуры данных и правила доступа;

• не только реализация, но и оценка перспективы и формирование требований исходя из особенностей ПО.

Отсюда следует, что АБД должен быть не только профессионалом в области БД, но должен знать ПО, а также должен уметь общаться с людьми различных категорий: пользователями, программистами, администрацией.

6. Независимость данных

Изм-я в формате, распол-и данных или спос-х доступа к ним могут повлиять на прикл. прогр., что повлечет, как минимум, перекомпил. Т. к. предметная область задачи меняется, такие изм-ия приходится делать не так уж редко. Незав-ть данных закл-ся в том, что программист всегда знает каков формат данных, где они расп-ся, как к ним обратиться, т. е. его программа не зависит от изм-я в расположении, формате данных и способе доступа к ним.

Существует 2 уровня независимости. Процесс проект-я начинается с установления концептуальных требований, формируется концептуальная модель (КМ) которая представляет объекты и их связи без указания способов физического хранения. Затем КМ переводится в модель данных, совместимую с выбранной СУБД, возникает логическая модель (ЛМ). Наконец, ЛМ отображается на физическую память: метод доступа и расположение. Это внутренняя (физическая) модель (ФМ).

1-й уровень независимости – логическая независимость,

2-й уровень – физическая независимость.

При наличии независимости на 1-м уровне решения, принимаемые в КМ, не зависят от выбираемой СУБД. Незав-ть на 2-м уровне озн-ет, что реализация ЛМ не зав. от метода доступа, расп-я данных, типа ЭВМ, харак-х ФМ. Т.о. для обесп-я незав-ти в КМ не должны учитываться особ-ти СУБД, а методы доступа к данным д. б. скрыты.

Df: Данные незав., если сущ-т возм-ть норм-го функ-я БД при изменениях как со стороны КМ, так и со стороны ФМ, т. е. обеспеч-ся логическая и физическая незав-ть.

7. Модель, схема, отношение. Связь с СУБД.

Df: Модель данных – средство для определения логического представления физических данных, относящихся к ПО.

Модель данных характеризуется тремя компонентами: структура данных, предназначенная для представления точки зрения пользователя на БД, множество допустимых операций, выполняемые в структуре данных, составляющее основу языка данных модели, ограничения для контроля целостности.

Схема – средство, с помощью которого определяется модель. Кроме модели, схема содержит дополнительную информацию.

Df: СУБД – набор программных средств, позволяющих обеспечить пользователя языковыми средствами манипулирования данными – языки определения данных (ЯОД) и языки манипулирования данными (ЯМД), обеспечить поддержку моделей пользователя, обеспечить реализацию ЯОД и ЯМД: отображение операций над данными в операции над физическими данными, обеспечить защиту (полномочия) и целостность (согласованность) данных.

Обычно рассматриваются три основных модели представления данных, которые отличаются ограничениями, накладываемыми на представление данных и виды связей. Это, в порядке хронологии появления, иерархическая, сетевая и реляционная модели. В настоящее время развивается и четвертый тип модели – объектно-ориентированный.

8. Иерархическая модель данных. Оценка. Применение.

ИМ данных – модель с отношением подчиненности между данными.

Определение. Отношение объектов ИМ определяется следующими правилам: А подчинено Б  Б не подчинено А; А подчинено Б  (А подчинено В)  (Б тождественно В), где А, Б, В – объекты. Другими словами, иерархическая модель реализуется древовидной структурой в которых объекты модели представлены узлами дерева. Данное определение не позволяет определить пустую модель, модель, состоящую из одного лишь корня. Кроме того, здесь допускается несвязная модель.

ИМ обл-т след. св-ми: Существует корень. Узел содержит атрибуты, исходный и зависимый узлы находятся в отношении «непосредственный предок и потомок». Узлы доб-ся гориз-но и верт-но. Потомок соединен !-ой связью с предком. Предок может иметь несколько потомков. Доступ к данным производится через предка. Может существовать множество экземпляров узла.

Достоинства: Простота в понимании и использовании. Обеспечение определенного уровня независимости по сравнению с файловыми системами. Простота обслуживания и оценки характеристик, так как благодаря дисциплине удаления нет нужды заботиться о висячих ссылках. Высокая скорость доступа.

Недостатки: Основной недостаток – невозможность реализации отношения «многие к многим» в рамках одной базы данных. Реализация такого отношения на основе двух БД затрудняет управление.

9. Сетевая модель данных. Предл-я КОДАСИЛ. Оценка. Прим.

БД делится на области, те – на записи, состоящие из полей. С другой стороны, БД состоит из наборов, а те – из записей.

Df: Запись – иерархия, обр-я из простейших (атомарных) эл-в данных, их групп и повт-ся групп. Тип записи – мн-во допустимых экз-в записи. Тип набора – мн-во экз-в набора. К набору отн-ся записи – члены набора и владелец набора. Записи-влад. (члены) могут быть одноврем. владельцами (членами) других наборов.

Доступ к члену набора производится только через владельца.

Огр-я КОДАСИЛ: 1. Тип набора опр-т отн-е 1:М между типом записи-влад. и типом записи-члена. 2. Экз-р типа записи-члена может участвовать только в 1 экз-ре типа набора.

В сетевой модели отношение записей явл. графом, не имеющ. циклов. Иерарх-я модель м. б. предст. как частн. сл-й СМ.

Наборы в сетевой БД могут иметь атрибуты. Атрибут «обязательный-необязательный» опр-т поведение СУБД при удалении вл-ца экз-ра набора. В I-м случае члены набора удал-ся при удал-и вл-ца, во II-м случае – нет. Атрибут «автоматический-ручной» опр-т способ включения в набор. В I сл-е члены набора вкл-ся в нужный экз-р набора автом-ки, во II-м случае в нужный набор запись включается по команде из прикладной программы.

В сетевой БД сущ. понятие текущего состояния. В сведения о текущем сост-и входит структ. базы, структ. наборов, связи и т.п. Эти данные позв-ют эфф-но осуществлять доступ к данным, контр-ть их целостность. Недост. такого централиз. предст-я – трудности с изменением структуры данных.

(+): 1. реализуется отношение M:N, 2. выс. произв-ть.

(-).: трудность реорган. БД, 2. в процессе исп-я из-за некорр. удалений, сбоев и т.п. накапливается мусор – данные, к которым нет доступа, 3. слабая выразит. языка запросов.

10. Реляционная модель данных. Основные понятия.

Принципы: 1. незав-ть данных на логич-м и физич-м уровнях – стремл-е к незав-ти; 2.создание структурно простой модели – стремл-е к коммуникаб-ти; 3. исп-е концепции языков высокого уровня для описания опер-й над порциями инф-и – стремл-е к обр-ке множ. Каждая ед. инф-ии в реляц. БД (РБД) ассоц-ся с уникальной 3-ой: именем отн-я, знач-м ключа, именем атрибута.

Модель данных – это не только структура, это комбинация, по крайней мере, 3-х сост-х: 1. набора типов структур данных; 2. набора операторов или правил вывода, применимых к правильным типам данных; 3. набора общих правил целостности, который определяет множество непротиворечивых состояний БД и множество изменений ее состояний.

Структурная часть реляц-й модели состоит из след. компонент: 1. доменов – совок-ти однотипных зн-й данных; 2. отношений неопред-го порядка – концептуально представл. табл-ми; 3. атрибутов – атомарных данных, опр-х столбцы таблицы; 4. кортежей – строк таблицы; 5. потенц-х (возможных) ключей – атрибутов, однозначно опр-х кортеж в отношении; 6. первичных ключей – для отношения это один из возможных ключей.

Обрабатывающая часть сост. из операторов выбора, проекции, соединения и т.п., которые преобразуют отношения в отношения.

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

Критерии, по которым СУБД можно отнести к реляционным. Эти критерии следующие: 1. СУБД должна поддерживать таблицы без видимых пользователю навигационных связей; 2. язык манипулирования данными должен обеспечивать минимальную возможность реляционной обработки, то есть включать операторы выбора, проекции и соединения.

11. Алгебра, схема, отношение. Ключ.

Df: Схема – конечное множество имен атрибутов {A₁, A₂ , ..., A_n}. Каждому имени A_i ставится в соответствие домен D_i: D_i=dom(A_i). Обозначим D = _i=1ⁿ D_{i .}

Df: Отношение r со схемой R – конечное множество отображений {t₁, t₂ , ..., t_n} из R в D, причем, для каждого отображения t r и каждого i значение атрибута A_i берется из D_i . Эти отображения называются кортежами.

Df: Ключ отношения со схемой R – это K={B₁, B₂ , ..., B_m }  R со свойством: для  t₁, t₂  r, t₁t₂,  BK такой, что t₁(B) t₂(B), то есть не существует двух различных кортежей, имеющих одинаковое значение на всех атрибутах K (t₁(K) t₂ (K)). Ключи, явно перечисленные в схеме, называются выделенными, остальные – возможными, один из выделенных называется первичным.

Df ключа слишком широкое, оно допускает существование подключа, то есть если K – ключ отношения r(R) и KKR, то K тоже ключ.

Df: Ключ отношения r(R) – это подмножество K R такое, что для  t₁, t₂  r, t₁t₂, следует t₁(K) t₂ (K) и ни одно K K не обладает этим свойством.

Если K R, удовлетворяющее первому определению ключа, в качестве собственного подмножества содержит ключ, оно называется суперключом.

12. Изменение отношений во времени

Размещение дополнительной информации производится операцией добавления ADD(r; A₁=d₁, A₂=d₂ , ..., A_n=d_n). Вариант для фиксированного порядка атрибутов: ADD(r; d₁, d₂, ..., d_n).

Возможные ошибки при добавлении: 1. кортеж не соответствует схеме; 2. некоторые значения не принадлежат доменам; 3. есть совпадения по ключу.

В любом случае операция не выполняется.

Удаление информации производится операцией DEL(r; A₁=d₁, A₂=d₂ , ..., A_n=d_n) или DEL(r; d₁, d₂ , ..., d_n). Если K={B₁, B₂ , ..., B_m } – ключ отношения, для удаления достаточно записать DEL(r; B₁=b₁, B₂=b₂ , ..., B_m=b_m).

Возможная ошибка – отсутствие удаляемого кортежа. Заметим, что допускается удаление последнего кортежа, то есть, пустое отношение может существовать.

Модификация информации производится операцией изменения. Пусть {C₁, C₂, ... C_p}  {A₁, A₂, ... A_n}. Тогда CH((r; A₁=d₁, A₂=d₂ , ..., A_n=d_n ; C₁=c₁, C₂=c₂ , ..., C_n=c_p) или, в случае ключа, CH((r; B₁=b₁, B₂=b₂ , ..., B_m=b_m ; C₁=c₁, C₂=c₂ , ..., C_n=c_p).

Того же эффекта можно достигнуть послед-м удалением изменяемого кортежа и добавлением нового. Поэтому ошибки модификации представляют собой объед-е ошибок удал-я и доб-я.

13. Операции реляционной алгебры: булевы операции

К БО отн-ся оп-ии , , -. Пусть r, s – отношения со схемой R. Они могут рассматриваться как подмножества множества всех кортежей, определяемых этой схемой, поэтому к ним применимы булевские операции. t – кортежи, тогда:

rs ={t|(tr)&(ts)};

rs ={t|(tr)(ts)};

r–s ={t|(tr)&(ts)}.

Заметим, что r  s = r - (r - s), то есть достаточно лишь двух операций.

Обозначим dom(R) множество всех кортежей над атрибутами из схемы R и их доменами: dom(R) = {t(d₁ d₂ … d_n)| d_i dom(A_i)}. Дополнение отношения определим как r(R): r = dom(R) - r(R). Но если какой-либо атрибут из R имеет бесконечный домен, r будет тоже иметь бесконечное число кортежей, то есть по определению не будет отношением.

Df: Пусть r(A₁, A₂,..., A_n) – отношение, D_i = dom(A_i). Тогда активный домен атрибута A_i относительно r – это множество adom(A_i,r) = {dD_i |  tr, t(A_i)=d).

Пусть adom(R,r) – множество всех кортежей над атрибутами из R и их активными доменами относительно r: adom(R, r) = {t(d₁ d₂ … d_n)| d_i adom(A_i, r)}. Тогда активным дополнением r будем называть . Так как число значений атрибутов, принадлежащих кортежам из r, конечно, то активное дополнение всегда будет отношением.

14. Операции реляционной алгебры: выбор; свойства выбора.

Пусть A – это некот. атрибут отн-я r(R) и a – эл-т мн-ва значений, кот. может принимать отобр-е t на этом атрибуте. Выб. из отн-я r те кортежи, для кот-х отобр-е t на A приним. зн-е a, и рез-т обозн. через _{A = a}(r). Это унарная оп-я (она прим-ся к 1 отн-ю), в результате которой у нас появляется новое отношение r (R).

Df: Выбором _{A = a}(r) называется отношение r (R) = _{A = a}(r){tr | t(A)=a}.

Утв. 1. _{A = a} ^ _{B = b}(r)  _{A = a}(_{B = b}(r)) = _{B = b}(_{A = a}(r))  _{B = b} ^ _{A = a}(r).

Док.: _{A = a}(_{B = b}(r)) = _{A = a}({tr | t(B) = b}) = { t{tr | t(B) = b}| t (A) = a } = { tr | t(A) = a, t(B) = b} = { tr | t(B) = b, t(A) = a} = { t {tr | t(A) = a}|t (B) = b } = _{B = b}({tr | t(A) = a}) = _{B = b}(_{A = a}(r)).

Обозн.: _{A = a} ^ _{B = b}  _{A = a, B = b} . Положим X = (A, B, C,…), а x = (a, b, c,…), тогда оператор выбора можно обозначить _{X = x}. .

Утв. 2. _{A = a}(rs) = _{A = a}(r)  _{A = a}(s), где {,,– }.

Док.: _{A = a}(rs) = _{A = a}({t | tr, ts}) = {t{t | tr, ts} | t (A) = a} = = {t | tr, t(A) = a}  {t | ts, t(A) = a} = _{A = a}({t | tr})  _{A = a}({t | ts}) = _{A = a}(r)  _{A = a}(s). Анал. Док-ся =-ва _{A = a}(rs)=_{A = a}(r)_{A = a}(s) и _{A = a}(rs) = = _{A = a}(r) _{A = a}(s).

Зам.: Опер-и выбора и активного дополнения не перестановочны (не коммутируют). Можно показать, что _{A = a}(r)  _{A = a} ( ).

15. Операции реляц. алгебры: проекция; свойства проекции.

Пусть r – отношение со схемой R, X  R.

Df: Проекцией _X(r) называется отношение r(X) = _X(r)  {t(X) | tr }.

Это унарная операция, но в отличие от операции выбора, которая выдаёт строки по заданным условиям, она выдаёт столбцы, заголовки которых перечислены в X.

Если Y – собственное подмножество X, то _Y(_X(r)) = _Y(r). В общем случае, если X₁  X₂ … X_m, то _X1 ^ _X2 ^…^ _Xm = _X1.

Утв.: Операторы проекции и выбора перестановочны:

_X(_{A = a} (r)) = _{A = a} (_X(r)).

Док: _X(_{A = a} (r)) = _X({tr | t(A) = a}) = {t(X) | t{tr| t (A) = a}} =

= {t(X) | tr, t (A) = a} = _{A = a} ({t(X) | tr}) = _{A = a} (_X(r)).

16. Операции реляционной алгебры: соединение.

Df: Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение r  s = q(RS) = {t(RS)|  t_r  r, t_s  s : t_r = t(R), t_s = t(S)}.

Если RS = {B₁B₂…B_l} = , то соединение r  s, результатом которого является множество кортежей t(A₁A₂…A_k C₁C₂…C_m), таких, что t(A₁A₂…A_k) r и t(C₁C₂…C_m) s, называется декартовым произведением отношений r и s и обозначается r  s.

17. Операции реляционной алгебры: свойства соединения

Св. 1. Имитация выбора: _A=a(r) для отн-я r(R) через : Опред. s(A) с ! кортежем t : t(A) = a. => rs=_A=a(r). Док.: rs={t|t_rr, t_s s, t_r=t(R), t_s=t(A)}={t|t_rr, t_r=t(R), t(A)=a}={t | t(A) = a } = _A=a(r).

Св. 2. Обобщ. оп-я выбора. s(A) с k кортежами t₁, t₂,…, t_k: t_i(A) = a_i и a_i  dom(A), i =1…k. => r  s = _A=a1(r) _A=a2(r) … _A=ak(r).

Св. 3. Коммут-ть оп-ра соед-я: Df => r  s = s  r.

Св. 4. Ассоц-ть оп-ра соед-я: Для q, r, s (q  r)  s = q  (r  s). => посл-ть соединений можно записывать без скобок.

Df: Кортежи t₁, t₂,…, t_n соединимы на S, если сущ. кортеж t на R : t_i = t(S_i) для каждого i = 1, 2,…, n. Кортеж t наз-ся рез-том соединения кортежей t₁, t₂,…, t_n на S.

Св. 5. Многократные соед-я: r₁(S₁), r₂(S₂),…, r_n(S_n), R = S₁S₂… S_n. Обозн. S – посл-ть схем S₁, S₂,…, S_n. Пусть t₁, t₂,…, t_n – посл-ть кортежей, t_i r_i, i = 1, 2,…, n. Если кортежи t_i i=1...n соед-мы на S с рез-м t, то t_i=t(S_i). => t_i=1ⁿ r(S)_i. Обратно: t_i=1ⁿ r(S)_i, => сущ. t_i i=1…n в r(S) : t_i=t(S_i), т.е. они соед-мы на S с рез-том t. => _i=1ⁿ r(S)_i сост. из рез-тов соед-й соединимых на S кортежей t₁ и t₂ .

Лемма. Отн-е _i=1ⁿ r_i сост. из всех корт. t, кот. явл-ся рез-том соед-я соед-х на S кортежей t_i r_i, i = 1, 2,…, n.

Не каждый кортеж каждого отношения может войти в соединение.

Df: Отн-я r₁, r₂,…, r_n полностью соед-мы, если каждый кортеж в каждом отн-и явл. членом списка соед-х на S кортежей.

Св. 7. Соединение проекций: q(RS), r = R(q), s = S(q), q′= r  s. Если t  q, то t(R)r, t(S)  s  tq′, т.е. q′ q. При q′ = q отношение разложимо без потерь на схемы R и S.

Св. 8. Идемпотентность процедур проекции и соединения: r = _r(q), s = _s(q), q = r  s (двойное применение соединения проекций). Пусть T = RS, тогда _T(r) = _T(_R(q)) = _T(q) = _T(_S(q)) = _T(s). Сл-но, r и s полностью соединимы т.к. для любого t_r из r сущ. t_s из s такой, что t_r(T) = t_s(T) и обратно.

Св. 9. r(R), r(R), s(S) => (rr)  s = (r  s)(r  s).

18. Операции реляционной алгебры: деление

Df: r(R), s(S), SR, R = R - S. => r, разделенное на s – это отношение r(R)={t | t_ss t_rr: t_r(R)=t & t_r(s)=t_s}. r– частн. от дел. r на s, что обозн-ся r= rs. Т.е. rs – это макс. подмнож. r мно-ва _R (r) : r  s  r. Соед-е здесь – дек-во произведение.

П ример:

Деление может быть использовано для сбора информации о пилотах, управляющими самолетами из множества q или для поиска тех пилотов, которые умеют управлять самолетами из множества s

19. Постоянные отношения. Переименование атрибутов.

Определение. Пусть A₁,…,A_n – различные атрибуты, а c_i является константой из dom(A_i) для 1 i  n, тогда с₁ : А₁,…,с_n : A_n - постоянный кортеж с₁,…,с_n над схемой А₁А₂…А_n.

П