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

Логическая  структура ООБД похожа на структуру  иерархической БД. Основное отличие состоит в методе монепулирования данными. Инкапсуляция

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

- возможность отображения информации о сложных взаимосвязях 
объекта. ООМД позволяет идентифицировать отдельную запись 
БД и определять функции обработки для нее.

Недостатки:

• высокая понятийная сложность.
• неудобство в обработке данных. 
• низкая скорость выполнения запросов.
 

39.Сильноветвящиеся  В-деревья. Основные понятия и операции. Балансировка страниц. Б-ДЕРЕВЬЯ

До сих пор мы в  наших обсуждениях ограничивали себя деревьями, у каждой вершины  которых было самое большее два  потомка, т. е. двоичными (или бинарными) деревьями. Этого было вполне достаточно, например, для представления родственных отношений, если исходить из «родословных» представлений, когда каждый человек ассоциируется со своими родителями. В конце концов у каждого из нас не более двух родителей. А если нужно «потомственное» или «наследственное» представление? Ведь в этом случае приходится учитывать, что некоторые могут иметь более двух детей, и, следовательно, соответствующие деревья — вершины с многими ветвями. За неимением лучшего термина мы будем называть такие деревья сильно ветвящимися. В этом случае значительно лучше представлять потомство в виде линейного списка со ссылками от родителя на самого младшего (или старшего) из детей. В такой ситуации можно воспользоваться такими описаниями типов:

Рис. 4.43. Сильно ветвящееся дерево, представленное в виде двоичного.

  (4,

На рис. 4.43 приведен пример данных соответствующей структуры. Можно заметить, что если повернуть  на этом рисунке ссылки на 45°, то получим  нечто вроде совершенного двоичного дерева. Однако считать его таковым было бы ошибкой, поскольку функционально эти две ссылки имеют совершенно другой смысл. Обычно нельзя обращаться с братом, как с сыном * и поэтому так не следует поступать даже при описании данных. Этот пример можно легко продолжить и, введя в запись, описывающую человека, еще другие компоненты, получить данные более сложной структуры, отражающие другие родственные отношения. Например, из отношений «сын» и «брат» нельзя вывести отношения класса «муж» и «жена» и даже обратного отношения «отец» и «мать». Подобные структуры быстро разрастаются в сложный реляционный банк данных, в котором можно выделить несколько деревьев. Алгоритмы, работающие с такими структурами, существенно зависят от их описаний, поэтому не имеет смысла определять для них какие-либо общие правила или приемы работы.

В этом случае будем считать, что вершины дерева должны храниться во вторичной памяти, скажем на диске. Вводимые в данной главе динамические структуры данных особенно подходят именно для такой вторичной памяти. Принципиальное новшество— ссылки представляют собой адреса на диске, а не в оперативной памяти. Если использовать для множества данных, включающих, например, миллион элементов, двоичное дерево, то потребуется в среднем приблизительно порядка log(10⁶), т. е. 20 шагов поиска. Поскольку теперь каждый шаг включает обращение к диску (с его собственным латентным временем), то крайне желательна организация памяти, требующая меньшего числа обращений. Сильно ветвящиеся деревья представляют собой идеальное решение этой проблемы. Если происходит обращение к одному элементу, расположенному во вторичной памяти, то без больших дополнительных затрат можно обратиться и к целой группе элементов. Это предполагает, что дерево разбито на поддеревья и эти поддеревья как раз те группы, которые одновременно доступны. Мы будем называть такие поддеревья страницами. На рис. 4.44 приведено разбитое на страницы двоичное дерево; каждая из страниц содержит 7 вершин.

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

Рис. 4.44. Двоичное дерево, разделенное на страницы.

в этом случае поиск в  дереве с миллионом элементов  будет в среднем требовать logioo(10⁶) обращений к страницам (т. е. всего около 3), а не 20. Конечно, если дерево растет случайным образом, то в худшем случае может потребоваться даже и 10⁴ обращений. Поэтому ясно, что для сильно ветвящихся деревьев почти обязательна   некоторая   схема   управления   их ростом.

Сильно ветвящиеся Б-деревья

Если речь заходит  о критерии управления ростом дерева, то сразу же можно отказаться от идеальной сбалансированности, поскольку  она требует слишком -больших  затрат на балансировку. Очевидно, правила  надо как-то смягчить. Очень разумный критерий был сформулирован в 1970 г. Р. Бэйером и Е. Маккрейтом {4.2]: каждая страница (кроме одной) должна содержать при заданном постоянном п от п до 2п вершин. Таким образом, для дерева с N элементами и максимальным размером страницы в 2п вершин в самом худшем случае потребуется logn N обращений к страницам, а ведь эти обращения составляют основную часть затрат на поиск. Кроме того, коэффициент использования памяти, а это достаточно важно, раеен 50 %, поскольку страницы всегда заполнены минимум наполовину. При всех этих достоинствах наша схема ориентирована и на сравнительно простые алгоритмы поиска, включения и исключения. В дальнейшем мы их изучим более детально. 

14. Реляционная  алгебра. Другие виды соединений. Понятие соединимости кортежей. . Тэта-соединение

Определение 9. Пусть отношение А содержит атрибут X ,

отношение В содержит атрибут Y, а - один из операторов

сравнения Тогда-соединением

отношения А  по атрибуту X с отношением В по атрибуту

Уназывают отношение

Это частный  случай операции общего соединения.

Иногда, для  операции -соединения применяют следующий,

более короткий синтаксис: Экви-соединение

Наиболее важным частным  случаем ^- Соединения является

случай, когда есть просто равенство. Синтаксис экви-соединения:

17. Понятие нормализации БД. Функциональная зависимость и взаимозависимость, транзитивная и многозначная зависимость. Денормализация БД.

Зависимости между атрибутами

1.   Атрибут В  функционально зависит от атрибута  А, если

каждому значению А соответствует  только одно значение В.

Обознач-ся: А  =>  В

2. Если существует  функциональная зависимость вида  А ->

В и В-> А, то между  А и В      имеется  взаимосвязанное

соответствие или функциональная взаимозависимость. Обозн:

А ? В Частичная    функциональная зависимость это зависимость неключевого атрибута от части составного ключа.

Полная  функциональная зависимость Когда неключевой атрибут полностью зависит от составного ключа.

Пр:_Кафедра(ФИО, должен, оклад, стаж, д_стаж, кафедра, предмет, группа, вид занятий) ФИО ->      кафедра ФИО ->    должность

->Атрибут  С зависит от А транзитивно  если для атрибутов А,В,С выполняется условие А ->    В и В ->   С , но нет обратной зависимости     А ->   С Пример.     ФИО -> должность   ->  оклад

В отношении r атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из г.

Обозн. А    =>   В,    А   <=  В, А <=>В       ФИО   < =>   предмет Замечание: В общем случае между двумя  атрибутами одного отношения могут существовать функциональные и многозначные зависимости (1:1, 1:М, М:М) т.к. зависимость между атрибутами является причиной аномалий, то необходимо разбить отношение с зависимостями атрибутов на несколько отношений. В результате получается совокупность связанных отношений, связи между которыми отражают зависимости между атрибутами различных отношений.

Два или более  атрибутов называются взаимонезависимыми, если не один из этих атрибутов не зависит функционально от других атрибутов (Обозн. А ? -> В).

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

Транзитивные зависимости также порождают избыточное порождение данных.

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

1. Концепция  баз данных. Понятия теории и  технологии баз данных (БД).

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

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

Теория баз данных является научной дисциплиной, обладающей

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

теоретическими результатами.

Математический аппарат составляет теория множеств, алгебра

логики, теория графов.

Технология баз  данных включает методологию и эксплуатацию ба

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

разработчиков и администраторов  БД.

Предметная область может быть определена как часть реального

мира, которая отображается с помощью банка данных.

Банк данных - это БД в совокупности с СУБД (система

управления БД) применимой для ее создания и эксплуатации.

Предметная область может быть описана множеством

информационных объектов и связями между ними.

Информационный объект - это некоторое понятие или процесс,

относящийся к предметной области, о котором хранятся

описательные сведения. Каждый объект описывается в виде: <имя

объекта, имя характеристики, значение характеристике

Для определения характеристик  объектов используется понятие

поля, которое является наименьшей и логически неделимой

единицей информации. Поле определяется именем и множеством

допустимых значений.

Принимаемые полями значения называют данными.

Запись - это совокупность значений всех полей, которые

описывают конкретный объект.

Множество однотипных записей  называют файлом данных.

Между полями между записями и между файлами существует

сложная система взаимосвязей. Среди всех полей, описывающих

некоторый объект можно  выделить одну или несколько, по

значению которых однозначно определяется объект в БД. Такое

поле называют ключом.

Элементы не входящие в состав ключа называют неключевыми

атрибутами. Соответственно, входящие называют ключевыми

атрибутами.

4. Модели данных: иерархическая, сетевая модели. Модели  данных

Виды взаимосвязей:

1. Один к одному 1:1 означает что в любой момент времени одному значению поля А соответствует только одно значение поля В.
2. Один ко многим 1:М; многие к одному М:1 означает что одному значению   поля А соответствует некоторое число (0,1 или несколько) значений, связанного с ним, поля В.
3. Многие ко многим М:М однозначность определения значений полей отсутствует в обоих направлениях.

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

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

1. Простота программной реализации.
2. Простота понимания и использования памяти Недостатки ИМД:

 

1. Жесткая ограниченность структур данных.;
2. Сложность действий при включении или удалении данных.

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

В отличие от ИМД СМД позволяет осуществлять доступ к данным несколькими путями.

Сетевые   структуры   могут  содержать   цикл.   Связи   в   сетевых моделях  представлены в явном виде в специальных  полях связи, следовательно, каждая запись имеет... Достоинства данной модели:

1. Возможность реализации связи М:М
2. Допустимость образования произвольных связей. Недостатки:

 

1. Сложность понимания и обработки информации.
2. Сложность структур данных .
3. Ослаблен контроль целостности