<< Пред.           стр. 5 (из 8)           След. >>

Список литературы по разделу

 F2(0тдел #, ПРИ, Таб№сотр),
 FЗ(Код_проекта #, Датанач, Датакон, Стоимость),
 F4(ФИО #, Отдел),
 F5(Код_проекта #, Работа #, ФИО #, Прод),
 F6(Код_проекта #, Заказ #, ГИП).
 
 2. У всех пар файлов, полученных на шаге 1, проверяется условие для ключей (Кi является частью Кj)). Если оно соблюдается, то из соответствующих файлов создается веерное отношение Wij(Fi,Fj).
 В нашем примере получим W35(FЗ,F5), W45(F4,F5), W36(FЗ,F6).
 Если на шаге 2 будут получены два веерных отношения Wij, Wjk то все атрибуты файла Fi передаются в файл Fj, и Fi вместе с Wij уничтожаются. В нашем примере таких веерных отношений нет.
 Атрибуты, не вошедшие в состав веерных отношений на шаге 2, добавляются в те файлы Fn (и содержащие Fn веерные отношения), где они будут неключевыми. При наличии нескольких подходящих файлов предпочтение отдается основным файлам. Если требуемые Fn отсутствуют, то создается новый файл из атрибутов первичного ключа, и повторяются шаги 2,3,4.
 В нашем примере F4 расширяется атрибутами ПРИ, Директор, Адрес, Таб№сотр.
 На рис.2.3 показана структура соответствующей двухуровневой БД.
 Структуры основных отношений показаны в верхней части рисунка, а структуры зависимых отношений - внизу.
 Перед рассмотрением операций в сетевой базе данных следует отметить, что существуют 2 различных подхода к обработке данных средствами СУБД.
 Для сетевой БД характерен принципом доступа к данным, называемый навигационным.
 Центральным для навигационного принципа доступа является понятие "текущая запись" в отношениях базы данных.
 Текущей записью в отношениях после выполнения некоторой операции является значение отношения, на котором операция завершилась. Следующая операция начинается с этой текущей записи, а в результате выполнения операции положение текущей записи изменяется (завершение операции может изменить положение текущей записи и в других отношениях).
 Для сетевой базы данных характерна такая операция, как выборка.
 
 
 
 ФИО
 Отдел#
 ПРИ
 Директор
 Адрес
 Таб№сотр Код_проекта#
 Датанач
 Датакон
 Приор
 
 
 
 Код_проекта#
 Работа#
 ФИО#
 Прод Код проекта#
 Заказ#
 ГИП
 
 Рис. 9. Сетевая БД со сведениями о проектных работах
 
 
 § 2.2.4. Иерархическая модель данных
 
 Иерархическая модель данных имеет много общих черт с сетевой моделью данных, хронологически она появилась даже раньше, чем сетевая. Допустимыми информационными конструкциями в иерархической модели данных являются отношение, веерное отношение и иерархическая база данных. В отличие от ранее рассмотренных моделей данных, где предполагалось, что информационным отображением одной предметной области является одна база данных, в иерархической модели данных допускается отображение одной предметной области в несколько иерархических баз данных.
 Понятия отношения и веерного отношения в иерархической модели данных не изменяются.
 Иерархической базой данных называется множество отношений и веерных отношений, для которых соблюдаются два ограничения.
 1. Существует единственное отношение, называемое корневым, которое не является зависимым ни в одном веерном отношении.
 2. Все остальные отношения (за исключением корневого) являются зависимыми отношениями только в одном веерном отношении.
 Схема иерархической БД по составу компонентов идентична сетевой базе данных. Названные выше ограничения поддерживаются иерархическими СУБД.
 На рис. 10 изображена структура иерархической базы данных, удовлетворяющая всем ограничениям, указанным в определении.
 Ограничение, которое поддерживается в иерархической модели данных, состоит в невозможности нарушения требований, фигурирующих в определении иерархической базы данных. Это ограничение обеспечивается специальной укладкой значений отношений в памяти ЭВМ. Ниже мы рассмотрим одну из простейших реализаций укладки иерархической БД.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Рис. 10. Иерархическая база данных
 
 На рис. 11 приводится линейная организация значений из иерархической базы данных, структура которой показана на рис. 10.
 Необходимо отметить, что существуют различные возможности прохождения иерархически организованных значений в линейной последовательности. Принцип, применяемый для иерархических баз данных, называется концевым прохождением.
 Правила концевого прохождения:
 1. Начиная с первого значения корневого отношения, перечисляются первые значения соответствующих отношений на каждом уровне вплоть до последнего.
 2. Перечисляются все значения в том веерном отношении, на котором остановился шаг 1.
 3. Перечисляются значения всех вееров этого веерного отношения в иерархической базе данных:
 4. От достигнутого уровня происходит подъем на предыдущий уровень, и если возможно применить шаг 1, то процесс повторяется.
 Записью иерархической базы данных называется множество значений, содержащих одно значение корневого отношения и все вееры, доступные от него в соответствии со структурой иерархической базы данных.
 Для веерных отношений в составе иерархической базы данных справедлива уже известная закономерность: если существует веерное отношение, то ключ зависимого отношения функционально определяет ключ основного отношения, и наоборот, если ключ одного отношения функционально определяет ключ второго отношения, то первое отношение может быть зависимым, а второе - основным в некотором веерном отношении.
 
 
 Запись 1
 
 Б=01 Лаб=01 Лаб=02 Пал=01 Пац=01 … Пац=04 Пал=02 Пац=01
 
 … Пац=06 … Пал=20 Пац=01 … Пац=04 Вр=01 Вр=02
 
 … Вр=40
 Запись 2
 Б=02 Лаб=01 Лаб=02 Пал=01 Пац=01 … Пац=05 Пал=02 Пац=01
 
 … Пац=04 … Пал=30 Пац=01 … Пац=04 Вр=01 Вр=02
 
 … Вр=60
 
 
 Рис. 11. Линейное представление значений
 
 Кроме того, ограничение на существование единственного корневого отношения в иерархической базе данных трансформируется в требование: первичный ключ каждого некорневого отношения должен функционально определять первичный ключ корневого отношения.
 
 § 2.3. Сравнение моделей данных
 
 На окончательный выбор моделей данных влияют многие дополнительные факторы, например, наличие хорошо зарекомендовавших себя СУБД, квалификация прикладных программистов, размер баз данных и прочее.
 Например одна и та же задача может быть реализована различными моделями данных, что представлено на рис. 12.
 Рассмотрим преимущества и недостатки известных моделей данных.
 
 Реляционная модель
 Преимущества:
 Простота. В реляционной модели всего одна информационная конструкция (двухуровневое отношение), которая формализует табличное представление данных, привычное для пользователей-экономистов.
 Теоретическое обоснование. Наличие теоретически обоснованных методов нормализации отношений и проверки БД на ацикличность позволяет получать базы данных с заданными характеристиками.
 Независимость данных. Когда необходимо изменить структуру реляционной БД, это, как правило, приводит к минимальным изменениям в прикладных программах.
 Недостатки:
 Низкая скорость при выполнении операции соединения.
 Большой расход памяти для представления реляционной БД. Хотя проектирование в ЗНФ рассчитано на минимальную избыточность, другие модели данных обеспечивают меньший расход памяти для представления тех же фактов. Например, длина адреса связи обычно намного меньше, чем длина значения атрибута.
 
 
 Иерархическая модель
 Преимущества:
 Простота. Хотя модель использует три информационные конструкции, иерархический принцип соподчиненности понятий является естественным для многих экономических задач (например, организация статистической отчетности).
 Минимальный расход памяти. Для задач, допускающих реализацию с помощью любой из трех моделей данных, иерархическая модель позволяет получить представление с минимально требуемой памятью.
 Недостатки:
 Неуниверсальность. Многие важные варианты взаимосвязи данных невозможно реализовать средствами иерархической модели, или реализация связана с повышением избыточности в базе данных.
 Допустимость только навигационного принципа доступа к данным.
 Доступ к данным производится только через корневое отношение.
 
 Сетевая модель
 Преимущества:
 Универсальность. Выразительные возможности сетевой модели данных являются наиболее обширными в сравнении с остальными моделями.
 Возможность доступа к данным через значения нескольких отношений (например, через любые основные отношения).
 Недостатки:
 Сложность, т.е. обилие понятий, вариантов их взаимосвязей и особенностей реализации.
 Допустимость только навигационного принципа доступа к данным.
 Результаты, полученные для ациклических баз данных, позволяют говорить о равноценных возможностях представления информации в ациклических реляционных БД, двухуровневых сетевых БД и иерархической БД без логических связей.
 При анализе моделей данных не затрагивалась проблема упорядоченности значений в отношениях баз данных. Для реляционной модели данных эта упорядоченность с теоретической точки зрения необязательна, а в двух других моделях она широко используется для повышения эффективности реализации запросов.
 
 
  Проект
 
 № проекта Название Местоположение
 
 
  Поставщик
 
 № поставщика Наименование Местонахождение
 
 
  Деталь
 
 № детали Наименование Вес Количество
 
 Иерархическая модель
 
 Проект (№ проекта, название, местоположение);
 Поставщик (№ поставщика, наименование, местонахождение);
 Деталь (№ детали, наименование, вес);
 Поставка (№ проекта, № поставщика, № детали, количество).
 
 Реляционная модель
 
 
 Проект Поставщик
 
 № пректа Название Местопо-ложение № поставщика Наимено-вание Местонахож-дение
 
 
  Поставка
 
 
 
 
  Деталь
 
 № детали Наименование Вес
 
 Сетевая модель
 
 
 Рис. 12. Различные модели данных для реализации одной задачи
 
 В последнее время реляционные СУБД заняли преимущественное положение как средство разработки ЭИС. Недостатки реляционной модели компенсируются ростом быстродействия и ресурсов памяти современных ЭВМ. Вследствие процессов децентрализации управления в экономике многие базы данных ЭИС имеют простую структуру, которая легко трансформируется в понятие системы таблиц (отношений).
 
 
 § 2.4. Модель инвертированных файлов и
 информационно-поисковые системы
 
 Основными информационными конструкциями в модели инвертированных файлов являются основной файл, который соответствует ранее введенному понятию “отношения”, “информационный файл” и “список связи”.
 Множество основных файлов базы данных обозначим через {F1, F2,...,Fn}. Все записи файлов F1...Fn получают в пределах базы данных единую нумерацию.
  В основном файле Fi выделяется один или несколько атрибутов, по значениям которых затем будут формироваться инвертированные файлы и списки связи. С точки зрения ранее рассмотренной реляционной модели данных выделяемый атрибут может быть как первичным, так и вторичным ключом в основном файле Fi.
 Естественно, что выделенный атрибут (обозначим его А) может принимать в Fi несколько различных значений {а(1),а(2),…,а(k)}. Поставим в соответствие каждому значению а(j) множество номеров записей файла Fi, в которых это значение связано с именем атрибута А.
 
 {а(1), n(t), n(р),...}
 {а(2), n(g), n(h),...}
 ..............................
 {а(j), n(х), n(у),..}
 ..............................
 
 Через n с соответствующим индексом обозначены номера записей из Fi.
 Определенная таким образом последовательность значений атрибута А и номеров записей основного файла Fi является инвертированным файлом, который далее будем обозначать через А(Fi).
 Чтобы определить понятие списка связи, необходимо отметить, что единая нумерация всех записей базы данных приводит к тому, что номер записи становится первичным ключом во всех основных файлах базы данных независимо от того, какие атрибуты образуют ключ в каждом из этих файлов.
 Рассмотрим два файла Fi и Fm, в структуре которых имеется общий атрибут А. В этой ситуации существуют два списка связи (Fi, Fm) и (Fm, Fi). В списке (Fi, Fm) для каждого номера записи из файла Fi указываются номера записей из файла Fm, имеющие то же самое значение атрибута А. Аналогично определяется содержимое списка связи (Fm, Fi).
 Аналогия с двухуровневой сетью заключается в следующем. Связь инвертированного файла А(Fi) и файла Fi соответствует типу "основной-зависимый". Отличия сводятся к тому, что атрибут А не имеет никакого отношения к первичному ключу Fi (в двухуровневой сети он должен быть частью первичного ключа), и, кроме того, вместе с атрибутом А в инвертированном файле запрещено хранить значения других атрибутов.
 Например, в базе данных содержатся основные файлы Магазин и Объем продаж.
 
 
 
 Магазин Объем продаж
 Название магазина Продукция Название магазина Дата Объем продаж
 01 Весна Видеокассеты 05 Вега 01.07 20
 02 Вега Аудиокассеты 06 Весна 01.07 15
 03 Альтаир Видеокассеты 07 Плаза 01.07 25
 04 Плаза Аудиокассеты 08 Альтаир 01.07 18
  09 Вега 02.07 15
  10 Весна 02.07 20
  11 Вега 03.07 25
 
 
 Инвертированный список Продукция (Магазин)
 
 Видеокассеты – 01, 03
 Аудиокассеты – 02, 04
 
 Список связи (Магазин, Объем продаж)
 01 – 05, 09, 11
 02 – 06, 10
 03 – 07
 04 - 08
 
 Преимущества модели инвертированных файлов особенно проявляются при реализации выборки с большим количеством условий. Каждое условие выборки соответствует множеству номеров записей, и комбинация условий выборки означает манипулирование ранее полученными из инвертированных файлов множествами номеров записей.
 В информационно-поисковых системах ключевые атрибуты соответствуют ключевым словам, определяющим тематику документа. Количество ключевых слов для документа может быть любым. Связь основного и инвертированного файла в этом случае выглядит иначе и показана на рис. 13.
 Пусть дан запрос: найти все документы, содержащие ключевые слова B и D. Система обратится к инвертированному файлу и найдет группы ключей B и D. Совпадающие значения номеров укажут в нашем примере на искомую запись с номером 110.
 
 Ключевые слова А, В, С, D, Е
 
 
 Номер записи Основной файл Инвертированный файл
 50 A B
 
 105 B C
 110 B D E B 50
 120 C D 105
  110
  C 105
  120
 
 
 
 
 
 
 Рис. 13. Связь основного и инвертированного файла
 
 Логические связки в запросах могут быть любыми, и с математической точки зрения требуемые поисковые операции есть операции пересечения, объединения, вычитания над множествами номеров записей, которые хранятся в инвертированных массивах для атрибутов, названных в запросе.
 Следует отметить, что поиск по инвертированному файлу обнаруживает только номера записей и плохо приспособлен для указания всех ключей, связанных с найденной записью. Между тем эта информация часто запрашивается. В одном из наших примеров запись с адресом 110 была найдена по значениям ключей B и D очень быстро, но определить, есть ли в этой записи третий ключ Е, используя только инвертированный файл, очень трудно.
 Модель инвертированных файлов служит основой для ряда современных информационно-поисковых систем. Одна база данных создается обычно для одного класса документов, которые объединены общей тематикой, например, справочная информация о предприятиях и организациях, сведения о производимой продукции, информация о происходящих выставках.
 С учетом реляционного подхода одна база данных в таком случае соответствует одному отношению.
 Значением атрибута может быть текст произвольных размеров, причем разбиение этого текста на строки может варьироваться и не должно влиять на реализацию поисковых запросов.
 Документ может сопровождаться графической иллюстрацией, и в таком случае ее предоставление определяется средствами компьютерной графики. Изображение не является значением какого-то атрибута в общепринятом смысле слова, поскольку как значение не может участвовать в операциях выборки.
 Из всего многообразия реализаций информационно-поисковых языков модели инвертированных файлов соответствуют дескрипторные языки.
 Дескриптором, или ключевым словом, называется слово или словосочетание, используемое для краткого обозначения темы документа, хранящегося в базе данных информационно-поисковой системы. Конкретный документ может сопровождаться несколькими дескрипторами в зависимости от количества характеризующих его терминов.
 Получение списка дескрипторов для каждого конкретного документа является достаточно сложной и трудоемкой задачей, которую обычно решают специалисты в той области знаний, которой посвящена информационно-поисковая система.
 Один из более простых подходов к определению списка дескрипторов для всех документов в базе данных заключается в том, что из всех атрибутов документа выбирается несколько наиболее информативных, и все слова, составляющие значения таких атрибутов, переносятся в список дескрипторов. Разумеется, при таком методе получения дескрипторов должна быть исключена ситуация попадания в дескрипторы явно неинформативных частей речи (предлогов, местоимений и некоторых других).
 Второй проблемой является необходимость отбрасывать в словах-дескрипторах окончания слов, чтобы употребление одного и того же термина в разных словосочетаниях не приводило к появлению множества дескрипторов, различных по написанию, но обозначающих одно и то же понятие.
 В каждой информационно-поисковой системе должна присутствовать административная подсистема и поисковая подсистема.
 Административная подсистема предназначена для организации новых баз данных, определения структуры вводимых в них записей, ввода подготовленных документов в базы данных в соответствии с определенными структурами, а также для создания главного инвертированного файла - основного средства ускорения поиска требуемой информации в ИПС с помощью ключевых слов.
 Модель инвертированных файлов можно рассматривать как частный случай сетевой двухуровневой модели данных. Произведенные упрощения двухуровневой сети позволили создать еще более понятную прикладным программистам и пользователям модель данных.
 
 Вопросы и задания
 1. Назовите компоненты моделей данных.
 2. Приведите схемы реляционной, сетевой и иерархической моделей данных.
 3. Назовите операции, выполняемые над отношениями в реляционной модели данных.
 4. Что такое натуральное соединение?
 5. Как выполняется деление отношений и что такое «образ»?
 6. Какова цель нормализации отношений?
 7. Приведите примеры отношений в 1НФ, 2НФ, 3НФ.
 8. По какому принципу организовано веерное отношение?
 9. Назовите правила концевого прохождения?
 10. Определите отношение в третьей нормальной форме для следующего списка атрибутов и функциональных зависимостей.
  а)
  Атрибуты Функциональные зависимости
 
  ФИО вкладчика № сберкнижки ? ФИО
  № сберкнижки № сберкнижки, Дата ? Расход
  Дата № сберкнижки, Дата ? Расход
  Приход № сберкнижки, Дата ? Остаток
  Расход № сберкнижки, Дата ? Приход, Расход, Остаток
  Остаток № сберкнижки, Дата ? Приход
 
  б)
  Атрибуты Функциональные зависимости
 
  Таб. номер Участок ? Цех
  ФИО Таб. номер ? Цех
  Цех Таб. номер ? Участок
  Дата Таб. номер, Дата ? Сумма
  Участок Таб. номер ? ФИО
  Сумма Таб. номер, ФИО ? Участок
 ГЛАВА 3. МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ
 
 §3.1. Анализ алгоритмов и структур данных
 

<< Пред.           стр. 5 (из 8)           След. >>

Список литературы по разделу