Шпаргалка по "Информатике"

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

4. Реляционная модель БД. Основные виды связей между таблицами в реляционной БД

РМД некоторой предметной области представляет собой набор  отношений, изменяющихся во времени. При  создании информационной системы совокупность отношений позволяет хранить  данные об объектах предметной области  и моделировать связи между ними.

Отношение представляет собой двумерную таблицу, содержащую некоторые данные. Математически под N-арным отношением R понимают множество декартова произведения D₁ D_{2 …} D_n множеств (доменов) D_1, D₂, …, D_n ( ), необязательно различных:

R D₁ D_{2 …} D_n,

где D₁ D_{2 …} D_n – полное декартово произведение, т.е. набор всевозможных сочетаний из n элементов каждое, где каждый элемент берется их своего домена.

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

• Домен имеет уникальное имя (в пределах базы данных).
• Домен определен на некотором простом типе данных или на другом домене.
• Домен может иметь некоторое логическое условие, позволяющее описать подмножество данных, допустимых для данного домена.
• Домен несет определенную смысловую нагрузку.

Атрибут отношения есть пара вида <Имя_атрибута : Имя_домена>. Имена атрибутов должны быть уникальны в пределах отношения. Часто имена атрибутов отношения совпадают с именами соответствующих доменов.

Отношение R, определенное на множестве доменов, содержит две части: заголовок и тело.

Заголовок отношения – это фиксированное количество атрибутов отношения:

Заголовок отношения описывает  декартово произведение доменов, на котором задано отношение. Заголовок  статичен, он не меняется во время работы с базой данных. Если в отношении  изменены, добавлены или удалены  атрибуты, то в результате получим  уже другое отношение (пусть даже с прежним именем).

Тело  отношения содержит множество кортежей отношения. Каждый кортеж отношения представляет собой множество пар вида <Имя_атрибута : Значение_атрибута>:

 

 

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

Отношение обычно записывается в виде:

 

,

или короче

,

или просто

.

Число атрибутов в отношении  называют степенью (или -арностью) отношения. Мощность множества кортежей отношения называют мощностью отношения.

Схемой  отношения называется перечень имен атрибутов данного отношения с указанием домена, к которому они относятся:

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

Схемы двух отношений называются эквивалентными, если они имеют одинаковую степень и возможно такое упорядочение имен атрибутов в схемах, что на одинаковых местах будут находиться сравнимые атрибуты, то есть атрибуты, принимающие значения из одного домена:

Пусть – схема отношения . – схема отношения после упорядочения имен атрибутов. Тогда

~

Таким образом, для эквивалентных  отношений выполняются следующие  условия:

• Таблицы имеют одинаковое количество столбцов.
• Таблицы содержат столбцы с одинаковыми наименованиями.
• Столбцы с одинаковыми наименованиями содержат данные из одних и тех же доменов.
• Таблицы имеют одинаковые строки с учетом того, что порядок столбцов может различаться.

Все такие таблицы есть различные изображения одного и того же отношения.

Свойства  отношений. Свойства отношений непосредственно следуют из приведенного выше определения отношения. В этих свойствах в основном и состоят различия между отношениями и таблицами.

• В отношении нет одинаковых кортежей.
• Кортежи не упорядочены (сверху вниз).
• Атрибуты не упорядочены (слева направо).
• Все значения атрибутов атомарны.

 

 

Рис. Схематическое  изображение отношения

 

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

Связью называется ассоциирование двух или более сущностей. Примерами  связей является зачисление служащих в отделы (связь “многие –  к одной”) и поставка деталей  поставщикам (связь “многие –  ко многим”).

5. Объекты реляционной  БД

БД может содержать  разные типы объектов. Каждая СУБД может  реализовывать свои типы объектов.

 

Таблицы  – основные объекты  любой БД, в которых хранятся все  данные, имеющиеся в базе, и хранится сама структура базы (поля, их типы и  свойства).

 

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

 

Страницы или страницы доступа к данным – специальные  объекты БД, выполненные в коде HTML , размещаемые на web -странице и передаваемые клиенту вместе с ней. Сам по себе объект не является БД, посетитель может с ее помощью просматривать записи базы в полях страницы доступа. Т.о., страницы – интерфейс между клиентом, сервером и базой данных, размещенным на сервере.

 

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

6.  Целостность данных. Первичные и вторичные ключи

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

• при изменении поля связи в записи родительской таблицы следует синхронно изменить значения полей связи в соответствующих записях дочерней таблицы;
• при удалении записи в родительской таблицы следует удалить соответствующие записи и в дочерней таблице.

