Учебное пособие по базам данных. Учебное пособие. Пособие по базам данных Введение

• Название: Пособие по базам данных Введение
• Анкор: Учебное пособие по базам данных
• Дата: 23.11.2021
• Размер: 169.5 Kb.
• Имя файла: Учебное пособие.doc
• Тип: Пособие; #279476
• страница: 1 из 3

Учебное пособие

по базам данных

Введение

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

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

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

Если данные имеют самостоятельную ценность: большой жизненный цикл данных, использование их в различных приложениях и т.д., то появляется необходимость использования СУБД. На проблему выбора СУБД оказывают влияние следующие факторы: 1) наличие или возможность приобретения ЭВМ и операционной системы, на которую ориентирована СУБД; 2) соответствие типа модели данных, который выбран при проектировании, и типа СУБД; 3) наличие функциональных возможностей в СУБД, необходимых для реализации приложений; 4) обеспечение многопользовательского режима доступа к данным; 5) соответствие стандарту языков описания и манипулирования данными и т.д. Наиболее важным этапом является построение модели данных прикладной области (схемы базы данных). Правильно построенная схема обеспечивает устойчивость всей системы к различным изменениям в прикладной области в процессе эксплуатации БД, что существенно сокращает затраты на сопровождение. Экономия достигается за счет отсутствия необходимости переписывания старого прикладного программного обеспечения и локальности необходимых преобразований физической организации данных. Отправной точкой для проектирования схемы БД является изучение документооборота в заданной прикладной области.
Типовое задание на проектирование схемы базы данных
В индивидуальном задании предлагается прикладная область, для которой требуется составить проект БД. Кроме того, приведен перечень документов, являющихся источником сведений для построения схемы. В некоторых случаях приводятся комментарии к документам, уточняющие их специфику.

Типовое задание содержит 6 пунктов. Результаты выполнения каждого пункта являются основой для выполнения следующих пунктов и ошибки, допущенные в каком-либо пункте, обязательно проявятся в результирующей схеме БД.
Этапы типового задания:
Этап 1. Для каждого документа выделить содержащиеся в нем элементы данных. Составить их общий перечень. Список может быть расширен за счет рекомендаций пользователя. При этом требуется: а) объединить синонимы в один элемент данных и присвоить ему имя, приемлемое для всех пользователей; б) разъединить омонимы, присвоив каждому элементу данных уникальное имя.

Общее требование к элементам данных следующее:

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

Ошибки: 1) Цех – этот элемент данных может содержать в себе другие элементы: начальник цеха, выпускаемая продукция и др., то есть отсутствует семантическая однозначная интерпретация этого элемента (наверное, имелось в виду название цеха или номер цеха); 2) Средняя зарплата в отделе – этот элемент не является первичной информацией, а может быть вычислен, следовательно, в базе данных надо хранить сведения о выплатах каждому сотруднику отдельно, а среднее, минимальное, максимальное значения – вычислять в прикладной программе; 3) Возраст – этот элемент имеет изменяемое значение (в системе отсутствует событие, приводящее к необходимости изменения этого значения), нужно использовать элемент "дата рождения", а возраст вычислять в приложении.
Этап 2. Для выделенных в пункте 1 атрибутов построить множество функциональных зависимостей.
Определение. Пусть задана схема отношения R на совокупности атрибутов U = {A₁, A₂, ..., A_n}, (возможно R – тип записи для структурированной модели данных). Пусть X и Y – некоторые подмножества из множества атрибутов U. Будем говорить, что X функционально определяет Y (XY), если в любой реализации r схемы R не могут присутствовать два кортежа t,ur, такие что t[X]=u[X] и t[Y]u[Y].

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

Шаг 1. По правилу декомпозиции функциональных зависимостей преобразуем F к виду, где все зависимости имеют один атрибут в правой части.

