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: Схема – конечное множество имен атрибутов {A1, A2 , ..., An}. Каждому имени Ai ставится в соответствие домен Di: Di=dom(Ai). Обозначим D = i=1n Di . Df: Отношение r со схемой R – конечное множество отображений {t1, t2 , ..., tn} из R в D, причем, для каждого отображения t r и каждого i значение атрибута Ai берется из Di . Эти отображения называются кортежами. Df: Ключ отношения со схемой R – это K={B1, B2 , ..., Bm } R со свойством: для t1, t2 r, t1t2, BK такой, что t1(B) t2(B), то есть не существует двух различных кортежей, имеющих одинаковое значение на всех атрибутах K (t1(K) t2 (K)). Ключи, явно перечисленные в схеме, называются выделенными, остальные – возможными, один из выделенных называется первичным. Df ключа слишком широкое, оно допускает существование подключа, то есть если K – ключ отношения r(R) и KKR, то K тоже ключ. Df: Ключ отношения r(R) – это подмножество K R такое, что для t1, t2 r, t1t2, следует t1(K) t2 (K) и ни одно K K не обладает этим свойством. Если K R, удовлетворяющее первому определению ключа, в качестве собственного подмножества содержит ключ, оно называется суперключом. | 12. Изменение отношений во времени Размещение дополнительной информации производится операцией добавления ADD(r; A1=d1, A2=d2 , ..., An=dn). Вариант для фиксированного порядка атрибутов: ADD(r; d1, d2, ..., dn). Возможные ошибки при добавлении: 1. кортеж не соответствует схеме; 2. некоторые значения не принадлежат доменам; 3. есть совпадения по ключу. В любом случае операция не выполняется. Удаление информации производится операцией DEL(r; A1=d1, A2=d2 , ..., An=dn) или DEL(r; d1, d2 , ..., dn). Если K={B1, B2 , ..., Bm } – ключ отношения, для удаления достаточно записать DEL(r; B1=b1, B2=b2 , ..., Bm=bm). Возможная ошибка – отсутствие удаляемого кортежа. Заметим, что допускается удаление последнего кортежа, то есть, пустое отношение может существовать. Модификация информации производится операцией изменения. Пусть {C1, C2, ... Cp} {A1, A2, ... An}. Тогда CH((r; A1=d1, A2=d2 , ..., An=dn ; C1=c1, C2=c2 , ..., Cn=cp) или, в случае ключа, CH((r; B1=b1, B2=b2 , ..., Bm=bm ; C1=c1, C2=c2 , ..., Cn=cp). Того же эффекта можно достигнуть послед-м удалением изменяемого кортежа и добавлением нового. Поэтому ошибки модификации представляют собой объед-е ошибок удал-я и доб-я. |
13. Операции реляционной алгебры: булевы операции К БО отн-ся оп-ии , , -. Пусть r, s – отношения со схемой R. Они могут рассматриваться как подмножества множества всех кортежей, определяемых этой схемой, поэтому к ним применимы булевские операции. t – кортежи, тогда: rs ={t|(tr)&(ts)}; rs ={t|(tr)(ts)}; r–s ={t|(tr)&(ts)}. Заметим, что r s = r - (r - s), то есть достаточно лишь двух операций. Обозначим dom(R) множество всех кортежей над атрибутами из схемы R и их доменами: dom(R) = {t(d1 d2 … dn)| di dom(Ai)}. Дополнение отношения определим как r(R): r = dom(R) - r(R). Но если какой-либо атрибут из R имеет бесконечный домен, r будет тоже иметь бесконечное число кортежей, то есть по определению не будет отношением. Df: Пусть r(A1, A2,..., An) – отношение, Di = dom(Ai). Тогда активный домен атрибута Ai относительно r – это множество adom(Ai,r) = {dDi | tr, t(Ai)=d). Пусть adom(R,r) – множество всех кортежей над атрибутами из R и их активными доменами относительно r: adom(R, r) = {t(d1 d2 … dn)| di adom(Ai, 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){tr | 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({tr | t(B) = b}) = { t{tr | t(B) = b}| t (A) = a } = { tr | t(A) = a, t(B) = b} = { tr | t(B) = b, t(A) = a} = { t {tr | t(A) = a}|t (B) = b } = B = b({tr | 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(rs) = A = a(r) A = a(s), где {,,– }. Док.: A = a(rs) = A = a({t | tr, ts}) = {t{t | tr, ts} | t (A) = a} = = {t | tr, t(A) = a} {t | ts, t(A) = a} = A = a({t | tr}) A = a({t | ts}) = A = a(r) A = a(s). Анал. Док-ся =-ва A = a(rs)=A = a(r)A = a(s) и A = a(rs) = = 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) | tr }. Это унарная операция, но в отличие от операции выбора, которая выдаёт строки по заданным условиям, она выдаёт столбцы, заголовки которых перечислены в X. Если Y – собственное подмножество X, то Y(X(r)) = Y(r). В общем случае, если X1 X2 … Xm, то X1 X2 … Xm = X1. Утв.: Операторы проекции и выбора перестановочны: X(A = a (r)) = A = a (X(r)). Док: X(A = a (r)) = X({tr | t(A) = a}) = {t(X) | t{tr| t (A) = a}} = = {t(X) | tr, t (A) = a} = A = a ({t(X) | tr}) = A = a (X(r)). |
16. Операции реляционной алгебры: соединение. Df: Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение r s = q(RS) = {t(RS)| tr r, ts s : tr = t(R), ts = t(S)}. Если RS = {B1B2…Bl} = , то соединение r s, результатом которого является множество кортежей t(A1A2…Ak C1C2…Cm), таких, что t(A1A2…Ak) r и t(C1C2…Cm) s, называется декартовым произведением отношений r и s и обозначается r s. | 17. Операции реляционной алгебры: свойства соединения Св. 1. Имитация выбора: A=a(r) для отн-я r(R) через : Опред. s(A) с ! кортежем t : t(A) = a. => rs=A=a(r). Док.: rs={t|trr, ts s, tr=t(R), ts=t(A)}={t|trr, tr=t(R), t(A)=a}={t | t(A) = a } = A=a(r). Св. 2. Обобщ. оп-я выбора. s(A) с k кортежами t1, t2,…, tk: ti(A) = ai и ai 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: Кортежи t1, t2,…, tn соединимы на S, если сущ. кортеж t на R : ti = t(Si) для каждого i = 1, 2,…, n. Кортеж t наз-ся рез-том соединения кортежей t1, t2,…, tn на S. Св. 5. Многократные соед-я: r1(S1), r2(S2),…, rn(Sn), R = S1S2… Sn. Обозн. S – посл-ть схем S1, S2,…, Sn. Пусть t1, t2,…, tn – посл-ть кортежей, ti ri, i = 1, 2,…, n. Если кортежи ti i=1...n соед-мы на S с рез-м t, то ti=t(Si). => ti=1n r(S)i. Обратно: ti=1n r(S)i, => сущ. ti i=1…n в r(S) : ti=t(Si), т.е. они соед-мы на S с рез-том t. => i=1n r(S)i сост. из рез-тов соед-й соединимых на S кортежей t1 и t2 . Лемма. Отн-е i=1n ri сост. из всех корт. t, кот. явл-ся рез-том соед-я соед-х на S кортежей ti ri, i = 1, 2,…, n. Не каждый кортеж каждого отношения может войти в соединение. Df: Отн-я r1, r2,…, rn полностью соед-мы, если каждый кортеж в каждом отн-и явл. членом списка соед-х на S кортежей. Св. 7. Соединение проекций: q(RS), r = R(q), s = S(q), q′= r s. Если t q, то t(R)r, t(S) s tq′, т.е. q′ q. При q′ = q отношение разложимо без потерь на схемы R и S. Св. 8. Идемпотентность процедур проекции и соединения: r = r(q), s = s(q), q = r s (двойное применение соединения проекций). Пусть T = RS, тогда T(r) = T(R(q)) = T(q) = T(S(q)) = T(s). Сл-но, r и s полностью соединимы т.к. для любого tr из r сущ. ts из s такой, что tr(T) = ts(T) и обратно. Св. 9. r(R), r(R), s(S) => (rr) s = (r s)(r s). | 18. Операции реляционной алгебры: деление Df: r(R), s(S), SR, R = R - S. => r, разделенное на s – это отношение r(R)={t | tss trr: tr(R)=t & tr(s)=ts}. r– частн. от дел. r на s, что обозн-ся r= rs. Т.е. rs – это макс. подмнож. r мно-ва R (r) : r s r. Соед-е здесь – дек-во произведение. П ример: Деление может быть использовано для сбора информации о пилотах, управляющими самолетами из множества q или для поиска тех пилотов, которые умеют управлять самолетами из множества s |
19. Постоянные отношения. Переименование атрибутов. Определение. Пусть A1,…,An – различные атрибуты, а ci является константой из dom(Ai) для 1 i n, тогда с1 : А1,…,сn : An - постоянный кортеж с1,…,сn над схемой А1А2…Аn. П ( A1 | A2 | | An ) | c11 | c21 | | cn1 | c12 | c22 | | cn1 | | | | | c1k | c2k | | cnk | остоянное отношение над схемой А1А2…Аn представляется как множество кортежей. Пусть cij – константа из dom(Ai ) для 1 i n и 1 j k, тогда ↓ представляет отношение, которое обычно |