Программисту или пользователю необходимо иметь возможность обращаться к отдельным, нужным ему записям  или отдельным элементам данных. В зависимости от уровня программного обеспечения прикладной программист  может использовать следующие способы: 
• Задать машинный адрес данных и в соответствии с физическим форматом записи прочитать значение. Это случай, когда программист должен быть «навигатором». 
• Сообщить системе имя записи или элемента данных, которые он хочет получить, и возможно, организацию набора данных. В этом случае система сама произведет выборку (по предыдущей схеме), но для этого она должна будет использовать вспомогательную информацию о структуре данных и организации набора. Такая информация по существу будет избыточной по отношению к объекту, однако общение с базой данных не будет требовать от пользователя знаний программиста и позволит переложить заботы о размещении данных на систему. 
В качестве ключа, обеспечивающего доступ к записи, можно использовать идентификатор – отдельный элемент данных. Ключ, который идентифицирует запись единственным образом, называется первичным (главным). 
В том случае, когда ключ идентифицирует некоторую группу записей, имеющих определенное общее свойство, ключ называется вторичным (альтернативным). Набор данных может иметь несколько вторичных ключей, необходимость введения которых определяется практической необходимостью – оптимизацией процессов нахождения записей по соответствующему ключу. 
Иногда в качестве идентификатора записи используют составной сцепленный ключ – несколько элементов данных, которые в совокупности, например, обеспечат уникальность идентификации каждой записи набора данных. 
Один из способов использования вторичного ключа в качестве входа – организация инвертированного списка, каждый вход которого содержит значение ключа вместе со списком идентификаторов соответствующих записей. 
Существует несколько различных способов адресации и поиска записей. 
1. Последовательное сканирование файла. Наиболее простым способом локализации записи является сканирование файла с проверкой ключа каждой записи. Этот способ, однако, требует слишком много времени и может применяться, когда каждая запись все равно должна быть прочитана. 
2. Блочный поиск. Если записи упорядочены по ключу, то при сканировании файла не требуется чтение каждой записи. ЭВМ могла бы, например, просматривать каждую сотую запись в последовательности возрастания ключей. При нахождении записи с ключом большим, чем искомое значение, просматриваются последние 99 записей, которые были пропущены. 
Этот способ называется блочным поиском. Записи группируются в блоки и каждый блок проверяется по одному разу до тех пор, пока не будет найден нужный блок. Иногда данный способ называется поиском с пропусками. 
3. Двоичный поиск. При двоичном поиске в файле записей, упорядоченных по ключу, анализируется запись, находящаяся в середине поисковой области файла (изначально всего файла), а ее ключ сравнивается с поисковым ключом. Затем поисковая область делится пополам и процесс повторяется для соответствующей половины области, пока не будет обнаружено искомое значение или длина области не станет равной 1. Число сравнений в этом случае будет меньше, чем для случая блочного поиска. 
Двоичный поиск эффективен для поиска в файлах, организованных в виде двоичного дерева с указателями, когда поиск проходит в направлении, задаваемом указателями. Кроме того, добавление в файл новых записей не приводит к сдвигу других записей, что требует много времени и является достаточно сложной процедурой. 
Таким образом, двоичный поиск более пригоден для поиска в индексе файла, чем в самом файле. 
4. Индексно-последовательные файлы. Если файл упорядочен по ключам, то для адресации может использоваться таблица, называемая индексом, связывающая ключ хранимой записи с ее относительным или абсолютным адресом во внешней памяти. 
Индекс можно определить как таблицу, с которой связана процедура, воспринимающая на входе информацию о некоторых значениях атрибутов и выдающая на выходе информацию, способствующую быстрой локализации записи или записей, которые имеют заданные значения атрибутов. 
Если записи файла упорядочены по ключу, индекс обычно содержит не ссылки на каждую запись, а ссылки на блоки записей, внутри которых можно выполнять поиск или сканирование. Хранение ссылок на блоки записей, а не на отдельные записи в значительной степени уменьшает размер индекса. Причем даже в этом случае индекс часто оказывается слишком большим для поиска, и поэтому используется индекс индекса. 
5. Индексно-произвольные файлы. Произвольный (не упорядоченный по ключу) файл можно индексировать точно так же, как и последовательный файл. Однако при этом индекс должен содержать по одному элементу для каждой записи файла, а не для блока записей. Более того, в нем должны содержаться полные абсолютные (или относительные) адреса, в то время как в индексе последовательного файла адреса могут содержаться в усеченном виде, так как старшие знаки последовательных адресов будут совпадать. 
Произвольные файлы в основном используются для обеспечения возможности адресации записей файла с несколькими ключами. Если файл упорядочен по одному ключу, то он не упорядочен по другому ключу. Для каждого типа ключей может существовать свой индекс: для упорядоченных ключей индекс будет иметь по одному элементу на блок записей, для других ключей индексы буду более длинными, так как должны будут содержать по одному элементу для каждой записи. Ключ, который чаще всего используется при адресации файла, обычно служит для его упорядочения. 
В индексно-произвольных файлах часто используются символические, а не абсолютные адреса, так как при добавлении новых или удалении старых записей изменяется местоположение записей. Если в записях имеется несколько ключей, то индекс вторичного ключа может содержать в качестве выхода первичный ключ записи. При определении же местоположения записи по ее первичному ключу можно использовать какой-нибудь другой способ адресации. По этому методу поиск осуществляется медленнее, чем поиск, при котором физический адрес записи определяется по индексу. В файлах, в которых положение записей часто изменяется, символическая адресация может оказаться предпочтительнее. 
6. Адресация с помощью ключей, преобразуемых в адрес. Известно много методов преобразования ключа непосредственно в значение адреса в файле. В тех случаях, когда возможно преобразование значения ключа непосредственно в значение адреса в файле, такой способ адресации обеспечивает самый быстрый доступ; при этом нет необходимости организовывать поиск внутри файла или выполнять операции с индексами. 
В некоторых приложениях адрес может быть вычислен на основе значений некоторых элементов данных записи. 
К недостаткам данного способа относится малое заполнение файла: в файле остаются свободные участки, поскольку ключи преобразуются не в непрерывное множество адресов. 
Другим недостатком схем прямой адресации является их малая гибкость. Машинные адреса записей могут измениться при обновлении файла. Для устранения этого недостатка прямую адресацию обычно выполняют в два этапа. Сначала ключ преобразуется в порядковый номер, который затем преобразуется в машинный адрес. 
7. Хэширование. Простым и полезным способом вычисления адреса является хэширование (перемешивание). В данном методе ключ преобразуется в квазислучайное число, которое используется для определения местоположения записи. 
Более экономичным является указание на область, в которой размещается группа записей. Эта область называется участком записей (slot, bucket). 
При первоначальной загрузке файла адрес, по которому должна быть размещена запись, определяется следующим образом: 
1. Ключ записи преобразуется в квазислучайное число, находящееся в диапазоне от 1 до числа участков, используемых для размещения записей. 
2. Число преобразуется в адрес участка и, если на участке есть свободное место, то логическая запись размещается на нем. 
3. Если участок заполнен, запись должна быть размещена на участке переполнения – следующий по порядку участок либо участок в отдельной области переполнения. 
При чтении записей из файла их поиск выполняется аналогично, причем может оказаться, что для поиска записи потребуется чтение нескольких участков переполнения. 
Из-за вероятностей природы алгоритма в этом способе не удалось достичь 100% плотности заполнения памяти, однако для большинства файлов может быть достигнута плотность 80 или 90%; при этом память для индексов не требуется. Большинство записей можно найти за одно обращение, но для некоторых потребуется второе обращение (при переполнении). Для очень небольшой части записей потребуется третье или четвертое обращение к файлу. 
Кроме того, в этом случае менее эффективно используется память, чем в индексных методах; записи не упорядочены для последовательной обработки. 
8. Комбинации способов адресации. При адресации записей некоторых файлов используются комбинации перечисленных выше способов. Например, с помощью индекса может определяться ограниченная поисковая область файла, затем эта область просматривается последовательно, либо в ней выполняется двоичный поиск. С помощью алгоритма прямой адресации может определяться нужный раздел индекса и, таким образом, исчезает необходимость поиска во всем индексе.