Шаг 2. По очереди удаляем каждую зависимость из F: G=F\{XA_i}, и проверяем эквивалентность полученного множества G исходному F (достаточно проверить условие: A_iX⁺_G). Если получено эквивалентное множество, то зависимость не возвращается, если не получено – возвращается.

Шаг 3. Последовательно исключаем по одному атрибуту в левой части каждой функциональной зависимости XA_iF. Пусть Z=X\A_j и G={F\{XA_i}}{ZA_i}, если полученное множество G эквивалентно F (достаточно проверить условие: A_iZ⁺_F), то атрибут A_j не возвращается, иначе возвращается.

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

В алгоритме X⁺_F  замыкание множества атрибутов X на множестве зависимостей F вычисляется следующим образом:

Шаг 0. Начальное множество X⁰=X (рефлексивность).

Шаг i (i=1,2,..). Выполняется итерация: просматриваются все функциональные зависимости из F. Если для какой-либо зависимости ZYF, ZX^i-1, тогда Xⁱ=X^i-1Y и переход к следующей итерации. Поскольку, X^i-1XⁱU, то алгоритм за конечное число шагов сойдется. Если на каком-то шаге после просмотра всех функциональных зависимостей оказалось, что X^i-1=Xⁱ (не было сделано ни одной подстановки), тогда X⁺_F=Xⁱ. Конец построения.
Этап 3. Построить схему базы данных реляционного типа, удовлетворяющую требованиям третьей нормальной формы, свойству соединения без потерь информации и сохраняющую зависимости. Построить минимальное множество связей между отношениями БД
Полученное на этапе 2 минимальное покрытие множества функциональных зависимостей преобразуется следующим образом: объединяются зависимости с совпадающими левыми частями. Например, зависимости XA_i и XA_j объединяются в зависимость XA_iA_j.

Замечание. На практике зависимости XA_i и XA_j могут иметь различную область определения (одна зависимость имеет место для одного подмножества объектов, другая  для другого). Тогда эти зависимости объединять нельзя.

Далее из полученных зависимостей формируются отношения. Например, зависимость A_iA_jA_lA_kA_m служит основанием для формирования отношения:

Ai

Aj

Al

Ak

Am

где A_iA_j  первичный ключ отношения.

Полученным отношениям присваиваются наименования. Если семантика атрибутов определена однозначно и функциональные зависимости построены без ошибок, то отношения будут иметь однозначную семантику и вводимое наименование отношения должно соответствовать этой семантике.

Такой способ формирования отношений гарантирует сохранение функциональных зависимостей и выполнение условий третьей нормальной формы (3НФ). При этом не гарантируется выполнение свойства соединения без потерь информации (зависимость соединения). Для проверки этого свойства формируем обобщенный ключ (суперключ), который функционально определяет все атрибуты из множества U: множество атрибутов XU, является обобщенным ключом для U, если XA₁,A₂,...,A_nF⁺; и для любого YX (Y-истинное подмножество X) выполнено YA₁,A₂,...,A_nF⁺.

Пусть X  обобщенный ключ. Если какое-либо отношение содержит атрибуты X (в качестве ключа), то совокупность сформированных отношений (схема БД) обладает свойством соединения без потерь информации (теорема 5.8 [1]).Если такого отношения нет, необходимо выполнить проверку по следующему алгоритму.

Исходные данные: декомпозиция ρ(R₁, R₂,…, R_k) схемы отношения R, определенной на множестве атрибутов U=(A₁, A₂, ..,A_n) и множество функциональных зависимостей F.

Шаг 1. Строим начальную таблицу, содержащую k строк и n столбцов. На пересечении i-ой строки и j-ого столбца ставим символ a_j, если атрибут A_j принадлежит отношению R_i, иначе – b_ij.

