Смелик В.В. – Управление данными – Лекции
.pdfПреподаватель: Смелик Владимир Валерьевич
Литература: не рекомендуется
Термины и определения
Методы измерения информации:
1.Статистический(стохастический). Измеряет количество информациив сообщении как уменьшение энтропии (неопределённости) приёмника.
2.Понятийный (семантический). Измеряет количество информациив сообщении как степень приращения тезауруса приёмника. Тезаурус — словарь предметной области с более-менее однозначнойтрактовкой терминов предметной области.
3.Полезностный(прагматический). Определяет количество информации в сообщении как изменение расстояния до цели.
Любые оценки зависят от получателя информации, то есть являются субъективными. Информациикак объекта реального мира не существует.
Данные — сведения об объектах и явлениях окружающегомира, выраженныев форме, доступной для восприятия, передачи и хранения.
Тип данных — способ представленияданных в оперативнойили постоянной памяти, а так же связанные с ним методы обработки.
Типы:
•Boolean. 1 бит.
•Byte. 1 байт, 256 значений.
•Short. 2 байта. Ushort (unsigned short). 2байта, только неотрицательные числа.
•Long, ulong. 4байта.
•Sreal (short real). 2байта с плавающей точкой.
•Decimal. В каждом байте хранится по 2 цифры от 0 до 9.
•String. Определяет строку заданной длины, инициированнуюпробелами (изначально заполняется пробелами).
•CString. Строка с терминатором. Терминатор — специальныйсимвол, обозначающийконец данных в строке. Можем использоватьна один байт меньше, чем заявленно.
•PString. Строка фиксированнойдлины с указателем длины в левом байте.
•VChar (varchar).Строка переменной длины.
•Blob "помойка". Тип переменно длины для хранения двоичных данных, неиндексируемых.
Домашнее задание: дать описание типам date и time.
Домашнее задание на листе А4. В левом верхнем углу: ФИО, группа, дата исполнения, номер задания.
Компоненты информационнойсистемы
1.Данные.
2.Средства ввода, вывода и передачи данных.
3.Средства хранения.
4.Средства обработки.
5.Потребительинформационногопродукта.
Термины баз данных
Атрибут — неотъемлемоесвойство объекта, без которого он не может ни существовать, ни мыслиться. Объекты одного класса описываютсяодними атрибутами.
Домен — определяет потенциальноемножество значений данного типа (атрибута) и, возможно, правила обработки.
Схема отношения — именованноемножество пар, "имя атрибута – имя домена".
Схема базы данных — набор именованныхсхем отношений.
Кортеж (соответствующийданной схеме отношений) — множество пар, "имя атрибута – значение", которые содержат одно вхождение каждого имени атрибута, принадлежащегосхеме отношений.
Отношение — множество кортежей, соответствующиходной схеме отношения.
Фундаментальныесвойства отношений:
1.Отсутствие кортежей-дубликатов. Первичный ключ — атрибут (или набор атрибутов), однозначно определяющийкортеж отношений.
2.Отсутствие упорядоченностикортежей.
3.Отсутствие упорядоченностиатрибутов.
4.Атомарностьзначений атрибутов.
Домашнее задание: изобразить соответствиеклассическихтерминов теории БД их коммерческиманалогам.
Проектированиереляционныхбаз данных
1.Каким образом отразить объекты предметной области в абстрактные объекты базы данных?
Из каких отношений должна состоять база данных?
Какие атрибуты должны быть у этих отношений?
2.Как обеспечить эффективностьвыполнения запросов к базе данных?
Методы проектирования:
•Проектированиес использованиемнормализации(математический подход).
•Проектированиес учётом смысла предметной области (семантическое проектирование). Заключаетсяв построении ER-диаграмм (entity – relationship). Набор сущностей, между которыми установлена связь. Элементы:
Сущность. На диаграмме прямоугольник. В заголовке имя сущности. Под именем сущности указываютсяатрибуты, которые характеризуютэту сущность. Ключевые атрибуты выделяются.
Связь. Отображаетсялинией. Прерывистаялиния обозначает необязательностьсвязи. На концах связи может отражаться мощность связи (указываетсяколичество экземпляровсущности, с которыми может быть установлена связь (в чаще всего либо 1, либо много (трезубец))). При необходимостисвязи подписываются.
Между сущностями устанавливаетсясвязь. Связей может быть несколько. Связь может связывать одну и ту же сущности.
Пример. Предметная область "Брачные отношения".
Моногамный брак. У одного мужчины может быть только одна жена, при этом он не может не иметь жену. То же и про жён.
Домашнее задание: придумать предметную область для диаграммы и дополнить её текстовым описанием.
Порядок построения ER-диаграмм
Шаги:
1.Предметная область полно и непротиворечивоописываетсяна естественномязыке.
2.Из описания предметной области выбираются все существительные.
3.В списке существительныхвыбираются синонимы и оставляется только один вариант.
4.Из описания предметной области выбираются все глаголы.
5.Каждое существительноеотображаетсяна ER-диаграмме в виде отдельной сущности.
6.В соответствиис описанием предметной области между сущностями проводятся связи; глаголы используютсядля подписи связей; определяетсямощность концов связи.
7.Выявляются пары сущностей, между которыми установлена связь "один к одному"; пары объединяютсяв сущность с новым именем; объединённыесущности становятся атрибутами новой сущности.
8.Выполняетсяпроверка на наличие избыточных связей; лишние связи удаляются.
9.На ER-диаграмме выявляются сущности-сироты и удаляются.
Правила преобразованияER-диаграммы в схему базы данных
Шаги:
1.ВыполняетсямодификацияER-диаграммы для исключения связей "многие ко многим".
2.Каждая сущность превращаетсяв таблицу. Имя сущности становится именем таблицы, имена атрибутов становятся именами столбцов.
3.Каждая таблица заполняется полем-идентификатором, являющимся первичным ключом.
4.Для каждой связи в таблице, находящейсяна стороне "много" добавляетсяполе, являющееся внешним ключом, по типу соответствующееполю первичного ключа в таблице на стороне связи "один".
5.Атрибуты всех таблиц типизируются.
6.Выделяютсяи детализируютсядомены; в описании таблиц типы заменяются на домены.
Домашнее задание: построить ER-диаграмму предметной области "почтовый адрес". Должен быть почтовый индекс, населённые пункты и улицы должны иметь деление на категории (село, город, улица, проспект).
АрхитектураСУБД
Функциональныеэлементы СУБД:
1.Физическое размещение данных в оперативнойи/или постоянной памяти.
2.Механизм поиска требуемых данных.
3.Система поддержанияфизической и логической целостности данных.
4.Подсистема обмена данными.
5.Система авторизациии прав доступа.
6.Система распараллеливанияпользователей(или сериализации транзакций).
Структуры внешней памяти:
1.Файлы данных.
2.Файлы индексов. Индекс — специальнаяструктура внешней памяти, в которой хранятся упорядоченныессылки на строки в файле данных.
3.Журнал. Журнал — это файл с данными о том, кто, что и когда делал с данными.
4.Служебные структуры СУБД.
Физическая организация файлов данных
В файле таблицы хранятся примерно так (А — атрибут, З — запись):
А1,А2,А3,А4 З1,З2,З3,З4 З5,З6,З7,З8
Проблема в том, что приходится искать каждый разделитель (запятые) для перехода к нужной строке. А давайте сделаем строки фиксированнойдлины
(T — длина):
А1:T1,А2:T2,А3:T3,А4:T4 З1,З2,З3,З4_________
З5,З6,З7,З8_______
Операции с данными: add, del, put (edit).
Домашнее задание: придумать предметную область, составить ER-диаграмму и схему базы данных по рисунку.
Жёсткие диски читают и записывают минимум кластерами (1–2 МБ), поэтому файлы данных разбиваютсяна страницы в соответствиис размером кластера. Есть 2 вида страниц:
1.Корневые (R). Хранятся указатели на задействованныестраницы данных. В конце указываетсяидентификаторследующей корневой страницы. Размер файлов ограничиваетсяколичествомбайтов, выделеннымна указатели.
2.Страницы данных (D). У каждой строки есть идентификатор.
Домашнее задание: построить ER-диаграмму и схему базы данных для магазинного чека.
Индексы (ключи)
Индексы — структуры внешней памяти, обеспечивающиеупорядоченный доступ к данным.
Таблицы данных не отсортированы. Для того, чтобы обеспечить доступ с сортировкойстроятся индексы.
Один из популярных алгоритмов построения индексов —би-дерево. Бидерево — сбалансированноесильно ветвистое дерево во внешней памяти. Сбалансированность — свойство дерева, подразумевающее, что расстояние от корня до любого листа одинаково. Сильная ветвистость подразумевает, что у каждого отца может быть много детей. В узлах дерева хранятся пары «значение ключа (ЗК) – номер страницы индекса (НСИ)». Правило: ЗК1,НСИ1 ≤ ЗК2,НСИ2 ≤ … ≤ ЗКn,НСИn. В листе пары «значение ключа (ЗК), номер страницы данных (НСД)». Правило: ЗК1,НСД1 < ЗК2,НСД2 < … < ЗКn,НСДn. Прелесть такой структуры в том, что она самоорганизующаяся.
Занесение новой записи (шаги):
1.Поиск листовой страницы (поиск по ключу).
2.Считывание листовой страницы в буфер оперативнойпамяти. Буфер оперативнойпамяти должен быть больше, чем размер страницы.
3.Помещаем на место в странице новую запись.
4.Если в странице осталось свободное место, она выталкиваетсяиз буфера. Если превышен размер страницы, то выделяется буфер под новую страницу, и выполняетсярасщеплениестраницы примерно пополам. После этого выполняетсявыталкиваниебуферов и считывание родительскойстраницы. В родительскуюстраницу добавляетсякорректирующаязапись, анализируетсястраница на предмет переполнения, и действия с ней выполняютсяпо вышеописанномуалгоритму.
Домашнее задание: ещё раз сделать ER-диаграмму и схему базы данных для чека.
Домашнее задание: сделать ER-диаграмму и схему базы данных для таблицы с фотографи (р/с — расчётный счёт, еи — единица измерения).
Домашнее задание: сделать ER-диаграмму и схему базы данных склада рефератов.
Журналы — служебные файлы систем хранения данных, содаржащиезаписи о выполненныхоперациях модификацииданных. Операции: добавление и удаление (изменение — удаление старых и добавление новых).
Транзакция — операция модификациибазы данных, характеризующаяся логической неделимостьюи переводящаябазу данных из одного согласованногосостояния в другое согласованноесостояние.
Признаки согласованногосостояния:
1.Отсутствие экземпляровсущностей. являющихся сиротами. Все значения внешних ключей должны присутствоватьв первичных ключах тех сущностей, на которые они ссылаются.
2.Данные должны соответствоватьограничениям, накладываемым доменами.
Проблемы, связанные с транзакциями:
1.Проблема грязного чтения. Чтение изменяющейсяв данный момент
таблицы.
2.Проблема повторного чтения. Внутри одной транзакции выборка по заданным условиям должна быть идентична, сколько бы раз не повторялась.
3.Проблема смертельногообъятия (проблема конкурирующегодоступа). Транзакция 1 читает таблицу 1 и изменяет таблицу 2, а транзакция 2 читает таблицу 2 и изменяет таблицу 1. Транзакция 1 захватывает таблицу 1, а транзакция 2 захватываеттаблицу 2, и они ждут, когда освободитсядругая таблица для записи. Ждут друг друга бесконечно.
Журнал содержит поля:
1.Транзакция. Идентификатор, внешний ключ.
2.Когда произошло.
3.Где. Какая таблица.
4.Что. Операция и значения.
Операторы для работы с транзакцией:
•BEGIN — оператор начала транзакции.
•COMMIT —оператор успешного завершения транзакции; операции из журнала полностью применяютсяк хранилищу данных.
•ROLLBACK —оператор отката транзакции; все операции из журнала должны быть отражены в хранилище данных в обратном порядке и с обратными операторами.
Сбои
Виды сбоев:
1.Жёсткий сбой. Характеризуетсяфизическим нарушением в хранилище данных. Приёмы защиты:
Базы данных и файлы журнала должны храниться на физически разных носителях.
Архивацияданных. Раз в неделю делается полный бэкап, а
каждый день бэкап только изменений в системе. Рекомендованнаяглубина бэкапа: 3 полных бэкапа.
2. Мягкий сбой. Характеризуетсяутратой содержимогооперативной памяти.
Домашнее задание: придумать предметную область на 7–9 сущностей и представить её в табличной форме, ER-диаграмме и схеме БД.
Темпаральные (временные) базы данных — это базы данных, в которых учитываетсявремя выполнения операций модификацииданных.
Домашнее задание: почтовый конверт.
Главное требование, предъявляемоек транзакциям — изолированность.
Сериализация транзакций — определениепорядка выполнения транзакций.
Метод упорядочениятранзакций:
1.Метод синхронизационныезахваты. Заключаетсяв том, что у каждой таблицы может быть проставленаметка, информирующаяо использованииэтой таблицы в транзакции. Выделяют 2 режима захвата таблиц: S-Shared (совместный, можно захватывать в режиме S, но не X), X-eXclusive (монопольный, нельзя захватывать).
2.Гранилированныесинхронизационныезахвати. Проставляетметки не только у таблиц, но и у картежей (записей). Объект любого уровня может быть захвачен в режиме S или X. Перед захватом объекта должен быть выполнен захват объекта верхнего уровня в режимах IS (Intended for Shared lock), IX (Intended for eXclusive lock)и SIX (Shared with Intended for eXclusive lock).
3.Предикатныезахваты. Захватываетобъекты, удовлетворяющие заданному условию.