7. Безопасность и целостность  БД

Целостность БД – обеспечивается корректным выполнением разрешенных действий.

В СУБД поддерживается избирательный или обязательный подходы обеспечения безопасности.

Избирательный подход – каждый пользователь обладает определенными правами (полномочиями, привилегиями) при работе с тем или иным объектом БД.

Обязательный  подход – каждому объекту БД присваивается уровень доступа, а пользователям – уровень допуска.

В случае избирательного подхода предусмотрены слелующие правила:

• имя правила;
• правила или привилегии;
• диапазон применения привилегий;
• идентификаторы пользователей;
• действие при нарушении правила.

При обязательном подходе предусмотрено следующее:

• пользователь имеет возможность работы с объектом, если уровень его допуска больше или равен уровню доступа объекта;
• пользователь имеет возможность модифицировать объект, если уровень его допуска равен уровню доступа объекта.

Виды  ограничений целостности:

• немедленно проверяемые;
• откладываемые.

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

Уровни  изолированности пользователей:

1. Отсутствие потерянных изменений.
2. Отсутствие чтения данных, модифицируемых другой транзакцией.
3. Отсутствие неповторяющихся чтений.
4. Сериализация транзакций.

 

8. Нормализация БД

Основные требования нормализации.

1. Атрибуты каждого информационного объекта должен содержать уникальный идентификатор – ключ. Ключ является простым, если он состоит из одного атрибута, или составным, если из нескольких.
2. Все неуникальные идентификаторы – описательные атрибуты должны быть взаимозависимы (то есть между ними не должно быть функциональных зависимостей).
3. Все атрибуты, входящие в составной ключ, должны быть также взаимозависимы.
4. Каждый описательный атрибут должен  быть функционально полно зависеть от ключа, то есть каждому значению ключа должно соответствовать только одно значение описательного атрибута.
5. При составном ключе описательные атрибуты должны зависеть целиком от всей совокупности атрибутов, образующих ключ.
6. Каждый описательный атрибут не должен зависеть от ключа транзитивно, то есть через другой промежуточный атрибут.
7. В случае транзитивной зависимости между атрибутами можно выполнить расщепление совокупности атрибутов с образованием двух информационных объектов вместо одного.