Шаг 2. Выполняем очередную итерацию – последовательно просматриваем все зависимости из F. Для текущей зависимости X→Y∈F выбираем строки из таблицы, которые совпадают по атрибутам X (совпадать могут символы a_j и b_ij). Если для какой-либо строки атрибут A_j*, принадлежащий Y, имеет значение a_j*, то значение b_ij* в выделенных строках заменяется на a_j*. Если для всех строк атрибут A_j*, принадлежащий Y, имеет различные значение b_ij*, то значения b_ij* в выделенных строках отождествляются (заменяются на одно какое-либо значение b_i*j* из выделенных строк). Если после очередной итерации появилась строка, состоящая из одних a_j, то декомпозиция ρ обладает свойством соединения без потерь информации. Если после очередной итерации не было сделано ни одной подстановки и в таблице отсутствует строка, состоящая из a_j, то декомпозиция не обладает свойством соединения без потерь информации. Конец алгоритма.

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

Проблемы обобщенного ключа и способы их решения:

1. Совокупность атрибутов в обобщенном ключе X не обладает свойством однозначной семантической интерпретации: этому отношению нельзя присвоить однозначное имя. Решения:

а) выявляются потерянные функциональные зависимости на атрибутах X.

б) дополняются новые атрибуты, либо меняется семантика существующих атрибутов в X, для установления новых функциональных зависимостей на атрибутах X. После изменений, сделанных в пунктах а) и б) необходимо сделать соответствующие изменения на предыдущих этапах и снова вернуться к построению декомпозиции.

в) выявляется многозначная зависимость на атрибутах X и осуществляется декомпозиция отношения X (см. далее).

2. Если отношение X оказалось интерпретируемым, то оно может быть не технологичным: на предприятии отсутствует служба, которая отвечала бы за сопровождение данных в этом отношении. Решение:

а) сформировать новую схему документооборота на предприятии.

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

Многозначные зависимости. Дано: схема отношения R, определенная на совокупности атрибутов U = {A₁, A₂, ..., A_n}, пусть WU, YU и WY=, Z=R\(WY).

Определение. Множество W мультиопределяет множество Y в контексте Z: WY(Z) (многозначная зависимость), если для произвольной реализации r схемы R существует два кортежа t₁,t₂r таких, что t₁[W]=t₂[W] , то существует кортеж t₃, для которого выполнено:

t₃[W]=t₁[W], t₃[Y]=t₁[Y], t₃[Z]=t₂[Z],

в силу симметрии существует кортеж t₄:

t₄[W]=t₁[W], t₄[Y]=t₂[Y], t₄[Z]=t₁[Z].

Замечание. Множества атрибутов Y и Z обычно содержатся в обобщенном ключе, а множество W может оказаться за пределами обобщенного ключа X.

Основной признак (необходимый, но не достаточный) наличия многозначной зависимости в X является следствием определения: дополнение одного кортежа в реализацию X приводит к необходимости дополнения еще нескольких кортежей.

После определения многозначной зависимости отношение, соответствующее обобщенному ключу X, декомпозируется на два отношения R_s и R_p , содержащие атрибуты WY и WZ соответственно. Основным признаком правильности определения множества W является отсутствие возможности появления лишних кортежей в объединенной таблице:

R_s⋈R_p ,

где ⋈  операция естественного соединения, т.е. таких кортежей, которые не имеют смысла в данной прикладной области. Это является гарантией, что после декомпозиции обобщенного ключа схема БД по прежнему удовлетворяет свойству соединения без потерь информации, но уже в рамках четвертой нормальной формы (4НФ)

Чаще всего отношения R_s и R_p , являются частью существующих отношений R_m(i,j) , сформированных по функциональным зависимостям:

R_s=_WY(R_m(s,1)⋈ R_m(s,2)⋈…⋈R_m(s,d))

и

R_p=_WZ(R_m(p,1)⋈ R_m(p,2)⋈…⋈ R_m(p,g))

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

Такие отношения, R_s и/или R_p, считаем существующими и удаляем их из схемы БД.

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