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

 

39 Продолжение

7. Модели данных: многомерная модель.

Многомерная модель данных (ММД)

Существуют  два направления в развитии концепции информационных систем:

• Системы оперативной (транзакционной ) обработки.
• Системы аналитической обработки (системы поддержки принятия решений).

Транзакция - одна или несколько команд выполняются все сразу

(единица работы  БД).

Многомерные СУБД являются узкоспециализированными,

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

информации.

Свойства данных ММД:

Агрегируемость - это рассмотрение информации на различных

уровнях и  ее обобщения.

Историчность - предполагает обеспечение высокого уровня

статичности (неизменяемости ) самих данных и  их взаимосвязей, а

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

Прогнозируемость - подразумевает задание функции

прогнозирования и применение их к различным временным

интервалам.

Термины ММД:

Измерение (Dimension)- множество однотипных данных,

образующих  одну из граней гиперкуба.

Ячейка - это поля, значение которого однозначно определяется

фиксированным набором измерений.

В существующих ММД имеются два варианта организации

данных:

• полекубическое,
• гиперкубическое.

В полекубической схеме  предполагается, что в БД может  быть

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

различными измерениями (Oracle Express Server).

В случае гиперкубической  схемы предполагается, что у всех

гиперкубов  БД одинаковые размерности и совпадающие

измерения.

Операции над данными:

• срез (slice) представляет собой подмножество гиперкуба, полученное в результате фиксации одного или нескольких измерений.

• вращение (rotate) применяется при двумерном представлении данных и состоит в изменении порядка измерений.

• агрегация (drill up) и детализация (drill down) - эти операции означают соответственно, переход к более общему и более детальному представлению информации из гиперкуба. Достоинства.уцобства. и эффективность аналитической обработки больших объемов данных, связанных со временем. Недостатки : громоздкость для простейших задач оперативной обработки информации.

10. Операции обновления данных: добавление, удаление, изменение записей. Проблемы, возникающие при обновлении данных.

ADD - данная операция сообщает об ошибках в следующих случаях:

• Добавляемый кортеж не соответствует схеме отношения.
• Нек-рое знач-е кортежа не принадлежит соотв-щему домену.
• Кортеж совпадает по ключу с кортежем, уже имеющемся в отношении.

DEL - для удаления достаточно указать значение ключа удаленного кортежа. Ошибка возникает только в том случае, если удаляемый кортеж в отношении отсутствует. СН - для данной операции все ошибки добавления и удаления имеют место.

Аномалия  обновления При изменении:

Необходимо  многократное изменение данных. При удалении:

Существует  возможность потерять очень важную информацию. При добавлении:

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

2. Понятие системы  управления базами данных (СУБД). Требования к централизованному управлению данными. Преимущества и недостатки СУБД.

Система управления данными (СУБД) - комплекс программно-аппаратных средств, обеспечивающих доступ к БД и управление данными.

Технологией БД предполагается , что создание БД, ее поддержка и обеспечение доступа пользователей осуществляется централизованно с помощью специального программного обеспечения (СУБД).

централизованное  управление данными должно обеспечиать требования:

1. Производительность системы, оценивается временем получения ответа на запрос.
2. Минимальное дублирование данных. Дублирование данных неэффективно вследствие следующих причин:

- дорого, т.к. требуется  больше памяти для хранения

дублируемых данных.

- требуется  более одной операции при обновлении данных.

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

3. Целостность БД - это непротиворечивость, согласованность, достоверность данных, содержащихся в БД в любой момент времени.
4. Безопасность и хранение информации в БД. -защита данных от случайного или преднамеренного доступа к ним лиц, не имеющих на это право или запрет несанкционированного доступа
5. Независимость данных. Независимость обеспечивается тем фактом, что пользователи работают с БД как с единым целым и не знают внутреннего представления данных. СУБД обеспечивает два уровня независимости:

1-й уровень  - это физическая независимость данных, 2-й уровень - это логическая независимость данных.

6. Синхронизация.
7. Защита от отказов и восстановление данных.
8. Наличие языка запросов высокого уровня,

Преимущества СУБД:

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

2. Увеличивается мобильность и гибкость информационной системы.

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

Недостатки  СУБД:

1. Может увеличиться опасность несанкционированного доступа к данным.

2. Увеличивается сложность создаваемых систем.

3. Повышаются требования к аппаратным средствам.
4. Увеличивается доля служебной информации в общем объеме хранящихся данных.

5. Модели данных: реляционная модель. Фундаментальные свойства отношений. Модели данных

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

