- •Глава 5. Организация интерфейса пользователя в информационных системах 72
- •Глава 1. Производство. Информация. Общество
- •1.1. Информатизация общества
- •1.2. Информационный характер процесса управления производством
- •1.3. Элементы субъекта управления и функции управления
- •1.4. Уровни управления и информация
- •1.5. Превращение информации в ресурс общества
- •Глава 2. Понятие информационной системы
- •2.1. Общая характеристика информационной системы
- •2.2. Классификация информационных систем
- •2.3. Хранение данных как важнейшая общая задача ис
- •Глава 3. Фактографические информационные системы
- •3.1. Основные понятия
- •3.2. Проектирование структуры данных3
- •3.3. Логическое проектирование структур данных
- •3.4. Физическое проектирование структур данных
- •3.4.1. Методы физического проектирования для реляционных моделей
- •3.4.1.1. Последовательная организация
- •3.4.1.2. Индексно-последовательная организация
- •3.4.1.3. Индексно-произвольная организация
- •3.4.1.4. Рандомизация
- •3.4.1.5. Цепь подобных записей
- •3.4.1.6. Инвертированные файлы
- •3.4.2. Методы физического проектирования для иерархических моделей
- •3.4.2.1. Множественные ссылки на порожденные записи
- •3.4.2.2. Ссылки на подобные и порожденные записи
- •3.4.2.3. Кольцевые структуры
- •3.4.2.4. Справочники
- •3.4.2.5. Битовые отображения
- •3.4.3. Методы физического проектирования для сетевых моделей
- •3.4.3.1. Множественные ссылки на порожденные записи
- •Кафедра должность
- •3.4.3.2. Ссылки на подобные и порожденные записи
- •3.4.3.3. Кольцевые структуры
- •Выполнение поисковых задач осуществляется аналогично иерархическим структурам.
- •3.4.3.5. Справочники
- •3.4.3.6. Битовые отображения
- •Глава 4. Документальные информационные системы
- •4.1. Методы организации хранения неструктурированных данных
- •4.1.1. Последовательные файлы
- •4.1.2. Цепочечные файлы
- •4.1.3. Инвертированные файлы
- •4.1.4. Кластерные файлы
- •4.2. Методы индексирования
- •4.2.1. Позиционные методы назначения весов
- •4.2.2. Статистические методы назначения весов
- •4.2.2.1. Частотные модели
- •4.2.2.2. Модель, учитывающая различительную силу термина
- •4.2.3. Динамический метод назначения весов
- •4.3. Кластеризация текстов
- •4.4. Поиск релевантных текстов
- •4.4.1. Поиск в инвертированных файлах
- •4.5.2. Поиск при кластерной организации хранения
- •4.5. Методы расширенного поиска
- •4.5.1. Построение словаря синонимов
- •4.5.2. Ассоциативное индексирование терминов
- •4.5.3. Вероятностное индексирование терминов
- •Глава 5. Организация интерфейса пользователя в информационных системах
- •5.1. Типы диалогов
- •5.2. Эргономичность интерфейса
- •Индивидуальные задания Реляционные модели
- •Деревья
- •Литература
3.4. Физическое проектирование структур данных
В данном разделе рассмотрим способы организации хранения на машинных носителях информационных массивов, отражающих одну из рассмотренных логических моделей данных. Каждый раз при решении вопроса о выборе способа структуризации файла, основным критерием является последующая минимизация времени доступа к данным по запросам пользователя, который включает, в общем случае, наименование и значение ключевого поля. Для этого часто вводятся дополнительные массивы данных, что ведет к перерасходу объемов внешней памяти, но позволяет оптимизировать доступ к данным.
3.4.1. Методы физического проектирования для реляционных моделей
Поскольку для реляционных структур существуют вторичные и первичные ключи, которые используются при поиске данных, различают методы физического проектирования для доступа по первичному и вторичному ключу. При рассмотрении каждой физической модели одновременно будет обсуждаться вопрос доступа к данным, что является основным критерием при решении вопроса о структурах хранения.
Для доступа по первичному ключу различают модели: последовательная организация, индексно-последовательная организация, индексно-произвольная организация, рандомизация. Для доступа по вторичному ключу выделяют модели: цепь подобных записей и инвертированные файлы.
3.4.1.1. Последовательная организация
Записи файла соответствуют логической модели данных. Число реляционных структур (таблиц) соответствует числу файлов. Доступ к записям осуществляется тремя способами: последовательным сканированием, блочным, двоичным.
При последовательном сканировании записи файла могут быть неупорядочены по первичному ключу. Для обозначения значения ключевого поля в запросе введем нотацию Кдоступ. Последовательно, начиная с первой записи, сравнивается ключ каждой записи файла К с ключом доступа Кдоступ. При равенстве обоих ключей требуемая запись найдена: содержащаяся в ней информация полностью или частично выводится пользователю. Если же равенство не выполняется, последующие шаги алгоритма различаются для упорядоченного и неупорядоченного файла:
для неупорядоченного файла сравнение повторяется до достижения его конца. В этом случае, если совпадения ключей так и не было, делается вывод об отсутствии нужной записи;
для упорядоченного файла проверяется условие, например, превышения значения ключа доступа Кдоступ значения ключа К: если файл упорядочен по возрастанию, поиск продолжается; если по убыванию – поиск прекращается ввиду отсутствия нужной записи.
При блочном способе записи файла должны быть упорядочены по первичному ключу. Для удобства дальнейшего изложения предположим (здесь и далее по реляционным моделям), что упорядочение выполнено по возрастанию значения ключа.
Файл разделяется на виртуальные блоки размером N записей, где N – число записей в файле. С ключом доступа Кдоступ сравниваются ключевые поля последних записей в блоках - Кjблока, начиная с первого блока (j – номер блока). С помощью такого сравнения вначале определяется блок, в котором возможно нахождение нужной записи (для этого требуется выполнение условия Кдоступ < Кjблока)5, а затем уже, как правило, методом последовательного сканирования - сама запись в блоке.
При двоичном способе записи файла также должны быть упорядочены по первичному ключу. Файл последовательно делится на две части, уменьшая пространство поиска каждый раз вдвое. Ключ доступа Кдоступ сравнивается с ключевым полем «средней» записи - Кср. Здесь возможны варианты:
Кдоступ=Кср; «средняя» запись является искомой, алгоритм заканчивает работу;
Кдоступ>Кср; поиск продолжается в той половине файла, где первичные ключи имеют бóльшие значения;
Кдоступ<Кср; поиск продолжается в той половине файла, где первичные ключи имеют мéньшие значения.
Продолжение поиска заключается вновь в делении выбранной половины файла пополам и т.д. Алгоритм заканчивает работу при нахождении нужной записи или при условии, когда очередная «половина» файла содержит только одну запись, ключевое поле которой не совпадает с Кдоступ. Делается вывод об отсутствии нужной записи в файле.