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

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

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

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

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

Отношение может  иметь несколько потенциальных  ключей. Традиционно, один из потенциальных  ключей объявляется первичным, а остальные - альтернативными. Различия между первичным и альтернативными ключами могут быть важны в конкретной реализации реляционной СУБД, но с точки зрения реляционной модели данных, нет оснований выделять таким образом один из потенциальных ключей. Первичным ключом называется атрибут (или совокупность атрибутов) отношения, однозначно идентифицирующие каждый из кортежей данного отношения. Пусть в отношении R1 имеется неключевой атрибут А, значение которого является значением ключевого атрибута В другого отношения R2, тогда говорят что атрибут А отношения R1 является внешним ключом. 

38.Сбалансированные деревья.  Алгоритм построения идеально сбалансированного дерева. Деревья Фибоначчи.

Дерево называется сбалансированным тогда и только тогда, когда

высоты двух поддеревьев  каждой из его вершин отличаются не

более чем  на единицу.

Деревья,   удовлетворяющие   такому   условию,   часто   называют

АВЛ-деревьями (по имени их открывателей). Мы их будем  просто

называть сбалансированными деревьями, поскольку упомянутый

критерий  сбалансированности  выглядит наиболее подходящим.

(Заметим, что все  идеально сбалансированные деревья  являются

также и АВЛ-деревьями.)

Введенное  определение  не только  само  очень  простое,  но  и

приводит к простой процедуре повторной балансировки, причем

средняя длина пути поиска практически совпадает с длиной в

идеально  сбалансированном дереве.

В сбалансированных деревьях за время, пропорциональное O(logn)

даже в худшем случае, можно выполнить такие операции:

1. Найти вершину с данным ключом.
2. Включить новую вершину с заданным ключом.

3. Исключить вершину с указанным ключом. Такие 
утверждения—следствие доказанной Адельсон-Вельским и 
Ландисом теоремы, гарантирующей, что сбалансированное дерево 
никогда не будет по высоте превышать идеально 
сбалансированное более чем на 45 % независимо от количества 
вершин. Если обозначить высоту сбалансированного дерева с п 
вершинами через h_b(n), то

log (n + 1)< Ц (п) < 1.4404 * log (n + 2) - 0.328 (4.60)

Оптимум достигается, очевидно, если дерево идеально сбалансировано, при п •== 2^й—1. Однако какова

Рис. 4.30. Деревья  Фибоначчи высотой 2, 3, 4.

структура самого плохого сбалансированного АВЛ-дерева? Чтобы найти максимальную высоту h для всех сбалансированных деревьев с п вершинами, поступим следующим образом: возьмем фиксированную высоту h и попытаемся построить сбалансированное дерево с минимальным числом вершин. Мы следуем такой стратегии, поскольку, как и в случае минимальной высоты, это значение может быть достигнуто только при некоторых вполне определенных значениях. Обозначим такое дерево высоты h через Th. Ясно, что То — пустое дерево, &Т\ — дерево с одной-единственной вершиной. Для построения Th для h > 1 мы будем брать корень и два поддерева опять же с минимальным числом вершин. Следовательно, эти деревья также относятся к классу Т-деревьев, Одно поддерево, очевидно, должно быть высотой h—1, а другому позволяется иметь высоту на единицу меньше, т. е. h—2. На рис. 4.30 представлены деревья высотой 2, 3 и 4. Поскольку принцип их построения очень напоминает построение чисел Фибоначчи, то мы будем называть такие деревья деревьями Фибоначчи. Они определяются следующим образом:

1. Пустое дерево есть дерево Фибоначчи высоты 0.

2. Единственная вершина есть дерево Фибоначчи 
высоты 1.

3. Если T_h.! и T_h.₂—деревья Фибоначчи высотой h — 1 и h — 2, то Th = < Ты, х, T_h.2> также дерево Фибоначчи высотой h.
4. Других деревьев Фибоначчи не существует. Число вершин в Th определяется из такого простого рекуррентного отношения:

N,=0,

+ I+N_h.

Числа Ni как раз и будут числом вершин для самых худших случаев (верхний предел h), их называют числами Леонарда. 

20.Нарушения  ссылочной целостности. Стратегии  поддержания ссылочной целостности. Операции, нарушающие ссылочную целостность:

Вставка, удаление, обновление кортежей в отношениях. Для родительского отношения:

1. Вставка кортежей. Здесь возникает новое значение потенциального ключа,
2. Обновление кортежей. Может изменится значение потенциального ключа..
3. Удаление кортежей. Удаляется значение потенциального ключа.

Для дочернего отношения:

1. Вставка кортежей. Нельзя вставить кортежей в дочернем отношении, если вставляемое значение внешнего ключа некорректно.
2. Обновление кортежей. При обновлении кортежей в дочернем отношении возможно некорректное изменение внешнего ключа.
3. Удаление кортежей. При удалении кортежей в дочернем отношении ссылочная целостность не нарушается.

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

1. обновление кортежей в родительском отношении.
2. удаление кортежей в родительском отношении.
3. вставка кортежей в дочернем отношении.

4. обновление кортежей в дочернем отношении. Стратегия поддержания ссылочной целостности Существует две основные:

 

1. RESTRICT (ограничить) т.е. не разрешить выполнение операции, приводящей к нарушению целостности. Здесь необходима проверка, имеются ли кортежи в дочернем отношении, связанные с некоторым кортежом в родительском отношении.
2. CASCADE (каскадировать). Разрешить выполнение операции, но внести необходимые изменения в других отношениях так, чтобы не допустить нарушение ссылочной целостности и сохранить все имеющиеся связи.

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