1. Один к одному   1:1 означает что в любой момент времени 
одному значению поля А соответствует только одно значение поля 
В.

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

3. Многие ко многим М:М однозначность определения значений полей отсутствует в обоих направлениях. Реляционная модель данных (РМД)

В настоящее время  является единственной моделью с  хорошо

проработанной теоретической БД.

В РМД объекты и  связи между ними представляются в виде

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

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

объект.

Большинство операций над  БД сводится к разрезанию и

склеиванию по строкам и столбцам таблиц. Связь между

таблицами осуществляется за счет наличия общих

столбцов(полей).

Достоинства РМД:

1. Простота, эффективность, удобство использования.
2. Легкость развития и дополнения.

3. Высокая степень независимости данных. Недостатки:

 

1. Сложность описания иерархических и сетевых связей.

2. Сложность обеспечения высокой производительности. Фундаментальные свойства отношений:

 

1. Отсутствие кортежей-дубликатов. Это свойство следует из определения отношения как множества кортежей. Во многих практических реализациях, как РСУБД, допускается нарушение свойства уникальности кортежей для промежуточных отношений, порождаемых при выполнении запроса.
2. Отсутствие упорядоченности кортежей. Это свойство дает дополнительную гибкость СУБД при хранении БД во временной

   памяти и при выполнении запросов.

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

* В оригинале речь идет об отношениях sibling (брат или сестра) и    offspring (сын или дочь). К сожалению, в русском языке такие

отношения не выражаются одним словом. — Прим.. перев.    Структуры данных, о которых идет речь, называются Б-деревьями,

an — порядком Б-дерева. Они обладают следующими свойствами:

1. Каждая страница содержит не более 2п элементов (ключей).

2. Каждая страница кроме корневой содержит не менее п 
элементов.

3. Каждая страница либо представляет собой лист, т. е. не имеет потомков, либо имеет m + 1 потомков, где m—число ключей на этой странице.
4. Все страницы-листья находятся на одном уровне. На рис. 4.45 приведено Б-дерево второго порядка с тремя уровнями. Все страницы содержат 2, 3 или 4 элемента, исключение представляет лишь корневая страница: в ней может находиться лишь один-единственный элемент. Все листья находятся на третьем уровне. Если спроецировать Б-дерево на один-единственный уровень, включая потомков между ключами их родительской страницы, то ключи идут в возрастающем порядке слева направо. Такое размещение представляет собой естественное развитие принципа двоичных деревьев и определяет метод поиска элемента с заданным ключом. Пусть страница имеет вид, приведенный на рис. 4.46, и задан некоторый аргумент поиска х. Предположим, страница уже считана

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

1. ki < х < k_i+1 для 1 =< i < m. Поиск продолжается на странице pi.
2. k_m < х. Поиск продолжается на странице p_mt.
3. х < k1. Поиск продолжается на странице р₍₎Т. Если указанная ссылка имеет значение NIL, т. е. страницы-потомка не существует, то в дереве вообще не существует элемента с ключом х и поиск заканчивается.

К удивлению, включение  в Б-дерево проводится сравнительно просто. Если элемент нужно поместить  на страницу с m < 2n элементами, то процесс включения затрагивает лишь эту страницу. Лишь включение в уже полную страницу затрагивает структуру дерева и может привести к появлению новых страниц. Для того чтобы понять, что происходит в этом случае, обратимся к рис. 4.47, иллюстрирующему процесс включения в Б-дерево порядка 2 ключа, равного 22. Включение проходит за три шага:

1. Обнаруживается, что ключ 22 отсутствует. Включение в 
страницу С невозможно, поскольку она уже заполнена.

2. Страница С разделяется на две страницы (т. е. вводится новая 
страница D).

| 7   10 15 18||26 30 35 4о[    [7   10 15 1 а) 122 26       J  fe 40 |

ВС В С Р

Рис. 4.47. Включение в  Б-дерево ключа со значением 22.

3. Ключи—их  всего 2п + 1—поровну распределяются  в С и D, а средний ключ переносится на один уровень вверх на «родительскую» страницу.

Такая весьма элегантная схема сохраняет все характерные  свойства Б-деревьев. В частности, получившиеся две новые страницы содержат ровно по п элементов. Конечно, включение элемента в родительскую страницу может вновь привести к переполнению страницы, т. е. разделение будет распространяться. В крайнем случае оно может «подняться» до самого корня. Фактически только в этом случае может увеличиться высота Б-! дерева. Так что Б-деревья растут несколько странно: от листьев к корню.

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