3. SET NULL. Разрешается выполнение операции, но все 
возникшие некорректные значения внешних ключей, 
изменяются на NULL значение. Эта стратегия имеет два 
недостатка:

1. Использование NULL значений.
2. Теряется связь кортежей дочернего отношения с кортежами родительского отношения.

 

4. SET DEFAULT. Разрешается выполнение операции, но все возникающие некорректные значения внешних ключей заменяются на некоторое значение, принятое по умолчанию.
5. IGNORE. Операции выполняются не обращая внимания на нарушение ссылочной целостности. Вся ответственность за целостность БД ложится на пользователя. Пользователь также может придумать свою стратегию поддержки ссылочной целостности.
 

29.Проектирование  БД. Этап «Концептуальное (логическое) проектирование».

Концептуальное (логическое) проектирование

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

Последовательность  проектирования структуры БД.

 

24.Разрешение  КОЛЛИЗИЙ. Метод последовательного  сдвига регистра. Привести пример.

любая методика повторного хеширования, где очередная  проба зависит только от предыдущей, обнаруживает группирующие свойства линейного хеширования. Рассмотрим методику :h; (x)= (h(x)+i)mod В, где d,e [1;B-1]

d,-"случайные" перестановки чисел 1,2 В-1.

Набор чисел А, должен использоваться при реализации всех операций, выполняемых над множеством, а перемешивание целых чисел должно быть выбрано еще при разработке алгоритма хеширования. Одним из эффективных методов перемешивания целых чисел является метод последовательных сдвигов регистров.Пусть В является степенью числа 2, К - константа из интервала е [1;В-1], далее генерируется последовательность d,   путем удвоения предыдущего значения до тех пор, пока последнее значение не превысит В, тогда чтобы получить следующее   А,  из последнего значения отнимается число В и результат суммируется по mod2 с константой К. Замечание: не для каждого значения К можно получить все переменные значения из интервала   [1 ;В-1], поэтому необходимо для каждого значения В подобрать свое значение К. Пример:В=$, К=3 [1;7] d_t=101=5

сдвиг	1010
удаление ведущую единицу	010
+3	d2=001=l
Сдвиг	d3=0K)=2
Сдвиг	d4= 100=4
Сдвиг	1000
удаление ведущую единицу	000
+3	ds=001=5
Сдвиг	d6= 110=6
Сдвиг	1100
Удаление ведущего Нуля	100
+3	d7=lll=7

Полный перемешанный набор чисел 1,... ,7 можно получить также для К=5, но не при каких других значениях. 

22.Хеширование  данных. Основные понятия и термины. Открытое хеширование

Открытое хеширование. Основная идея: потенциальное множество разбивается на конечное число классов.

Классы нумеруется от 0 до В-1. Для В классов строится хеш-функция h такая, что для любого элемента х исходного множества h(x) e [0, В-1] (целочисленное значение),т.е. которое соответствует классу, которому принадлежит элемент х. Элемент х называют ключом, h(x) - хеш-кодом, х (свертка ), классы называют сегментами.

Массив называемый таблицей сегментов и проиндексированный номерами сегментов содержит заголовки для В списков элемент х, /-го списка - это элемент исходного множества, для которого h(x) = i.

Если исходное множество   состоит из   п    элементов, то средняя длина списков будет равна п/В.

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

 

 

 

Концептуальной  схемой называют описание предметной области

в терминах некоторой  модели данных.

Отображение концептуальной схемы на физическом уровне ЭВМ

называют внутренней схемой.

Отображение взгляда  отдельной категории пользователей  на

концептуальную схему  называют внешней схемой.

32.Жизненный  цикл систем баз данных.

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

1. Формулирование и анализ требовании.
2. Концептуальное проектирование.
3. Проектирование реализации,
4. Физическое проектирование.

Фаза  реализации и функционирования базы данных

1. Реализация базы данных,
2. Анализ функционирования и поддержка.
3. Модификация и адаптация.

Фаза  реализации и функционирования базы данных Реализация базы данных подразумевает создание базы данных и прикладных программ на основе результатов трех главных эталон проектирования базы данных, а также, загрузку базы данных. Задача загрузки базы данных часто упускается из вида, однако она требует много усилий. Имеющиеся данные необходимо преобразовывать из существующей формы представления логической и физической структуры в новую форму, соответствующую результатам проектирования базы данных, Разработка прикладных программ тесно связана с выбором включающего (базового) языка программирования, с логической структурой базы данных и в меньшей степени с физической структурой. Целью этого этапа является создание надежных н эффективных программ доступа к базе данных, удовлетворяющих требованиям пользователей к обработке данных. Анализ функционирования и поддержка используются для сбора (регистрации) и статистической обработки данных о функционировании системы. Эта информация позволяет выявить степень обоснованности требований пользователей, а также "узкие места" в процессе эксплуатации с целью пересмотра системы в будущем. Поддержка базы данных должна обеспечивать ее целостность и эффективное восстановление после сбоев. Модификация и адаптация предусматривает внесение в реализованный проект изменений, возникающих вследствие появления новых требований, анализа функционирования системы или анализа мнений пользователей о работе системы. Целью этого этапа является оптимизации функционирования существующей системы путем реорганизации базы данных и/или внесения изменений в программное обеспечение. Реорганизация базы данных является широким понятием, используемым для описания любых изменений в логической или физической структуре базы данных. Изменения могут варьироваться в пределах от инвертирования связей (реструктурирования) до перестройки физической структуры (реформатирования).