Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«Калининградский государственный технический университет»
Кафедра систем управления и вычислительной техники
Топоркова О.М.
ИНФОРМАЦИОННЫЕ СИСТЕМЫ
Конспект лекций
для специальности «Прикладная информатика в экономике»
Калининград
2007
Оглавление
|
[1] [1.1] 1.1. Информатизация общества [1.2] 1.2. Информационный характер процесса управления производством [1.3] 1.3. Элементы субъекта управления и функции управления [1.4] 1.4. Уровни управления и информация [1.5] 1.5. Превращение информации в ресурс общества
[2] [2.1] 2.1. Общая характеристика информационной системы [2.2] 2.2. Классификация информационных систем [2.3] 2.3. Хранение данных как важнейшая общая задача ИС [3] Глава 3. Фактографические информационные системы [3.1] 3.1. Основные понятия [3.2] 3.2. Проектирование структуры данных [3.3] 3.3. Логическое проектирование структур данных [3.4] 3.4. Физическое проектирование структур данных [3.4.1] 3.4.1. Методы физического проектирования для реляционных моделей [3.4.1.1] 3.4.1.1. Последовательная организация [3.4.1.2] 3.4.1.2. Индексно-последовательная организация [3.4.1.3] 3.4.1.3. Индексно-произвольная организация [3.4.1.4] 3.4.1.4. Рандомизация [3.4.1.5] 3.4.1.5. Цепь подобных записей [3.4.1.6] 3.4.1.6. Инвертированные файлы [3.4.2] 3.4.2. Методы физического проектирования для иерархических моделей [3.4.2.1] 3.4.2.1. Множественные ссылки на порожденные записи [3.4.2.2] 3.4.2.2. Ссылки на подобные и порожденные записи [3.4.2.3] 3.4.2.3. Кольцевые структуры [3.4.2.4] 3.4.2.4. Справочники [3.4.2.5] 3.4.2.5. Битовые отображения [3.4.3] 3.4.3. Методы физического проектирования для сетевых моделей [3.4.3.1] 3.4.3.1. Множественные ссылки на порожденные записи [3.4.3.2] кафедра должность [3.4.3.3] 3.4.3.2. Ссылки на подобные и порожденные записи [3.4.3.4] 3.4.3.3. Кольцевые структуры [3.4.3.5] Выполнение поисковых задач осуществляется аналогично иерархическим структурам. [3.4.3.6] 3.4.3.5. Справочники [3.4.3.7] 3.4.3.6. Битовые отображения
[4] [4.1] 4.1. Методы организации хранения неструктурированных данных [4.1.1] 4.1.1. Последовательные файлы [4.1.2] 4.1.2. Цепочечные файлы [4.1.3] 4.1.3. Инвертированные файлы [4.1.4] 4.1.4. Кластерные файлы [4.2] 4.2. Методы индексирования [4.2.1] 4.2.1. Позиционные методы назначения весов [4.2.2] 4.2.2. Статистические методы назначения весов [4.2.2.1] 4.2.2.1. Частотные модели [4.2.2.2] 4.2.2.2. Модель, учитывающая различительную силу термина [4.2.3] 4.2.3. Динамический метод назначения весов [4.3] 4.3. Кластеризация текстов [4.4] 4.4. Поиск релевантных текстов [4.4.1] 4.4.1. Поиск в инвертированных файлах [4.4.2] 4.5.2. Поиск при кластерной организации хранения [4.5] 4.5. Методы расширенного поиска [4.5.1] 4.5.1. Построение словаря синонимов [4.5.2] 4.5.2. Ассоциативное индексирование терминов [4.5.3] 4.5.3. Вероятностное индексирование терминов
[5] [5.1] 5.1. Типы диалогов [5.2] 5.2. Эргономичность интерфейса
[6]
[7] |
Процессы информатизации, происходящие в современном обществе, выражаются в широком внедрении средств вычислительной техники и программного обеспечения с целью автоматизации обработки информации. Информатизация общества выражается в информатизации, в частности, следующих основных его систем и соответствующих типичных задач (перечень неполный, хотя и охватывает все основные системы):
Процесс информатизации происходит на разных уровнях общества, включая соответствующие задачи:
Основные социально-экономические проявления информатизации выражаются в следующем:
В процессе информатизации общества необходимо решить следующие задачи:
Наиболее значимый объект информатизации – производство. Оно является источником экономического эффекта, и в нем наиболее сложны и многообразны процессы обработки информации.
Производство – это организационно-экономическая и технологическая деятельность, отличающаяся единством целей функционирования, технологий, входных и выходных продуктов труда.
Любое производство существует в условиях взаимодействия с окружающей средой через информационные и ресурсные (материальные) связи. Схема такого взаимодействия показана на рис. 1.1.
Информация о внешней среде
Цель Осведомляющая информация
Входной материальный поток Готовая продукция
Ресурс Технологии
Обозначения:
- материальная связь; - информационная связь.
Рис. 1.1 - Схема взаимодействия производства с внешней средой
Цель – это желаемое состояние системы, отражающее волю субъекта управления и имеющее строго определенный срок существования. Она определяет функционирование производства, регламентируя то, что должно быть произведено. Цель связана с понятиями стратегии и показателя: стратегия – образ действия, обеспечивающий достижение поставленной цели; показатель - измеритель степени достижения цели.
Входной материальный поток – это предметы труда, на преобразование которых в соответствии с заданной целью направлено производство.
Осведомляющая информация – данные, отражающие состояние результата производства продукции.
Информация о внешней среде – данные, определяющие функционирование производства в условиях внешних воздействий.
Готовая продукция – целевой материальный поток произведенной продукции.
Ресурс – материальные, кадровые, финансовые и другие средства, необходимые для реализации цели (энергия, сырье, персонал и т.д.).
Технология – позволяет входной материальный поток с привлечением ресурса превратить в готовую продукцию. Включает: отдельные операции и их логическое следование во времени; инструментальную среду, с помощью которой выполняется преобразование входного материального потока; информационную среду как совокупность специальной терминологии, характерной для той или иной технологии; систему управления деятельностью по преобразованию входного материального потока.
Совокупность технологий, ресурсов и входного материального потока формирует технологический процесс производства.
Примером производства может служить подготовка специалистов учебными заведениями высшей школы - вузами. Во времена плановой экономики целью функционирования вуза являлась подготовка специалистов для нужд народного хозяйства. Однако в условиях рыночных отношений цель поменялась - это удовлетворение потребностей членов общества в знаниях. Смена цели в данном примере отвечает приведенному свойству ее срочности. Входной материальный поток в обоих случаях – это граждане общества, которые, будучи зачисленными в вуз, стали его студентами, готовая продукция – это специалисты, получившие диплом о высшем образовании. Ресурсы – это преподаватели и технический персонал, аудитории, лаборатории и т.д. Технологии обучения включают: операции по обучению (проведение занятий в форме лекций, лабораторных и практических занятий, семинаров и т.п.) и контролю знаний студентов (экзамены, зачеты, тесты); технические средства обучения (например, компьютеры как средство автоматизированного тестирования), методическое обеспечение учебного процесса – как инструментальную среду; специальную терминологию, включающую такие понятия как сессия, переэкзаменовка, академический отпуск и т.д., – как информационную среду; взаимодействие преподавателей и студентов во время учебного процесса – как систему управления учебной деятельностью. Осведомляющая информация содержит данные о качественном и количественном выпуске специалистов, о расходовании фонда заработной платы и т.д. Информация о внешней среде включает, в частности, сведения о перспективах развития экономики в регионе или в стране, что позволяет вузам открывать новые специальности; о прогнозируемой демографической обстановке и т.п.
Важнейшую роль в производстве играют информационные связи, с помощью которых переносится информация. Информация – это одно из наиболее общих понятий науки, обозначающее некоторые сведения об окружающем мире (объекте, процессе, явлении, событии), которые используются при управлении или регулировании, осуществляемом живым организмом или искусственно созданной системой (такие системы называются кибернетическими) путем преобразования входной информации в выходную.
Например, выходя утром из дома, мы слушаем по радио прогноз погоды на день и принимаем решение о том, понадобится ли нам зонт. В этом случае информация, содержащаяся в прогнозе, является входной. Она влияет на наше решение, которое рождается в недрах собственного сознания в виде другой, выходной информации, например, в форме фразы: «возьму-ка я зонтик, поскольку давление понижается».
В деятельности вуза как одной из форм производства и одновременно искусственно созданной системе также применяется информация. Например, преподаватель использует ответ студента в качестве входной информации для принятия решения об итоговой оценке за экзамен, которая выполняет функцию выходной информации.
В практике современных сложных производственных предприятий типовыми видами деятельности являются:
Часто производство рассматривается как система, состоящая из двух подсистем:
Это позволяет представить производство схемой рис. 1.2.
Информация о внешней среде
Цель Осведомляющая информация
Управляющая Информация
информация о состоянии ОУ
Входной материальный Готовая продукция
поток
Ресурс Технологии
Производство
Рис. 1.2 - Производство как система взаимодействия объекта и субъекта
управления
Как видно из рисунка, субъект и объект управления связаны управляющей информацией (прямая связь между СУ и ОУ) и информацией о состоянии объекта (обратная связь). Прямая связь позволяет доводить до ОУ управленческие решения, что обеспечивает функционирование производства для реализации цели, а обратная связь снабжает СУ информацией, позволяющей вырабатывать эти решения адекватными состоянию объекта управления.
В качестве объекта управления в вузе может рассматриваться учебный процесс (технологический процесс на рисунке 1.2), в котором участвуют студенты (входной материальный поток - продукт производства), преподаватели и аудитории как некоторые из видов ресурсов данного производства, лекционные и практические занятия как разновидности операций технологии обучения. Субъект управления в вузе – это ректор и ректорат, деканаты, учебная часть и т.п.
Рис. 1.2 показывает, что с информацией, в основном, связан субъект управления. Его элементами служат:
Сами производственные задачи по степени сложности и возможности их автоматизации делятся на три вида:
Примером структурированной задачи может служить назначение стипендий в студенческой группе по результатам сессии. В самом деле, алгоритм ее решения достаточно ясен, входные данные – это оценки за экзамены, размер базовой стипендии и правила назначения надбавок, а выходные – список фамилий студентов с назначенными стипендиями.
Неструктурированная задача, например, - это задача формирования рабочей группы для реализации некоторого проекта. Для ее решения необходимо включить в группу профессионалов различного уровня квалификации и распределить их на разные, наиболее подходящие для них, направления работ, учитывая при этом фактор человеческих взаимоотношений в коллективе. Опытный руководитель часто и успешно решает подобные задачи, но автоматизировать их практически невозможно.
Частично структурированная задача может быть проиллюстрирована задачей составления расписания занятий в вузе, которая успешно решается специалистами диспетчерской службы. Одновременно существуют известные алгоритмы составления расписания, которые могут быть использованы для автоматизации.
Стандартные процедуры отвечают следующим функциям управления:
Взаимосвязь функций управления показана на рис. 1.3. В результате выполнения каждой из них формируется определенная информация, названная далее по имени соответствующей функции.
Обозначения:
Рис. 1.3 - Взаимосвязь функций управления
Учетную функцию выполняет, в частности, преподаватель, когда отмечает в учетной карточке группы присутствующих на лекции студентов. Учетная информация – это отметки о присутствии или отсутствии студентов. Контроль тогда состоит в выделении отсутствующих студентов в общем списке, поскольку, как правило, посещение лекций является обязательным (т.е. плановым) для студентов. Контрольная информация в этом случае может фиксироваться в памяти преподавателя или в виде выписки с фамилиями отсутствующих. Поскольку причина отсутствия студента может быть уважительной, за контролем следует анализ, в результате которого вырабатывается аналитическая информация, например, в виде записи о причине отсутствия. Предположим, что отсутствие студента вызвано непосильной учебной нагрузкой, заложенной в учебном плане, что привело к физическому срыву и болезни. Тогда следует пересмотреть нормы нагрузки, что выполняется при нормировании процесса обучения. Нормативная информация тогда – это часовые нормы, выделяемые на выполнение самостоятельной работы и аудиторной нагрузки студента. Следует отметить, что нормирование – не обязательная функция СУ. Часто нормы и нормативы «спускаются» на производство из вышестоящей организации, например, общее число часов на обучение, состав обязательных дисциплин и т.п. зафиксированы в Государственном образовательном стандарте специальности или направления. После получения таких норм и нормативов следует планирование учебного процесса – составление учебного плана для специальности конкретного года приема (это долгосрочное планирование – на все время обучения), разработка планов обучения на семестр в виде расписания занятий (это текущее планирование), а также оперативное планирование, например, дополнительных занятий со студентами отдельным преподавателем. Совокупность всех планов составляет плановую информацию. Когда планы составлены, следует организационная функция. Она заключается, например, в вывешивании расписания занятий для студентов, информировании преподавателей об их нагрузке и т.д. Можно сказать, что организационная информация есть управляющая информация для ОУ (по крайней мере, в данном случае).
Показанные на рис. 1.3 управляющие связи – это сигналы о возможности начала выполнения следующей функции. По существу это также информационные связи, но количество информации в них минимально – она может быть представлена лишь одним битом.
Процессы управления, осуществляемые в СУ, в зависимости от решаемых задач делятся на уровни:
Стратегический уровень управления в вузе связан с решением задач открытия новых специальностей и закрытия прежних, созданием новых кафедр и факультетов и другими «крупными» задачами. Они связаны с выживанием на рынке образовательных услуг и с процветанием учебного заведения. Тактический уровень предполагает «сведение» студенческих потоков с наиболее квалифицированными преподавателями, с размещением учебных занятий в наиболее подходящих помещениях и т.п. Управление технологическими процессами выполняется, в основном, преподавателями путем учета, контроля, анализа (эти примеры приводились ранее), планирования и организации дополнительных учебных занятий.
Уровни управления связаны с агрегированностью информации: чем выше уровень, тем больше период обновления информации и степень ее агрегирования.
В самом деле, такая подробная информация о работе студента в течение семестра, как его посещаемость и оценки за самостоятельные и домашние задания, вряд ли интересует руководство высшего звена вуза. А вот агрегированная информация о трудоустройстве выпускников позволяет принимать решения о востребованности той или иной специальности и корректировать наборы абитуриентов.
Распределение функций управления по уровням показано на рис. 1.4. Следует иметь в виду, что представленная структура свойственна каждому виду деятельности, причем между такими структурами также существуют информационные связи. Понятно, насколько сложны и многообразны информационные связи. Это обуславливает важность автоматизации соответствующих информационных процессов.
В современном обществе постепенно формируется такая его часть, предметом труда которой становится не материальный объект, а информация. В этой связи происходит постепенное перераспределение трудовых ресурсов из сферы материального производства в сферу
АИ, КИ, УИ ПИ, НИ, ОИ
АИ, КИ, УИ ПИ, НИ, ОИ
Рис. 1.4 - Взаимосвязь функций управления по уровням
информационного обслуживания: так, в начале 20 века информационной деятельностью занимались 10% населения, в конце 20 века – около 50%.
В постиндустриальной экономике традиционная промышленность по показателям занятости и доле в национальном продукте постепенно уступает ведущее место сфере услуг, которая основывается преимущественно на обработке информации и производстве знаний.
Основной сферой накопления и использования капиталовложений во все большей мере становится человеческий капитал, как движущая сила бесконечных по своей природе информационных ресурсов (в отличие от ограниченных природных ресурсов). Вспомним в этой связи ряд характерных черт информации: ее возможность накапливаться, когда одно знаний порождает другое, – именно это является основой прогресса и в области науки, и в области техники; ее способность повышать ценность других ресурсов, в частности, трудовых, и вызывать к жизни новые производства.
Важнейшее положение, характеризующее сущность "нового экономического порядка" в информационном обществе, таково: отныне конкурентоспособность и процветание предприятий любых отраслей зависят не столько от материальных ресурсов (занимаемой территории, количества зданий и цехов, производительности станков и машин), сколько от эффективности их организации и управления, наличия развитых средств коммуникации и кооперации с клиентами и партнерами, объема накопленных сотрудниками профессиональных знаний и умений, а также возможностей их интенсивного использования.
Превращение информации в ресурс выражается в следующих фактах:
Эти тенденции заставляют по-новому относиться к процессу накопления, хранения и использования информации.
Если информация становится предметом труда, то в результате этой трудовой деятельности возникает новый вид ресурса – информационный. Возникают производства, занятые выпуском информации (рис. 1.5):
Информация о внешней среде
Цель Осведомляющая информация
Входной информационный Готовая продукция-
поток информационный ресурс
Ресурс Технологии
Рис. 1.5 - Структура информационного производства
Информационный ресурс отражает интеллектуальный потенциал общества и переходит в экономическую категорию. Его уровень определяет эффективность развития практически всех отраслей экономики любой страны: это означает, что он приобретает национальный характер.
Отличительными особенностями информационного ресурса являются следующие:
Таким образом, информация становится стратегическим ресурсом общества в целом. Его использование возможно за счет информатизации общества, для чего должны быть выполнены условия: использование средств вычислительной техники во всех общественно значимых сферах общества; поднятие престижа интеллектуальной деятельности в информационной сфере общества; охват информацией всех слоев общества.
Различают два вида информационных ресурсов – данные и знания.
Данные – это полученные эмпирическим путем и зафиксированные факты, дискретно описывающие источник информации (говорят – предметную область ПО), т.е. характеризующие отдельные его свойства.
Знания – это закономерности источника информации (понятия, сведения, принципы, связи, законы), полученные или приобретенные в результате обучения, практической деятельности и профессионального опыта, позволяющие специалистам ставить и решать задачи в этой предметной области.
Формирование данных и знаний отвечает гносеологической1 цепочке приобретения знаний: факт – обобщенный факт – эмпирический закон – теоретический закон. Такой подход полностью согласуется со структурой самого знания, которое имеет два уровня: эмпирический (наблюдения, явления, т.е. факты) и теоретический (абстракции, обобщения, законы).
Примером данных могут служить сведения о результатах сдачи сессии некоторой учебной группой и о последующих решениях деканата по тому или иному студенту по поводу его последующего обучения: это факты, имеющие место в некоторой предметной области, в роли которой выступает конкретный деканат, определенная учебная группа и результаты сдачи ею сессии. Так, например, студент Х имеет двойку по дисциплине Y; студента Х отчислили из вуза. Обобщенный факт – это результат абстрагирования от конкретных характеристик предметной области: результаты сдачи любой сессии любой учебной группой являются основанием для решений произвольного деканата по каждому из студентов группы по поводу его дальнейшей судьбы в вузе. Например, студент имеет двойку по какой-либо дисциплине; студента отчислили из вуза. Эмпирический закон определяет общие правила, которыми руководствуется деканат, выявленные в результате анализа обобщенных фактов. Например, студент не сдал экзамен; студента отчисляют из вуза.2. Теоретический закон означает еще большее обобщение: он записывается с использованием кванторов «всегда», «иногда»: для каждого студента, не сдавшего экзамен, выполняется его отчисление из вуза.
Таким образом, данные – это простейший первичный уровень представления информации, который создает условия для получения знаний – высшей, наиболее ценной формы информации.
Методы получения информации можно разбить на три группы: эмпирические методы или методы получения эмпирических данных; теоретические методы или методы построения различных теорий; эмпирико-теоретические методы (смешанные) или методы построения теорий на основе полученных эмпирических данных.
Эмпирические методы включают:
Кроме классических форм их реализации, в последнее время используются опрос, интервью, тестирование и другие.
Эмпирико-теоретические методы включают:
Кроме указанных классических форм реализации эмпирико-теоретических методов часто используются и мониторинг (система наблюдений и анализа состояний), деловые игры и ситуации, экспертные оценки (экспертное оценивание), имитация (подражание) и другие формы.
Теоретические методы включают:
Например, для построения модели планирования и управления производством в рамках страны, региона или крупной отрасли нужно решить следующие проблемы:
Информационная система (ИС) - организационно упорядоченная совокупность данных и знаний в виде информационных массивов, а также информационных технологий, реализующих информационные процессы.
Цели внедрения ИС:
Задачи ИС делятся на общие и конкретные. Конкретные задачи зависят от предметной области, для которой предназначена система. Общие задачи связаны с общими чертами ИС и должны:
В соответствии с данными задачами структура ИС в основном включает три составляющие: информационные массивы, программное обеспечение, интерфейс (рис. 2.1).
Рис. 2.1. Структура информационной системы
Информационные массивы – это определенным образом организованные данные и знания, хранящиеся, как правило, на машинных носителях, что не исключает, однако использования бумажных носителей информации.
Программное обеспечение выполняет две основные функции: ведение информационных массивов как поддержание их в актуальном состоянии; обработка информации в соответствии с задачами того производства, на котором эксплуатируется ИС.
Интерфейс предназначен для организации диалога пользователя с ИС с целью решения определенных функциональных задач.
Эволюция информационных систем приведена в табл. 2.1.
Эволюция информационных систем
Таблица 2.1
|
Период времени |
Средства реализации |
Концепция использования информации |
Вид информационной системы |
Цель использования |
|
50–60 г.г.20 века |
Электромеханические бухгалтерские счетные машины |
Бумажный поток расчетных документов |
ИС обработки расчетных документов |
Сокращение затрат на подготовку бумажных документов, повышение качества их подготовки |
|
60-70 г.г.20 века |
Компьютеры |
Помощь в подготовке отчетов |
Управленческие ИС для производственной информации |
Ускорение подготовки отчетности, повышение качества подготовки |
|
70-80 г.г.20 века |
-«- |
Управленческий контроль реализации |
Системы поддержки принятия решений, системы для высшего звена управления |
Выработка наиболее рационального решения |
|
с 80 г.г.20 века |
Сетевые компьютеры |
Информация – стратегический ресурс, обеспечивающий конкурентное преимущество |
Стратегические ИС, автоматизированные офисы |
Выживание и процветание фирмы |
Классификация ИС выполняется по ряду признаков: по масштабу, по архитектуре, по характеру использования информации, по поддерживаемым стандартам управления и технологиям коммуникации, по степени автоматизации, по структурированности решаемых задач, по функциональному признаку, по уровням управления, по сфере применения, по типу используемой информации.
По масштабу ИС будем подразделять на однопользовательские, групповые и корпоративные:
В соответствии с архитектурой различают три класса ИС: с файл-серверной, клиент-серверной и трехслойной архитектурой.
В рамках архитектуры "клиент-сервер" существуют два основных понятия:
В зависимости от характера использования информации выделяют классы ИС:
Рассмотрим классификацию по поддерживаемым стандартам управления и технологиям коммуникации.:
В соответствии со степенью автоматизации выделяют классы ИС:
1) ручные ИС характеризуются отсутствием современных технических средств переработки информации и выполнением всех операций человеком. Например, о деятельности менеджера в фирме, где отсутствуют компьютеры, можно говорить, что он работает с ручной ИС;
2) автоматические ИС выполняют все операции по переработке информации без участия человека;
3) автоматизированные ИС предполагают участие в процессе обработки информации и человека, и технических средств, причем главная роль отводится компьютеру. В современном толковании в термин "информационная система", как правило, вкладывается понятие автоматизированной системы.
По структурированности решаемых задач ИС делятся на два класса:
Классификации ИС по функциональному признаку определяет назначение системы, ее основные цели, задачи и функции. В соответствии с этим признаком определяются следующие классы ИС:
Классификация по уровням управления соответствует приведенной ранее иерархической структуре субъекта управления. Выделяют классы ИС:
В соответствии с классификацией по сфере применения выделяют следующие виды ИС:
По типу используемой информации выделяют классы ИС:
Ранее указывались основные задачи, решаемые любой ИС. Организация хранения данных является важнейшей общей задачей, которая во многом определяет другие задачи. Она связана с обеспечением доступа к самим данным. Под доступом понимается возможность выделения элемента данных (или множества элементов) среди других элементов по каким-либо признакам с целью выполнения некоторых действий над элементом. При этом под элементом понимается как запись файла (в случае структурированных данных), так и сам файл (в случае неструктурированных данных).
Для данных любого вида доступ осуществляется с помощью специальных данных, которые называются ключевыми (ключами). Для структурированных данных такие ключи входят в состав записей файлов в качестве отдельных полей записей. Для неструктурированных данных поисковые слова или выражения входят, как правило, в искомый текст. С помощью ключей выполняется идентификация требуемых элементов в БД.
Процедура доступа к данным может быть инициирована как самой ИС (для решения каких-либо своих технических задач), так и пользователем ИС. В последнем случае пользователь формирует запрос к ИС, куда включает, в частности, обозначение требуемого вида доступа, или действия, и указание на то, над какими данными это действие надо выполнить (именно для работы с такими запросами предназначен интерфейс ИС). Как отмечалось ранее, идентификация данных осуществляется с помощью ключей. В качестве же требуемого действия может быть одно из следующих: добавление, удаление, изменение, просмотр элемента или обработка данных из элемента:
Таким образом, запрос q в общем случае имеет структуру:
q = (<действие>, <ключ> [{,<указание на составляющую элемента>[=<значение составляющей элемента>]}] ),
где скобки <> означают, что они и их содержимое в конкретных случаях заменяются некоторыми значениями; скобки [] свидетельствуют о возможном отсутствии их содержимого; скобки {} представляют возможное повторение их содержимого.
Тогда для указанных ранее действий можно определить следующие структуры запросов:
qдобавление = (<ключ> {,<указание на составляющую элемента>=<значение составляющей элемента>}),
qудаление = (<ключ>),
qизменение = (<ключ> {,<указание на составляющую элемента>=<значение составляющей элемента>}),
qпросмотр = (<ключ> [{,<указание на составляющую элемента>}]).
Чтобы выполнить любое их указанных выше действий, нужный элемент должен быть предварительно найден в БД, для чего выполняется его поиск (для добавления нового элемента тоже делается попытка его поиска, которая заканчивается неудачно, и тогда элемент добавляется). Под поиском элемента понимается определение его местонахождения в БД. Таким образом, любой доступ к элементам БД включает поиск, что делает эту фазу доступа наиболее значимой. Технологии доступа при выполнении действий добавления или изменения элемента БД показаны на рис. 2.2, технология удаления изображена на рис. 2.3, технология просмотра элемента приведена на рис. 2.4. Различие в схемах состоит в том, что по технологии рис. 2.2 выполняется воздействие на БД с целью ее изменения, для чего в БД передаются данные, по технологии рис. 2.3 воздействие на БД не связано с передачей данных, а по схеме рис. 2.4 данные выводятся из БД без изменения БД.
При выполнении рассмотренных действий над элементами БД на практике важны два фактора, противоречащие друг другу: временной фактор, в соответствии с которым запрос пользователя должен обрабатываться в минимальные сроки, и фактор минимизации требуемого объема памяти для хранения данных. Для уменьшения времени обработки запроса особые усилия прилагаются к применению таких структур хранения данных в БД, которые бы позволяли оптимизировать поисковые операции, возможно, за счет дополнительных описаний данных. Это, очевидно, повышает расход памяти. Поэтому при проектировании моделей данных БД учитывается предполагаемый режим эксплуатации ИС: если это интерактивный режим, то основное внимание уделяется минимизации времени доступа к данным, если режим пакетный, то минимизируют требуемую память. Кроме того, на выбор модели влияют особенности той предметной области, которая отражается в БД.
информационные связи
управляющие связи
Рис. 2.2. Схема доступа к БД при выполнении действий добавления или изменения элемента БД
Рис. 2.3. Схема доступа к БД при выполнении удаления элемента БД
Рис. 2.4. Схема доступа к БД при выполнении просмотра элемента БД
Данный класс ИС использует для организации информационных массивов структурированные данные, в которых отражаются отдельные факты источника информации - предметной области.
Предметная область – это часть реального мира, которая представляется с помощью информационных массивов и использующих их приложений (программного обеспечения). Это может быть предприятие в целом, некоторая его функциональная часть или подразделение, процесс, система и т.д. Предметная область моделируется с использованием понятий информационных объектов, связей между ними и функций, выполняемых этими объектами или для них.
Информационный объект – это идентифицируемый (т.е. такой, который можно выделить в предметной области) объект реального мира, понятие, процесс или явление. В роли информационных объектов в зависимости от прикладных задач, которые должна решать ИС, могут выступать люди, изделия, счета и т.д.
Информационный объект описывается с помощью характеристик, существенных для модели. Каждая из характеристик определяется именем и значением.
Например, если ИС предназначена для учета успеваемости студентов вуза, то в качестве информационного объекта можно рассматривать студента как участника учебного процесса. Его характеристиками являются фамилия, телефон (для связи деканата), средняя оценка в сессию (для назначения стипендии) и т.д. Это – имена характеристик.
Если задаться конкретным студентом, то характеристики приобретают значения. Например (в порядке перечисления характеристик), Иванов, 123456, 4.
Совокупность имени и всех значений характеристики информационного объекта называется элементом данных.
Для нашего примера элементами данных являются (в каждой строке представлен элемент данных):
фамилия (Иванов);
телефон (123456);
средний балл (4).
Если студентов трое, элементы данных приобретут вид (каждая строка по-прежнему - элемент данных):
фамилия (Иванов; Федоров; Петров);
телефон (123456, 234567, 345678);
средний балл (4, 5, 4).
Подобные данные привычнее (и удобнее) представлять таблицей:
|
фамилия |
телефон |
средний балл |
|
Иванов |
123456 |
4 |
|
Федоров |
234567 |
5 |
|
Петров |
345678 |
4 |
Здесь элементом данных является каждый столбец, который, как должен подсказывать читателю его программистский опыт, является полем данных для соответствующего файла. Видно, что структура каждого столбца единообразна: есть заголовок – суть имя характеристики информационного объекта, а также имеется множество значений данной характеристики – под заголовком.
Запись об объекте – совокупность значений элементов данных, которые описывают конкретный экземпляр объекта.
Для нашего примера, представленного таблицей, запись об объекте – это одна из строк таблицы со значениями, например,
|
Иванов |
123456 |
4 |
Очевидно, совокупность записей об объекте представляется на машинном носителе файлом, играющим роль информационного массива для структурированных данных.
Для различения экземпляров объектов в файле (т.е. записей файла) применяется идентификатор – элемент данных (или совокупность элементов данных), используемый для определения записи (или нескольких записей). Идентификация может быть уникальной (или однозначной), когда идентификатору сопоставим один экземпляр объектов, и неуникальной (многозначной), когда идентификатору сопоставимо множество (возможно, одноэлементное) экземпляров объекта.
Так, в нашем примере поля «фамилия» и «телефон» могут служить однозначным идентификатором – каждое значение соответствующей характеристики определяет только одну запись. В то же время поле «средний балл» является примером многозначного идентификатора – одинаковые результаты сдачи сессии принадлежат разным студентам.
Проектирование структуры данных для фактографических ИС является сложным процессом, включающим три самостоятельных этапа – концептуальное, логическое и физическое проектирование.
При концептуальном проектировании осуществляется выявление информационных объектов, их характеристик, взаимосвязей между ними, определение идентификаторов.
Для формального представления концептуальной модели при проектировании структуры данных используется ER4-модель. Она применяет следующие базовые понятия и их обозначения:
сущность (объект); ранее - информационный объект
атрибут сущности (свойство, характеризующее объект);
ранее – характеристика информационного объекта
ключевой атрибут (атрибут, входящий в первичный ключ);
ранее – идентификатор информационного объекта
связь; ранее отсутствовала
Первичный ключ - атрибут или группа атрибутов, однозначно идентифицирующих объект. Первичный ключ может состоять из нескольких атрибутов, тогда в нотации ER-модели подчеркивается каждый из них.
Объект и его атрибуты соединяются ненаправленными дугами:
Связи между объектами могут быть 3-х типов:
Ромб связи и прямоугольник объекта соединяются ненаправленными дугами в сторону "ко многим" и направленными в сторону "к одному":
Если связь соединяет две сущности, она называется бинарной. Связь может соединять более двух сущностей, например, связь, соединяющая три сущности, называется тернарной:
Пусть, например, требуется разработать концептуальную модель данных, описывающую организационную структуру кафедр вуза. Тогда кафедры являются предметной областью для задачи. Данная предметная область характеризуется следующими сущностями и их атрибутами:
сотрудник – ФИО, ученая степень, научное звание, контактные данные;
кафедра – название, шифр в вузе;
должность – название, образование.
Сформируем ER-диаграммы, описывающие сущности и связи между ними:
Определим, какие атрибуты могут играть роль ключевых:
На этапе логического проектирования требования к данным преобразуются в структуры, применяемые в используемой системе управления данными.
Физическое проектирование решает вопросы, связанные с производительностью системы; определяются способы размещения данных в файлах (т.е. на машинных носителях) и методы доступа к данным. Этот уровень проектирования связан также с типами записывающих устройств, методами доступа, длинами блоков и т.д., т.е. с теми физическими характеристиками машинных носителей, которые являются предметом изучения и освоения специалистов технических профессий.
В настоящее время все действия по физическому проектированию выполняются системами управления базами данных (СУБД), а потому не актуальны для учебного курса. Тем не менее, логическое проектирование, связанное с разработкой моделей данных, а также вопросы физического проектирования, связанные со структурами хранения данных, входят в программу дисциплины «Информационные системы» и являются предметом подробного рассмотрения далее.
Концептуальная модель данных позволяет перейти к формированию логических моделей. Существует три вида логических моделей данных: реляционные, иерархические (или древовидные), сетевые (или сети).
Реляционная модель – это совокупность элементов данных, описывающих информационные объекты одного класса, а потому имеющие одинаковый состав характеристик. Например, следующая таблица описывает результаты сдачи сессии студентами:
|
фамилия, имя, отчество |
оценки в сессию |
|
Иванов Иван Иванович |
Информатика – 5, КСЕ – 4, Программирование – 5 |
|
Федоров Федор Федорович |
Информатика – 3, КСЕ – 3, Программирование – 4 |
|
Петров Петр Петрович |
Информатика – 5, КСЕ – 4, Программирование – 5 |
Элемент данных, играющий роль идентификатора объекта, называется ключевым полем, или попросту ключом. Ключ, выполняющий однозначную идентификацию, называется первичным. Ключ, выполняющий многозначную идентификацию, называется вторичным. Если в качестве ключа выступает один элемент данных, такой ключ называется простым. Если используются несколько элементов данных в качестве ключа, такой ключ называется составным.
Для построенной ранее концептуальной модели можно сформировать три реляционные структуры, поскольку выделены три сущности, причем для таблицы, соответствующей сущности сотрудник, требуется составной первичный ключ, включающий атрибуты ФИО, название кафедры (первичные ключи выделены полужирно):
сотрудник кафедра должность
|
ФИО |
ученая степень |
научное звание |
контактные данные |
название кафедры |
название должности |
название |
шифр в вузе |
название |
образование |
||
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
Все остальные поля могут рассматриваться как вторичные ключи, если пользователь заинтересован в организации последующего доступа к данным по этим полям.
Иерархическая модель (или дерево) – это конечное множество Т элементов, такое, что выполняются следующие условия:
Пример дерева показан на рисунке:
Дадим некоторые определения, которые понадобятся нам в дальнейшем:
Построим иерархическую модель для концептуальной модели из рассмотренного ранее примера. Для этого воспользуется видом связи «один-ко-многим», которая показана на ER-диаграмме. Чтобы продемонстрировать эту связь на схеме, сущность, выступающую в роли «ко-многим», изобразим в виде повторяющихся прямоугольников:
Видно, что имеют место два дерева, одно из которых моделирует отношения сотрудников с кафедрами, а второе – сотрудников и занимаемые ими должности.
С учетом атрибутов сущностей данная схема выглядит следующим образом (первичные ключи выделены подчеркиванием):
Сетевая модель (сеть) – это два множества Т и R, между которыми задано отображение Г: Т R, где Т – множество элементов сети, R – множество бинарных отношений между ними, Г – отображение, показывающее, какие элементы какими отношениями связаны. Нестрого сетевые модели можно определить как несколько иерархических моделей, соединенных вершинами максимального уровня иерархии.
Построим сетевую модель для нашего примера. Уже иллюстрации к дереву показывают, что модель информационно избыточна – в обоих деревьях находится описание одних и тех же сотрудников. Этот недостаток устраняется в сетевых моделях:
В данном разделе рассмотрим способы организации хранения на машинных носителях информационных массивов, отражающих одну из рассмотренных логических моделей данных. Каждый раз при решении вопроса о выборе способа структуризации файла, основным критерием является последующая минимизация времени доступа к данным по запросам пользователя, который включает, в общем случае, наименование и значение ключевого поля. Для этого часто вводятся дополнительные массивы данных, что ведет к перерасходу объемов внешней памяти, но позволяет оптимизировать доступ к данным.
Поскольку для реляционных структур существуют вторичные и первичные ключи, которые используются при поиске данных, различают методы физического проектирования для доступа по первичному и вторичному ключу. При рассмотрении каждой физической модели одновременно будет обсуждаться вопрос доступа к данным, что является основным критерием при решении вопроса о структурах хранения.
Для доступа по первичному ключу различают модели: последовательная организация, индексно-последовательная организация, индексно-произвольная организация, рандомизация. Для доступа по вторичному ключу выделяют модели: цепь подобных записей и инвертированные файлы.
3.4.1.1. Последовательная организация
Записи файла соответствуют логической модели данных. Число реляционных структур (таблиц) соответствует числу файлов. Доступ к записям осуществляется тремя способами: последовательным сканированием, блочным, двоичным.
При последовательном сканировании записи файла могут быть неупорядочены по первичному ключу. Для обозначения значения ключевого поля в запросе введем нотацию Кдоступ. Последовательно, начиная с первой записи, сравнивается ключ каждой записи файла К с ключом доступа Кдоступ. При равенстве обоих ключей требуемая запись найдена: содержащаяся в ней информация полностью или частично выводится пользователю. Если же равенство не выполняется, последующие шаги алгоритма различаются для упорядоченного и неупорядоченного файла:
При блочном способе записи файла должны быть упорядочены по первичному ключу. Для удобства дальнейшего изложения предположим (здесь и далее по реляционным моделям), что упорядочение выполнено по возрастанию значения ключа.
Файл разделяется на виртуальные блоки размером N записей, где N – число записей в файле. С ключом доступа Кдоступ сравниваются ключевые поля последних записей в блоках - Кjблока, начиная с первого блока (j – номер блока). С помощью такого сравнения вначале определяется блок, в котором возможно нахождение нужной записи (для этого требуется выполнение условия Кдоступ < Кjблока)5, а затем уже, как правило, методом последовательного сканирования - сама запись в блоке.
При двоичном способе записи файла также должны быть упорядочены по первичному ключу. Файл последовательно делится на две части, уменьшая пространство поиска каждый раз вдвое. Ключ доступа Кдоступ сравнивается с ключевым полем «средней» записи - Кср. Здесь возможны варианты:
Кдоступ=Кср; «средняя» запись является искомой, алгоритм заканчивает работу;
Кдоступ>Кср; поиск продолжается в той половине файла, где первичные ключи имеют бóльшие значения;
Кдоступ<Кср; поиск продолжается в той половине файла, где первичные ключи имеют мéньшие значения.
Продолжение поиска заключается вновь в делении выбранной половины файла пополам и т.д. Алгоритм заканчивает работу при нахождении нужной записи или при условии, когда очередная «половина» файла содержит только одну запись, ключевое поле которой не совпадает с Кдоступ. Делается вывод об отсутствии нужной записи в файле.
3.4.1.2. Индексно-последовательная организация
Записи файла должны быть упорядочены по первичному ключу. Аналогично блочному методу доступа, файл делится на виртуальные блоки размером N. Затем ключевые поля последних записей блоков вместе с порядковыми номерами этих записей в файле включаются в дополнительные файлы, которые называются индексами. Видно, что данный способ использует дополнительные построения, - назовем тогда исходный файл основным.
Пусть основной файл соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид (здесь и далее графа № п/п не входит в состав записей файла, а формируется операционной системой при создании файла):
кафедра
|
№ п/п |
название |
шифр в вузе |
|
1 |
АПП |
238 |
|
2 |
СУиВТ |
239 |
|
3 |
ТАМ |
145 |
|
4 |
Экономики |
056 |
Для этого файла N = 4. Это значит, что индекс будет иметь вид (графа ссылки формируется как номера соответствующих записей основного файла):
|
название |
ссылки |
|
СУиВТ |
2 |
|
Экономики |
4 |
Доступ к записям вновь осуществляется по ключу Кдоступ, который указывается пользователем в запросе. Однако алгоритм поиска начнет его не с основного файла, а с индекса, интерпретируя его как обычный файл с последовательной организацией записей, и применит к нему один из описанных ранее методов доступа, например, последовательное сканирование. Тогда ключевое поле К каждой записи индекса будет сравниваться с ключом Кдоступ. Возможны варианты:
3.4.1.3. Индексно-произвольная организация
Этот способ организации данных используется, когда надо обеспечить доступ по нескольким первичным ключам. Поскольку, в общем случае, невозможно упорядочить линейный список сразу по нескольким ключам, требуется применять особые методы оптимизации поиска.
В таком случае список упорядочивается по тому ключу, по которому предполагаются наиболее частые запросы. По этому ключу организуется индекс как в случае индексно-последовательной организации (см. предыдущий раздел). Остальные значения первичных ключей формируют дополнительный файл – также индекс. Они включаются в индекс в полном составе из исходного файла и упорядочиваются. Кроме того, в индекс записываются ссылки на эти элементы в основном файле в виде порядковых номеров записей.
Пусть основной файл вновь соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид:
кафедра
|
№ п/п |
название |
шифр в вузе |
|
1 |
АПП |
238 |
|
2 |
СУиВТ |
239 |
|
3 |
ТАМ |
145 |
|
4 |
Экономики |
056 |
В данной модели, как отмечалось ранее, два первичных ключа – название и шифр в вузе. Пусть предполагается искать данные по обоим ключам, причем, в основном поиск будет вестись по ключу название. Тогда по этому ключу упорядочиваются записи в файле (что и сделано в таблице). Видно, что второй ключ имеет неупорядоченные значения.
Формируются два индекса: первый – для ключа название – аналогичен предыдущему примеру:
|
название |
ссылки |
|
СУиВТ |
2 |
|
Экономики |
4 |
Второй индекс имеет вид:
|
шифр в вузе |
ссылки |
|
056 |
4 |
|
145 |
3 |
|
238 |
1 |
|
239 |
2 |
Видно из второй таблицы, что значения ключа шифр в вузе упорядочены по возрастанию. Это позволяет данный индекс рассматривать как упорядоченный последовательный файл и применять к нему рассмотренные методы доступа в разделе «Последовательная организация».
3.4.1.4. Рандомизация
Этот метод доступа имеет несколько названий: перемешивание, рандомизация, хэширование. Общая схема представлена на рисунке.
Область размещения записей файла
Область размещения записей файла делится на участки – бакеты. При добавлении записей файла в соответствии со значениями первичных ключей Кi алгоритм рандомизации определяет не адрес отдельной записи (как это было в предыдущих случаях), а номер (адрес) бакета. Сама запись размещается в бакете в первом свободном месте – после уже имеющихся в нем записей. Таким образом, записи внутри бакета не упорядочены.
При поиске записи алгоритм рандомизации по первичному ключу определяет вначале номер бакета, в котором должна находиться запись. Затем уже в найденном бакете способом последовательного сканирования делается попытка найти нужную запись.
Алгоритм рандомизации состоит из следующих шагов:
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ ь ъ ы э ю я
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
Тогда, например, ключ Сидоров запишется как 8945752 (различие прописных и строчных букв игнорируется). Очевидно, такая замена может привести к тому, что разные нечисловые значения будут иметь одинаковые числовые замены. Это одна из причин потери информации при выполнении алгоритмов рандомизации;
8945752 80026478845504 4788;
средняя часть числа,
состоящая из 4 цифр
8945752 894 (13)(16)92 4792;
5752
старшие младшие совмещенные результат окончательный
разряды разряды разряды сложения результат совмещенных разрядов
8945752 9457 (17)47(12) 8473.
8 25
средняя результат окончательный
часть наложенные сложения результат
части числа
Очевидно, рассмотренные методы могут дать одинаковые результаты для разных числовых значений ключа. Это вторая причина потери информации при рандомизации. Выбор того или иного метода из трех рассмотренных выполняется экспериментально: лучшим считается тот метод, при использовании которого бакеты заполняются записями относительно равномерно;
С=7000/9999=0,7.
Рассчитаем реальный номер бакета для результата предыдущего шага, полученного методом складывания: 8473*0,7=5931.
3.4.1.5. Цепь подобных записей
К исходному файлу не предъявляется никаких требований. К нему достраиваются дополнительные файлы – индексы - в количестве, соответствующем числу вторичных ключей. Записи таких файлов имеют два поля: первое – значение вторичного ключа из основного файла, второе – ссылка на первую запись в основном файле с таким же значением вторичного ключа (в качестве ссылки используется порядковый номер записи в файле). Сами записи файла также модифицируются: они дополняются полями в количестве, соответствующем числу вторичных ключей. Каждое поле служит для организации цепочек записей с одним и тем же значением вторичного ключа.
Пусть основной файл имеет вид:
сотрудник
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
название (кафедры) |
название (должности) |
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
СУиВТ |
доцент |
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
ТАМ |
доцент |
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
СУиВТ |
ассистент |
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
ТАМ |
профессор |
Вторичными ключами являются ученая степень, научное звание, название (кафедры), название (должности). Построим индексы для этих ключей:
|
ученая степень |
ссылки |
научное звание |
ссылки |
название (кафедры) |
ссылки |
название (должности) |
ссылки |
|||
|
д.т.н. |
4 |
доцент |
1 |
СУиВТ |
1 |
ассистент |
3 |
|||
|
к.т.н. |
1 |
нет |
2 |
ТАМ |
2 |
доцент |
1 |
|||
|
нет |
3 |
профессор |
4 |
профессор |
4 |
Как видно из таблиц, каждый индекс содержит поле со всеми значениями соответствующего вторичного ключа из основного файла и поле (озаглавлено ссылки), в котором указывается номер записи основного файла, где впервые встречается соответствующее значение вторичного ключа. Значения вторичных ключей в индексах упорядочены по возрастанию, так что с индексами можно работать как с упорядоченными файлами (в роли первичных ключей таких файлов выступают вторичные ключи основных файлов).
Модифицируем также и основной файл. Для удобства поместим дополнительные поля (они выделены заливкой) справа от соответствующего вторичного ключа. Получим таблицу:
сотрудник
|
№ п/п |
ФИО |
ученая степень |
№ п/п |
научное звание |
№ п/п |
контактные данные |
название (кафедры) |
№ п/п |
название (должности) |
№ п/п |
|
1 |
Иванов И.И. |
к.т.н. |
2 |
доцент |
- |
234567 |
СУиВТ |
3 |
доцент |
2 |
|
2 |
Петров П.П. |
к.т.н. |
- |
нет |
3 |
456789 |
ТАМ |
4 |
доцент |
- |
|
3 |
Сидоров С.С. |
нет |
- |
нет |
- |
123456 |
СУиВТ |
- |
ассистент |
- |
|
4 |
Яковлев Я.Я. |
д.т.н. |
- |
профессор |
- |
345678 |
ТАМ |
- |
профессор |
- |
Рассмотрим, как выполняется задача поиска нужной записи.
Пусть надо найти фамилии и инициалы всех сотрудников, работающих в должности ассистента. Очевидно, Кдоступ=<название (должности)=ассистент>. Поиск осуществляется последовательным выполнением шагов:
Если доступ планируется одновременно по нескольким вторичным ключам, можно оптимизировать эту процедуру. Оптимизация состоит в том, что каждый индекс дополняется полем, в котором указывается число записей в цепочке, и тогда вначале обращение осуществляется к тому индексу, в котором длина цепочки минимальна.
Например, основной список представлен таблицей:
сотрудник
|
№ п/п |
ФИО |
ученая степень |
№ п/п |
научное звание |
№ п/п |
контактные данные |
название (кафедры) |
№ п/п |
название (должности) |
№ п/п |
|
1 |
Иванов И.И. |
к.т.н. |
2 |
доцент |
- |
234567 |
СУиВТ |
3 |
доцент |
2 |
|
2 |
Петров П.П. |
к.т.н. |
- |
нет |
3 |
456789 |
ТАМ |
4 |
доцент |
- |
|
3 |
Сидоров С.С. |
нет |
- |
нет |
- |
123456 |
СУиВТ |
- |
ассистент |
- |
|
4 |
Яковлев Я.Я. |
д.т.н. |
- |
профессор |
- |
345678 |
ТАМ |
- |
профессор |
- |
Индексы модифицированы и показаны в таблицах (дополнительные поля показаны заливкой):
|
ученая степень |
ссылки |
длина цепочки |
научное звание |
ссылки |
длина цепочки |
название (кафедры) |
ссылки |
длина цепочки |
название (должности) |
ссылки |
длина цепочки |
|||
|
д.т.н. |
4 |
1 |
доцент |
1 |
1 |
СУиВТ |
1 |
2 |
ассистент |
3 |
1 |
|||
|
к.т.н. |
1 |
2 |
нет |
2 |
2 |
ТАМ |
2 |
2 |
доцент |
1 |
2 |
|||
|
нет |
3 |
1 |
профессор |
4 |
1 |
профессор |
4 |
1 |
Значения полей длина цепочки – это количество записей основного файла с соответствующим значением вторичного ключа.
Пусть надо определить, какие сотрудники работают в должности доцентов и не имеют ученой степени. Очевидно, Кдоступ=<название (должности)=доцент, ученая степень=нет). Задача решается следующим образом:
3.4.1.6. Инвертированные файлы
Основной файл не изменяется. Строятся индексы в нужном количестве. В индекс включаются все значения соответствующего вторичного ключа, а также все ссылки на записи основного файла с данным значением вторичного ключа.
Пусть основной файл показан в таблице:
сотрудник
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
название (кафедры) |
название (должности) |
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
СУиВТ |
доцент |
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
ТАМ |
доцент |
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
СУиВТ |
ассистент |
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
ТАМ |
профессор |
Соответствующие индексы показаны в таблицах:
|
ученая степень |
ссылки |
научное звание |
ссылки |
название (кафедры) |
ссылки |
название (должности) |
ссылки |
|||
|
д.т.н. |
4 |
доцент |
1 |
СУиВТ |
1, 3 |
ассистент |
3 |
|||
|
к.т.н. |
1, 2 |
нет |
2, 3 |
ТАМ |
2, 4 |
доцент |
1, 2 |
|||
|
нет |
3 |
профессор |
4 |
профессор |
4 |
Расположение всех ссылок для некоторого вторичного ключа в одном поле позволяет исключить перебор записей в цепочке записей при их поиске.
Рассмотрим, как выполняется задача поиска нужной записи.
Пусть надо определить список всех сотрудников, работающих в должности доцента, Кдоступ=<название (должности)=доцент>. Поиск осуществляется последовательным выполнением шагов:
Традиционными способами организации хранения иерархических моделей являются: множественные ссылки на порожденные записи, ссылки на порожденные и подобные записи; кольцевые структуры; справочники, битовые отображения.
3.4.2.1. Множественные ссылки на порожденные записи
Для хранения подобных записей в иерархических структурах используются реляционные структуры. Записи файлов могут иметь одно или несколько полей, среди которых можно выделять первичные и вторичные ключи. Для указания связей, которые образуют иерархические структуры, применяют систему ссылок. В случае, когда это ссылки на порожденные записи, каждая из них ссылается на некоторую порожденную запись. Количество таких ссылок соответствует числу порожденных записей. Поскольку у записей, соответствующих элементам максимального уровня иерархии дерева, нет порожденных записей, у них отсутствуют какие-либо ссылки.
Рассмотрим данную организацию хранения элементов для дерева, описывающего состав кафедр некоторого факультета:
Этому абстрактному дереву соответствует следующая структура, показывающая конкретный состав кафедр вуза (верхний уровень описывает кафедры, нижний - сотрудников):
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Поскольку в этом дереве есть два множества подобных элементов (кафедры и сотрудники), сформируем для них таблицы:
сотрудник кафедра
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
№ п/п |
название |
шифр в вузе |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
1 |
СУиВТ |
239 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
2 |
ТАМ |
145 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Теперь надо показать связи между элементами, указанные в дереве. Для этого, в соответствии с рассматриваемым способом, сформируем у таблицы, описывающей кафедры, дополнительное поле ссылки, в котором и зафиксируем требуемые связи. Получим таблицу:
|
название |
шифр в вузе |
ссылки |
|
СУиВТ |
239 |
1, 3 |
|
ТАМ |
145 |
2, 4 |
В таком дереве «хорошо» решаются задачи поиска записей в направлении от корня к терминальным вершинам.
Пусть надо сформировать список сотрудников кафедры СУиВТ (эта задача подобна задаче поиска по вторичному ключу для линейных списков), т.е. Кдоступ = <название (кафедры) = СУиВТ>. Задача решается следующим образом:
3.4.2.2. Ссылки на подобные и порожденные записи
Аналогично предыдущему методу подобные записи описываются в реляционных структурах. Для указания связей применяют два вида ссылок: одна фиксирует связь с первой порожденной записью, вторая – с подобной. Причем с помощью подобия показывается, каким родительским записям принадлежат порожденные. Для записей, соответствующих максимальному уровню иерархии, поддерживается только одна ссылка (на подобные записи), поскольку они не имеют порожденных записей; для записей первого уровня иерархии также поддерживается одна ссылка (на порожденные записи), поскольку все они имеют одного родителя – корень. Для остальных записей поддерживается две ссылки.
Рассмотрим данную организацию хранения элементов для дерева:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Для уровня кафедр устанавливаются только ссылки на порожденные записи. Для уровня сотрудников поддерживается ссылка на подобные элементы, с помощью которой показывается «цепочка» сотрудников, работающих на одной кафедре:
сотрудник кафедра
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
ссылки |
№ п/п |
название |
шифр в вузе |
ссылки |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
3 |
1 |
СУиВТ |
239 |
1 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
4 |
2 |
ТАМ |
145 |
2 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
- |
|||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
- |
Преимущество этого метода организации хранения иерархических моделей состоит в однотипности списков ссылок: они всегда содержат по одной ссылке (пустой, если цепочка закончена или нет порожденных записей).
Пусть надо сформировать список сотрудников кафедры СУиВТ, т.е. Кдоступ = <название (кафедры) = СУиВТ>. Задача решается следующим образом:
3.4.2.3. Кольцевые структуры
В отличие от предыдущих методов позволяют от порожденных записей переходить к родительским. Для этого в структуре записей поддерживаются специальные ссылки на «родителей».
Представим данным методом дерево:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Его описание сведем в таблицы:
сотрудник кафедра
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
ссылки на подобные элементы |
ссылки на родительские элементы |
№ п/п |
название |
шифр в вузе |
ссылки на порожденные элементы |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
3 |
1 |
1 |
СУиВТ |
239 |
1 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
4 |
2 |
2 |
ТАМ |
145 |
2 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
1 |
1 |
|||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
4 |
2 |
Как видно, в таблице сотрудников отсутствуют пустые ссылки. Это означает, что конечные записи в цепочках подобных записей ссылаются на первые записи в этих цепочках. Так получаются «горизонтальные» кольца. Наличие таких колец позволяет решать задачи, требующие многократного просмотра записей от начала к концу. Подобная задача, например, имеет место при сортировке файла некоторыми методами. Например, когда требуется отсортировать список сотрудников кафедры СУиВТ по возрастанию значений ключа, а кафедры ТАМ – по убыванию. В то же время совокупность ссылок на порожденные и родительские записи формирует «вертикальные» кольца. Они позволяют переходить от порожденных записей к родительским, чего не было в предыдущих методах.
Задачи поиска требуемых данных в направлении просмотра дерева «сверху вниз» решаются аналогично предыдущим методам и здесь не рассматриваются.
Рассмотрим, как решается противоположная задача просмотра дерева в направлении «снизу вверх», например, когда надо определить, на какой кафедре работает некоторый сотрудник.
Пусть надо определить, на какой кафедре работает сотрудник по фамилии и инициалам Сидоров С.С., т.е. Кдоступ=<ФИО=Сидоров С.С.>. Задача решается следующим образом:
3.4.2.4. Справочники
Связи между записями дерева формируют отдельное описание в виде файла-справочника. Сами элементы дерева описываются в отдельных таблицах.
Пусть исходное дерево имеет вид:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Описание сотрудников и кафедр располагается в таблицах:
сотрудник кафедра
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
№ п/п |
название |
шифр в вузе |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
1 |
СУиВТ |
239 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
2 |
ТАМ |
145 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Сформируем для дерева справочник - это файл, в котором в качестве полей, идентифицирующих записи основных файлов, выступают соответствующие первичные ключи (поле элемент дерева):
|
№ п/п |
элемент дерева |
ссылки на родительскую запись6 |
ссылки на порожденную запись7 |
|
1 |
СУиВТ |
- |
3, 5 |
|
2 |
ТАМ |
- |
4, 6 |
|
3 |
Иванов И.И. |
1 |
- |
|
4 |
Петров П.П. |
2 |
- |
|
5 |
Сидоров С.С. |
1 |
- |
|
6 |
Яковлев Я.Я. |
2 |
- |
Пусть надо определить, каков шифр кафедры, на которой работает сотрудник по фамилии и инициалам Сидоров С.С., т.е. Кдоступ=<ФИО=Сидоров С.С.>. Задача решается следующим образом:
Пусть надо определить контактные данные сотрудников кафедры СУиВТ, т.е. Кдоступ = <название (кафедры)=СУиВТ>. Задача решается следующим образом:
3.4.2.5. Битовые отображения
Структура дерева представляется бинарной матрицей. Вначале формируются обозначения строк и столбцов матрицы следующим образом:
Затем в ячейках матрицы на пересечении обозначений столбцов и строк проставляются единицы, если между ними есть связи в дереве, и нули в противном случае.
Пусть дерево имеет вид:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Описание сотрудников и кафедр располагается в таблицах:
сотрудник кафедра
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
№ п/п |
название |
шифр в вузе |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
1 |
СУиВТ |
239 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
2 |
ТАМ |
145 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Связи между вершинами дерева фиксируются в битовой матрице:
|
Обозначения строк |
Обозначения столбцов |
|
|
СУиВТ |
ТАМ |
|
|
Иванов И.И. |
1 |
0 |
|
Петров П.П. |
0 |
1 |
|
Сидоров С.С. |
1 |
0 |
|
Яковлев Я.Я. |
0 |
1 |
Данная матрица является логической моделью связей между элементами дерева, которой соответствует следующая физическая модель в виде файла:
|
№ п/п |
ФИО |
название |
|
1 |
Иванов И.И. |
СУиВТ |
|
2 |
Петров П.П. |
ТАМ |
|
3 |
Сидоров С.С. |
СУиВТ |
|
4 |
Яковлев Я.Я. |
ТАМ |
Пусть надо определить, каков шифр кафедры, на которой работает сотрудник по фамилии и инициалам Сидоров С.С., т.е. Кдоступ=<ФИО=Сидоров С.С.>. Задача решается следующим образом:
Пусть надо определить контактные данные сотрудников кафедры СУиВТ, т.е. Кдоступ=<название (кафедры)=СУиВТ>. Задача решается следующим образом:
Для организации хранения сетей и доступа к их элементам используют методы: множественные ссылки на порожденные записи; ссылки на порожденные и подобные записи; кольцевые структуры; справочники; битовые отображения. Следует отметить, что рассматриваемые далее способы аналогичны тем, которые приводились ранее для деревьев.
3.4.3.1. Множественные ссылки на порожденные записи
Пусть исходная сеть имеет вид:
Этой абстрактной сети соответствует конкретизированная данными структура:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
|
ассистент |
высшее |
доцент |
высшее |
профессор |
высшее |
Здесь два дерева: кафедра – сотрудник и должность – сотрудник. Они «сцеплены» своими терминальными вершинами – сотрудниками, которые являются вершинами максимального уровня иерархии для обоих деревьев.
Описание этой сети задано в таблицах (формируются по аналогии с деревьями):
сотрудник
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
|
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
|
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
|
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
кафедра должность
|
№ п/п |
название |
шифр в вузе |
ссылки |
№ п/п |
название |
образование |
ссылки |
|
|
1 |
СУиВТ |
239 |
1, 3 |
1 |
ассистент |
высшее |
3 |
|
|
2 |
ТАМ |
145 |
2, 4 |
2 |
доцент |
высшее |
1, 2 |
|
|
3 |
профессор |
высшее |
4 |
Выполнение поисковых задач осуществляется аналогично иерархическим структурам. Однако некоторые задачи могут быть оптимизированы.
Пусть, например, надо определить сотрудников, работающих в должности доцента на кафедре СУиВТ, т.е. Кдоступ=<название (кафедры)=СУиВТ&должность=доцент>. Задача решается следующим образом:
3.4.3.2. Ссылки на подобные и порожденные записи
Пусть сеть имеет вид:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
|
ассистент |
высшее |
доцент |
высшее |
профессор |
высшее |
Тогда ее описание задано в таблицах (формируются по аналогии с деревьями):
сотрудник
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
ссылки для цепи кафедр |
ссылки для цепи должностей |
|||||||
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
3 |
2 |
|||||||
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
4 |
- |
|||||||
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
- |
- |
|||||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
- |
- |
кафедра должность
|
№ п/п |
название |
шифр в вузе |
ссылки |
№ п/п |
название |
образование |
ссылки |
|
|
1 |
СУиВТ |
239 |
1 |
1 |
ассистент |
высшее |
3 |
|
|
2 |
ТАМ |
145 |
2 |
2 |
доцент |
высшее |
1 |
|
|
3 |
профессор |
высшее |
4 |
|||||
Выполнение поисковых задач осуществляется аналогично иерархическим структурам.
3.4.3.3. Кольцевые структуры
Пусть сеть имеет вид:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
|
ассистент |
высшее |
доцент |
высшее |
профессор |
высшее |
Описание элементов сети задано в таблицах (формируются по аналогии с деревьями):
сотрудник
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
ссылки для цепи кафедр |
ссылки для цепи должностей |
||
|
на подобные элементы |
на родительские элементы |
на подобные элементы |
на родительские элементы |
|||||
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
3 |
1 |
2 |
2 |
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
4 |
2 |
1 |
2 |
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
1 |
1 |
3 |
1 |
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
2 |
2 |
4 |
4 |
кафедра должность
|
№ п/п |
название |
шифр в вузе |
ссылки |
№ п/п |
название |
образование |
ссылки |
|
|
1 |
СУиВТ |
239 |
1 |
1 |
ассистент |
высшее |
3 |
|
|
2 |
ТАМ |
145 |
2 |
2 |
доцент |
высшее |
1 |
|
|
3 |
профессор |
высшее |
4 |
Выполнение поисковых задач осуществляется аналогично иерархическим структурам.
3.4.3.5. Справочники
Пусть сеть имеет вид:
|
СУиВТ |
239 |
ТАМ |
145 |
|||||
|
Иванов И.И. |
к.т.н. |
доцент |
234567 |
Петров П.П. |
к.т.н. |
нет |
456789 |
|
|
Сидоров С.С. |
нет |
нет |
123456 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
|
ассистент |
высшее |
доцент |
высшее |
профессор |
высшее |
Описание элементов сети задано в таблицах:
сотрудник кафедра должность
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
№ п/п |
название |
шифр в вузе |
№ п/п |
название |
образование |
||
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
1 |
СУиВТ |
239 |
1 |
ассистент |
высшее |
||
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
2 |
ТАМ |
145 |
2 |
доцент |
высшее |
||
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
3 |
профессор |
высшее |
|||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Описание связей между элементами сети задано таблицей - справочником (формируется аналогично иерархическим структурам с учетом того, что сеть из примера представлена двумя деревьями):
|
№ п/п |
элемент сети |
ссылки на родительскую запись |
ссылки на порожденную запись |
|
1 |
СУиВТ |
- |
6, 8 |
|
2 |
ТАМ |
- |
7, 9 |
|
3 |
ассистент |
- |
8 |
|
4 |
доцент |
- |
6, 7 |
|
5 |
профессор |
- |
9 |
|
6 |
Иванов И.И. |
1 |
- |
|
7 |
Петров П.П. |
2 |
- |
|
8 |
Сидоров С.С. |
1 |
- |
|
9 |
Яковлев Я.Я. |
2 |
- |
Выполнение поисковых задач осуществляется аналогично иерархическим структурам.
3.4.3.6. Битовые отображения
Пусть исходная сеть соответствует последнему примеру. Описание элементов сети задано в таблицах:
сотрудник кафедра должность
|
№ п/п |
ФИО |
ученая степень |
научное звание |
контактные данные |
№ п/п |
название |
шифр в вузе |
№ п/п |
название |
образование |
||
|
1 |
Иванов И.И. |
к.т.н. |
доцент |
234567 |
1 |
СУиВТ |
239 |
1 |
ассистент |
высшее |
||
|
2 |
Петров П.П. |
к.т.н. |
нет |
456789 |
2 |
ТАМ |
145 |
2 |
доцент |
высшее |
||
|
3 |
Сидоров С.С. |
нет |
нет |
123456 |
3 |
профессор |
высшее |
|||||
|
4 |
Яковлев Я.Я. |
д.т.н. |
профессор |
345678 |
Связи между элементами сети показаны в таблице – битовой матрице (формируется аналогично иерархическим структурам):
|
Обозначение строк |
Обозначение столбцов |
||||
|
СУиВТ |
ТАМ |
ассистент |
доцент |
профессор |
|
|
Иванов И.И. |
1 |
0 |
0 |
1 |
0 |
|
Петров П.П. |
0 |
1 |
0 |
1 |
0 |
|
Сидоров С.С. |
1 |
0 |
1 |
0 |
0 |
|
Яковлев Я.Я. |
0 |
1 |
0 |
0 |
1 |
Данная матрица является логической моделью связей между элементами сети, которой соответствует следующая физическая модель в виде файла:
|
№ п/п |
ФИО |
название (кафедры) |
название (должности) |
|
1 |
Иванов И.И. |
СУиВТ |
доцент |
|
2 |
Петров П.П. |
ТАМ |
доцент |
|
3 |
Сидоров С.С. |
СУиВТ |
ассистент |
|
4 |
Яковлев Я.Я. |
ТАМ |
профессор |
Выполнение поисковых задач осуществляется аналогично иерархическим структурам.
Как отмечалось ранее, информационные массивы таких систем содержат неструктурированные данные произвольного формата. Наиболее представительное множество документальных систем основано на текстовых данных, поэтому дальнейшее изложение относится именно к ним.
Минимальным информационным элементом в документальных ИС является файл. В ответ на запрос пользователя ИС отклик системы содержит не данные, описывающие отдельные факты, как в случае фактографических ИС, а целые файлы (или ссылки на них), релевантные запросу, т.е. отвечающие его смыслу. Выделение смысла текста (или запроса) – самостоятельная очень сложная проблема, которая касается такой области современной информатики как искусственный интеллект, а потому здесь не рассматривается. На практике определение релевантности текста и запроса выполняется, в простейшем случае, на основе совпадения терминов запроса и текста, что, конечно, сильно обедняет результат поиска, поскольку один смысл можно выразить по-разному. При этом в качестве таких терминов могут использоваться как отдельные слова, так и словосочетания. Применяемые для поиска релевантных текстов термины называются также ключевыми словами (или ключами)8.
При организации хранения неструктурированных данных решаются две основные задачи:
Различают следующие методы хранения неструктурированных данных, организованных в виде файлов:
Совокупность файлов, содержащих текстовые данные, составляет полнотекстовую базу данных – ТБД, т.е. информационные массивы ИС.
Файлы хранятся в произвольном порядке, например, в порядке их поступления. Не определены ни группы, ни классы файлов, нет справочников или других списков, обеспечивающих доступ к любому файлу.
Для нахождения всех файлов, обладающих некоторой характеристикой, требуется просмотр всего массива файлов. Неэффективность данного метода объясняет его практическое неиспользование.
Пусть, например, имеются тексты, которые хранятся в файлах с именами, соответственно, Ф1, Ф2, Ф3, Ф4, содержащие некоторые ключи Кi (на рисунке схематично показаны текстовые файлы, где в тексте среди слов содержатся ключевые слова):
Рассмотрим решение задачи поиска релевантного текста.
Пусть запрос содержит ключевое слово К1, например, компьютер. Тогда алгоритм поиска имеет вид:
Подобный метод организации хранения файлов и последующий поиск требуемых данных осуществляется в операционных системах семейства Windows и характеризуется большими временными затратами.
Файлы разделены на множества так, что все элементы одного множества отождествлены с помощью ключевого слова. По аналогии со структурированными данными можно говорить о подобии текстов, отождествленных с помощью одного ключа. Внутри каждого множества файлы соединены ссылками, а для доступа к первому элементу в цепочке организуются справочники - индексы. В роли ссылок могут выступать, в частности, полные имена файлов.
Пусть ТБД содержит те же файлы, что и в предыдущем примере. Индекс – это структурированный файл вида:
|
Ключевое слово |
Ссылка |
|
К1 |
Ф1 |
|
К2 |
Ф2 |
|
К3 |
Ф1 |
|
К4 |
Ф4 |
Кроме того, претерпевают изменения и сами файлы Ф1 – Ф4: они содержат описания цепочек подобных файлов, размещенные, например, в конце самих текстов (показаны заливкой):
Из рисунка видно, что структура этих описаний соответствует структуре самого индекса: первое поле – это ключевое слово, а второе – ссылка на файл, следующий в цепочке подобных текстов.
Рассмотрим, как решается задача поиска релевантного текста при такой организации.
Пусть запрос по-прежнему содержит ключевое слово К1. Тогда алгоритм просмотра имеет вид:
Этот способ организации текстовых файлов является развитием предыдущего: в справочник включаются все адресные ссылки, соответствующие тому или иному ключевому слову. Одновременно адресные ссылки исключаются из самих текстовых файлов. Тогда ТБД из предыдущего раздела при данной организации хранения будет иметь в составе следующие составляющие:
|
Ключевое слово |
Ссылки |
|
К1 |
Ф2, Ф3 |
|
К2 |
Ф2 |
|
К3 |
Ф1, Ф2 |
|
К4 |
Ф4 |
Как видно, поле Ссылки индекса содержит список ссылок на все файлы, содержащие то или иное ключевое слово.
Рассмотрим решение задачи поиска релевантного текста.
Пусть запрос содержит ключевое слово К1. Тогда алгоритм просмотра имеет вид:
Рассмотренный метод позволяет легко решать задачи поиска по сложным запросам.
Пусть запрос содержит ключевые слова К1, К3, связанные оператором «или», т.е. пользователю требуется найти тексты, содержащие либо слово К1, либо слово К3. Используя предыдущий алгоритм, находим файлы, релевантные запросу:
для К1 – {Ф1, Ф3};
для К3 – {Ф1, Ф2}.
Тогда множество файлов, удовлетворяющих запросу в целом, соответствует объединению полученных множеств:
К1К3 {Ф1, Ф3}{Ф1, Ф2} = {Ф1, Ф2, Ф3}.
Пусть запрос содержит ключевые слова К1, К3, связанные оператором «и», т.е. пользователю требуется найти тексты, содержащие одновременно слова К1 и К3. Используя известный алгоритм, находим файлы, релевантные запросу:
для К1 – {Ф1, Ф3};
для К3 – {Ф1, Ф2}.
Тогда множество файлов, удовлетворяющих запросу в целом, соответствует пересечению полученных множеств:
К1К3 {Ф1, Ф3}{Ф1, Ф2} = {Ф1}.
Тексты делятся на группы - кластеры родственных текстов, для чего исследуется подобие ключевых слов, характеризующих каждый текст. Тогда в один кластер включаются тексты, которые оказались подобны друг другу. Внутри кластера тексты могут быть организованы любым из рассмотренных ранее способов. Каждый кластер описывается множеством ключевых слов, которые входят в состав профиля кластера (формально определяется далее). В описание включается также адресная ссылка на соответствующий кластер. При хранении кластер может отождествляться с папкой (в терминологии операционной системы Windows’xx).
Пусть ТБД содержит файлы Ф1 – Ф4, которые входят в состав двух кластеров С1 и С2 следующим образом: С1 = {Ф2, Ф4}, С2 = {Ф1, Ф2, Ф3}. Профили П1 и П2 кластеров С1 и С2, соответственно, имеют в составе ключевые слова: П1 = {К2, К4}, П2 = {К1, К3}. Файлы внутри кластеров имеют последовательную организацию.
Тогда ТБД имеет в составе следующие компоненты:
|
Ключевое слово |
Ссылка |
|
К1 |
С2 |
|
К2 |
С1 |
|
К3 |
С2 |
|
К4 |
С1 |
Рассмотрим решение задачи поиска релевантного текста.
Пусть запрос содержит ключевое слово К1. Тогда алгоритм просмотра:
Следует отметить, что наиболее употребляемыми из рассмотренных методов являются инвертированные и кластерные файлы, поэтому дальнейшее изложение ориентировано на эти способы хранения текстовых файлов.
Как видно из описаний методов организации ТБД, в них активно используются ключевые слова. Задача выделения в том или ином тексте ключевых слов имеет самостоятельное значение и рассматривается в данном разделе.
Выделение ключевых слов в тексте называется его индексированием. Эта процедура сводится к последовательным действиям:
Таким образом, приведенные ранее примеры упрощали представление индексов, а также процедуры просмотра и добавления новых текстов в ТБД: на самом деле они включают и используют веса ключевых слов.
В результате описанных действий формируется список индексационных терминов (далее – терминов) – это ключевые слова, снабженные весами.
На значение веса термина влияют следующие факторы:
К сожалению, в литературе отсутствуют публикации аналитических зависимостей веса термина и его позиции в тексте. Решение данной задачи выполняется эвристическими методами на усмотрение разработчиков соответствующего программного обеспечения.
Используют частотные параметры терминов tk в тексте Di, которые характеризуют частоту встречаемости того или иного слова в том или ином тексте. Эти параметры называют частотами и обозначают fik, где i – обозначение текста, k – обозначение термина. Следует иметь в виду, что методы используют абсолютную частоту терминов, т.е. число их появлений. Данные методы включают частотные модели; модель, учитывающую различительную силу термина, и ее модификацию; модель, использующую динамическую оценку информативности.
4.2.2.1. Частотные модели
В применение частоты для оценки значимости термина вкладывают следующий смысл: чем чаще используется тот или иной термин, тем теснее он связан с семантикой текста. Этот тезис побуждает связать вес wik термина tk в тексте Di напрямую с частотой, т.е. wik = fik. Однако этого делать нельзя по двум причинам:
По этим соображениям формула для расчета веса термина приобретает вид:
wik = fik* К,
где К – коэффициент, который рассчитывается по разным зависимостям в соответствии с разновидностью частотных моделей.
Так, модель, использующую текстовую частоту термина, определяет К:
К = IDFk,
где IDFk (Inverse Document Frequency) – обратная частота tk в наборе из n текстов:
IDFk = ,
Dk – текстовая частота - число текстов набора из n, в которых есть tk.
Модель, учитывающая соотношение «сигнал-шум», рассчитывает К как:
,
где Nk – шум термина tk в наборе из n текстов:
,
- суммарная частота термина tk в наборе из n текстов,
Sk - сигнал термина tk в наборе из n текстов:
.
Модель, учитывающая распределение частоты термина, определяет К по формуле:
,
где - средняя частота термина tk в наборе из n текстов:
,
(Vk)2 - среднеквадратическое уклонение термина tk:
.
4.2.2.2. Модель, учитывающая различительную силу термина
В этой модели «хорошим», т.е. имеющим бóльший вес, считается термин, уменьшающий коэффициент подобия текстов. Вес термина здесь также прямо пропорционален его частоте, однако в расчете коэффициента К учитывается роль термина в усилении или уменьшении подобия текстов, что исключает данный метод из числа частотных.
Введем некоторые понятия:
где T = |{tk}| - число индексационных терминов.
Коэффициент подобия принимает значения от 0 до 1: при 0 тексты различны, при 1 – полностью идентичны (по смыслу).
В данной модели К = DVk
где - различительная сила (Difference Volume) термина tk:
,
- среднее значение коэффициента попарного подобия текстов данного набора в присутствии термина tk:
,
- то же в отсутствие термина tk.
Недостатком данной модели является то, что для вычисления средних попарных подобий текстов из набора n текстов требуется n2 операций. Модификация этого метода использует понятие пространства текстов и его характеристик - профиля и плотности пространства текстов.
Пространство текстов – множество текстов, каждый из которых характеризуется вектором. Профиль П пространства из n текстов – это виртуальный текст, вектор которого VП определяется как:
VП = {(tПk, fПk)},
где {tпk} = , т.е.множество {tпk} индексационных терминов есть объединение индексационных терминов текстов набора,
, т.е. частоты терминов есть усредненные частоты терминов по текстам набора.
Плотность Q пространства текстов:
,
где S(П,Di) – коэффициент подобия профиля и текста Di:
Чем больше Q, тем больше сходство между текстами набора.
С использованием плотности пространства Q можно по другому определить различительную силу DVk термина tk:
DVk = Qk – Q,
где Qk – плотность пространства текстов, когда термин tk исключен из всех текстов набора n,
Q - плотность пространства текстов в присутствии термина tk.
Вес wik термина tk в тексте Di определяется как:
wik = IVik,
где IVik – информативность (Information Value) термина tk в тексте Di, принимает значения от 0 до 2.
Информативность того или иного термина определяется экспериментально, а первоначально всем терминам приписываются одинаковые значения информативности, например, равные 1 (точка на рисунке).
Таким образом, начальными условиями для динамического назначения информативности для каждого tik являются: IVik = 1 и xik = 0. Тогда в случае полезности термина в процессе его использования его информативность увеличивается, а в случае бесполезности – уменьшается, причем указанные изменения имеют синусоидальный характер.
IV IV=1+sin(x)
2
1
0
-/2 0 /2 x
Увеличение (+) или уменьшение (-) информативности выполняется по формуле
,
где ,;
c – константа, имеющая смысл: число экспериментов для установления информативности термина.
Таким образом, в результате индексирования набора из n текстов (любым из рассмотренных методов) формируется справочник со структурой:
|
Термин tk |
Текст Di |
|||
|
Ф1 |
Ф2 |
... |
Фn |
|
|
t1 |
w11 |
w21 |
wn1 |
|
|
t2 |
w12 |
w22 |
wn2 |
|
|
... |
||||
|
tT |
w1T |
w2T |
wnT |
Такие справочники характерны для инвертированных файлов.
Для организации хранения кластерных файлов требуется их разбиение на кластеры.
Методы кластеризации основаны на построении полной матрицы подобия текстов заданного пространства, в которой для каждой пары текстов Di, Dj приводится коэффициент подобия S(Di,Dj). Затем вводится некоторое пороговое значение коэффициента подобия Ŝ: если S(Di,Dj)> Ŝ, тексты Di, Dj включаются в кластер, иначе – не включаются.
Как отмечалось, наиболее употребляемыми на практике являются два способа – инвертированные и кластерные файлы. Рассмотрим, как решается задача поиска релевантных текстов в этих случаях.
Пусть есть пространство текстов размером n, каждый из которых характеризуется вектором Vi = {(tk; wki)}. Пусть запрос содержит множество ключевых слов (терминов): q = ({tkq}). Определим формально текст, релевантный запросу q, как такой текст ТБД, для которого коэффициент подобия с запросом отличен от нуля.
Для расчета коэффициента подобия запроса и текстов ТБД применяются вектора текстов и запроса. Определим вектор запроса Vq:
Vq = {(tkq; wkq)},
где tkq – термин запроса;
wkq - вес этого термина.
Тексты Di характеризуются векторами Vi:
Vi = {(tk; wki)},
где tk – термин вектора текста – индексационный термин;
wki - вес этого термина:
Тогда при поиске релевантного текста (текстов) по запросу q рассчитываются коэффициенты подобия запроса и каждого из текстов ТБД:
После определения релевантных текстов возможны два подхода:
Пусть пространство текстов разбито на множество кластеров {Cl}, каждый из которых есть своё подпространство размером nl текстов исходного пространства размером n текстов. При этом каждый кластер характеризуется профилем Пl и вектором Vl вида:
Vl = {(tlk, flk)},
где {tlk} = , т.е. множество {tlk} индексационных терминов есть объединение индексационных терминов текстов кластера Сl,
, т.е. частоты терминов есть усредненные частоты терминов по текстам кластера.
Рассчитываются коэффициенты подобия S(q, Cl) запроса и кластера, представленного своим вектором:
где wlk – вес термина tk в профиле кластера Cl;
Тl – число индексационных терминов в профиле кластера Сl.
После определения релевантного кластера (его подобие с запросом отлично от нуля) поиск релевантного текста (текстов) выполняется внутри кластера.
Часто при поиске в ТБД необходимо увеличить число релевантных текстов (в поисковых системах Интернет это называется расширенным поиском). Пространство релевантности увеличивается за счет дополнительных совпадений терминов запроса и индексационных терминов.
Для увеличения числа совпадений используются методы:
Смысл этого метода сводится к тому, что с каждым термином tk связывается множество его синонимов Synk. Образуется тезаурус. Тогда вектор запроса пополняется терминами из тезауруса, что расширяет число текстов, релевантных запросу.
Связь термина tk с множеством Synk может быть представлена дополнительной графой справочника, в которой множество синонимов задано либо явно, либо списком номеров синонимичных терминов из того же справочника, например:
|
Термин tk |
Синонимы Synk |
Текст |
|||
|
Ф1 |
Ф2 |
Ф3 |
Ф4 |
||
|
К1 |
К4 |
wФ1К1 |
wФ2К1 |
wФ3К1 |
wФ4К1 |
|
К2 |
- |
wФ1К2 |
wФ2К2 |
wФ3К2 |
wФ4К2 |
|
К3 |
- |
wФ1К3 |
wФ2К3 |
wФ3К3 |
wФ4К3 |
|
К4 |
К1 |
wФ1К4 |
wФ2К4 |
wФ3К4 |
wФ4К4 |
Тогда, например, если в запросе участвует термин К1, а его синонимом является термин К4, то запросу релевантны тексты, характеризующиеся как термином К1, т.е. Ф1, так и К4, т.е. Ф4.
При формировании тезауруса применяются рассмотренные выше для текстов методы кластеризации. Для этого каждый термин tk представляется вектором Vk вида:
Vk = {(Di, fik)} или Vk = {(Di, wik)}.
Тогда для терминов tk и tr коэффициент подобия S(tk,tr) рассчитывается по формуле:
где pir – параметр (частота или вес), характеризующий термин tr в тексте Di,
n – число текстов в наборе.
Для каждого термина tk находятся дополнительные термины, которые ассоциируются с исходным, - Assk. Тогда вектор запроса, аналогично предыдущему методу, пополняется дополнительными терминами. Это, очевидно, расширяет число релевантных запросу текстов. Связь термина tk с множеством Assk может быть также представлена дополнительной графой справочника.
Для выявления ассоциируемых терминов строится матрица ассоциируемости, задающая для каждой пары терминов (tk, tr) показатель ассоциируемости a(k, r):
где fik, fir – частоты терминов tk, tr в тексте Di.
Этот показатель принимает значения от 1 до 0: если он равен 1, то термины полностью ассоциируются, если равен 0, то никакой ассоциации между ними не существует. На практике для определения ассоциируемости вводится некоторое пороговое значение показателя â. Тогда термины ассоциируются, если для них показатель ассоциируемости превышает это пороговое значение.
Этот метод применяется при кластерной организации файлов, причем кластеры не должны пересекаться.
Суть метода состоит в том, что наличие в векторе запроса некоторых терминов используется как основа для утверждения, что данный запрос с вероятностью p относится к кластеру Сl с профилем Пl. Если вероятность превышает некоторое пороговое значение, термины из профиля (или их веса) приписываются к вектору запроса.
Вероятность p рассчитывается следующим образом:
p(t1, t3,..., tT’, Cl) = в*p(Cl)*p(Cl, t1)*p(Cl, t3)*...*p(Cl, tT’),
где р(Cl) - вероятность кластера Cl:
,
|DiCl| - число текстов в кластере Cl,
n - число текстов во всех кластерах,
р(Cl, tk) - вероятность того, что каждый текст из кластера Cl содержит термин tk:
p(Cl, tk) =
FClk – общее число терминов tk в текстах кластера Cl,
FCl – общее число терминов в текстах кластера Cl,
Т’ - число терминов с ненулевым весом в векторе запроса,
в – константа, значение которой выбирается таким образом, чтобы выполнялось условие:
,
где С – общее число кластеров.
Схема информационной системы включает интерфейс пользователя (конечного или профессионала), который носит диалоговый характер. От организации интерфейса во многом зависит комфортность работы пользователя и функциональная полнота решаемых задач.
К настоящему моменту сложились следующие типы диалогов: вопрос-ответ; меню; экранная форма; командный язык; прямое манипулирование.
Диалог типа «вопрос-ответ», или регламентированный диалог, является первым в истории взаимодействия пользователя и ЭВМ. Почти сразу после появления первых вычислительных машин в середине 20-го века возникло желание организовать общение с ними на привычном для человека естественном языке9. Это позволило бы исключить специальную подготовку пользователя. Однако, в силу сложности данной задачи, она не решена практически до настоящего времени, хотя надежда разработать подобный интерфейс не оставляет исследователей. При этом виде диалога запросы пользователя и формируемые ответы системы имеют наперед заданную структуру и кодируются с использованием лингвистического обеспечения ИТ (ИС). В зависимости от ситуации инициатива ведения диалога может принадлежать компьютеру или пользователю.
Некое подобие данного вида диалога реализовано в условиях ограничений на язык или предметную область. При ограничениях на предметную область создаются 2 словаря:
Например, БД имеет структуру, соответствующую таблице:
|
фамилия |
дисциплина |
оценка |
|
… |
… |
… |
|
… |
… |
… |
Словари функциональных и специфических слов имеют вид:
|
Функциональное слово |
Интерпретация |
Специфическое слово |
Интерпретация |
|
|
какие |
найти и напечатать |
студент |
фамилия |
|
|
найти |
Search |
пятерка |
оценка=5 |
|
|
напечатать |
|
фамилия |
поле БД |
|
|
оценка |
поле БД |
|||
|
информатика |
дисциплина |
|||
|
дисциплина |
поле БД |
Тогда возможен запрос: Какие студенты сдали информатику на пятерку?
При обработке запроса в нем выделяются значимые для запроса – ключевые – слова. Сначала в запросе выделяется функциональное слово какие, которое, как видно из словаря функциональных слов, соответствует словам найти и напечатать (именно в такой последовательности). В свою очередь, каждое из этих слов связано с одной из процедур – Search и Print, соответственно. Таким образом, сформирована последовательность процедур для решения задачи. Ключевое слово какие определяет возможную структуру запроса в целом, что способствует дальнейшей его обработке.
Затем из запроса выделяются параметры, требуемые для работы процедур и определяющие нужные пользователю данные. По словарю специфических слов видно, что системе «известны» такие специфические слова из запроса, как студент, информатика, пятерка. Остальные слова отбрасываются как шумовые, не несущие смысловой нагрузки. Тогда исходный запрос преобразуется в некоторое условное промежуточное представление:
Search (фамилия | дисциплина=информатика оценка=5)
Print (фамилия)
При ограничениях на язык также поддерживаются два аналогичных словаря, но к структуре запроса предъявляются жесткие требования:
Для решения той же задачи, что и в предыдущем случае, при тех же начальных условиях запрос будет выглядеть следующим образом:
Найти фамилии студентов, сдавших экзамены по дисциплине = информатика с оценкой = 5. Напечатать фамилии.
Диалог данного типа применяется, когда диапазон входных величин слишком велик для структуры типа меню или сложен для командного языка, а последующий вопрос зависит от ответа на текущий вопрос.
Диалог типа меню – это диалог, при котором среди набора опций, отображаемых на экране (меню), пользователи могут выбирать и выполнять действия, тем самым производя изменения в состоянии интерфейса. Достоинство меню в том, что пользователи не должны помнить название элемента или действия, которые они ходят выполнить – они должны только распознать его среди пунктов меню. Таким образом, меню может использовать даже неопытный пользователь.
Форматы меню хорошо известны читателю из интегрированных оболочек операционных систем типа Far, Norton Commander, прикладных программных продуктов и т.п. Особым формат меню - иконки в качестве изображений объектов, приложений или действий, которые являются одним из элементов графического интерфейса и рассматриваются далее.
Для удовлетворения требованиям эргономичности интерфейса меню должно иметь следующие характеристики:
Диалог типа меню применяется в случаях, когда: диапазон возможных ответов достаточно мал, и все они могут быть явно отражены; пользователю необходимо видеть возможные варианты ответов; пользователь неопытен.
Командный язык удобен для организации диалога с операционной системой и пригоден для подготовленных пользователей. Имена команд должны нести смысловую нагрузку: они управляют данными, поскольку за ключевым словом в команде следуют параметры, состав и порядок которых определяется именем команды. Параметры могут быть позиционными, когда смысл параметра определяется его позицией в команде, и ключевыми, когда семантика операнда определяется предшествующим ему ключевым словом.
Пример – две команды копирования файлов операционной системы MS DOS (первая использует позиционные параметры, вторая – ключевые):
copy a.com b.com
copy source = a.com destination = b.com
Командный язык применяется, когда: число значений для ввода мало и их можно запомнить; ограниченного числа ответов достаточно, чтобы идентифицировать как требуемую задачу, так и необходимые данные; пользователь подготовлен; задачи не требуют много данных на входе.
Экранная форма предназначена для удобного и понятного ввода и просмотра данных, состояния, сообщений автоматизированной системы. В общем случае форма имеет информационную и управляющую часть: в первой вводятся данные, во второй – команды (ОК, Отмена, Сохранить и т.д.). Наглядными примерами экранных форм служат диалоговые окна операционной системы Windows.
Для эргономичности интерфейса экранная форма должна отвечать следующим требованиям:
Экранная форма имеет следующие преимущества перед предыдущими форматами: работает быстрее; может работать с более широким диапазоном входных данных, чем меню; может быть использована пользователем любой квалификации. Она применяется, когда заранее может быть определена стандартная последовательность вводимых данных.
Графический интерфейс (прямое манипулирование) – самый молодой вид диалога. В этом случае пользователь управляет объектами на экране посредством устройства манипулирования типа мышь. Этими объектами могут быть:
Цель создания эргономичного интерфейса состоит в том, чтобы сделать работу за монитором конечного пользователя (прежде всего) максимально удобной и комфортной. Для этого вводят критерии эргономичного интерфейса, включающие: естественность (интуитивность), последовательность (непротиворечивость), выделение элементов для привлечения внимания пользователя, организация системы навигации, поддержка пользователя, гибкость.
Естественность диалога – это такое его свойство, при котором пользователю не приходится существенно изменять свои традиционные способы решения задачи. Включает следующие принципы:
Последовательность ведения диалога гарантирует единство общих принципов работы с системой. Критерий включает:
Выделение элементов интерфейса используется для привлечения внимания пользователя. При этом следует помнить, что большое количество выделенных элементов может вызвать у пользователя дискомфорт.
Способы выделения элементов:
Система навигации обеспечивает пользователю способность перемещаться между различными экранами, информационными единицами и подпрограммами в ходе ведения диалога. Тип системы навигации существенно зависит от принятого вида интерфейса: для интерфейса языка команд очень мало способов обеспечения полноценной навигации; в интерфейсах с меню можно использовать иерархически структурированные меню, которые будут «направлять» пользователя. Общие принципы проектирования системы навигации включают: использование заголовков страниц для каждого экрана; использование номеров страниц, номеров строк и столбцов; отображение текущего имени файла вверху страницы.
Поддержка пользователя во время диалога - это мера помощи, которую диалог оказывает пользователю при его работе с системой. Включает:
1) инструкции пользователю - необходимы для направления пользователя в нужную сторону, подсказок и предупреждений для выполнения необходимых действий на пути решения задачи. Инструкции могут быть обеспечены в форме диалога, экранных заставок, справочной информации и т.п. Они могут предложить пользователю: выбрать из предложенных альтернатив некую опцию или набор опций; ввести некоторую информацию; выбрать опцию из набора опций, которые могут изменяться в зависимости от текущего контекста; подтвердить фрагмент введенной информации перед продолжением ввода. Инструкции могут быть помещены в модальные диалоговые окна, которые вынуждают пользователя ответить на вопрос прежде, чем может быть предпринято любое другое действие, потому что все другие средства управления заморожены. Это может быть полезно, когда система должна вынудить пользователя принять решение перед продолжением работы. Немодальные диалоговые окна позволяют работать с другими элементами интерфейса, в то время как само окно может игнорироваться;
2) подтверждение действий системы - используется, чтобы пользователь мог убедиться, что система выполняет, выполнила или будет выполнять требуемое действие (либо требуемые действия по каким-то причинам не выполнены). В полноценной системе пользователь также может всегда получить информацию о состоянии системы, процесса или активной подпрограмме;
3) сообщения об ошибках - должны объяснить, в чем ошибка, и указать, как ее исправить.
Ошибки могут быть классифицированы следующим образом:
Техника защиты от ошибок включает в себя аспекты:
Обработка ошибок в формах ввода включает обеспечение следующих действий:
Гибкость диалога - это мера того, насколько хорошо диалог соответствует различным уровням подготовки и производительности труда пользователя. При этом диалог может подстраивать свою структуру или входные данные. Гибкость диалога проявляется в способности диалоговых систем адаптироваться либо с помощью пользователя, либо самостоятельно к любому возможному уровню подготовки оператора. Существует три уровня адаптации: фиксированная, полная, косметическая.
При фиксированной адаптации пользователь сам явно выбирает уровень диалоговой поддержки, оценивая свою компетентность как новичка или эксперта.
При полной адаптации диалоговая система строит модель пользователя, которая меняется по мере работы его с системой и определяет стиль диалога. При этом главная проблема – распознавание характеристик пользователя, что является очень трудной практической задачей.
Косметическая адаптация является промежуточной адаптацией: гибкость обеспечивается без учета поведения пользователя и без однозначного выбора им конкретного стиля диалога.
Это достигается применением специальных приемов:
1B, F, P, V 4L
2G, J, K, Q, S, X, Z 5M, N
3D, T 6R
Например, вводится имя FORBES. Оно преобразуется в код F612. Пусть в системе есть имена FARBES, FFORBES, FORBOUYS, которые имеют такие же числовые коды. Поскольку возникла неоднозначность, пользователю поступает запрос на ее снятие.
Реляционные модели
1. Дан последовательный файл из N фамилий. Фамилия – первичный ключ. Файл упорядочен по алфавиту. По вводимой фамилии (Кпоиск) двоичным способом определить номер требуемой записи в файле или выдать сообщение о её отсутствии.
2. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. По вводимой фамилии (Кпоиск) блочным способом определить номер требуемой записи в файле или выдать сообщение о её отсутствии.
3. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. Сформировать индекс для индексно-последовательного способа доступа.
4. Дан последовательный файл из N элементов (N = m2, где m – натуральное число), содержащих поля «фамилия» и «номер зачетной книжки». Фамилия и номер зачетной книжки – первичные ключи. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для индексно-произвольного способа доступа. Доступ организовать по обоим полям, причем поле «фамилия» имеет приоритет.
5. Дан последовательный файл из N фамилий (N = m2, где m – натуральное число). Фамилия – первичный ключ. Файл упорядочен по алфавиту. Сформирован индекс для индексно-последовательного способа доступа (он размещен в отдельном файле). По вводимой фамилии (Кпоиск) индексно-последовательным способом доступа определить номер требуемой записи в основном файле или выдать сообщение об отсутствии искомой записи.
6. Дан последовательный файл из N записей (N = m2, где m – натуральное число), содержащих поля «фамилия» и «номер зачетной книжки». Фамилия и номер зачетной книжки – первичные ключи. Файл упорядочен по алфавиту по полю «фамилия». Построены два индекса для организации индексно-произвольного способа доступа, причем приоритет в поиске принадлежит ключу «фамилия». По ключу Кпоиск, содержащему значение зачетной книжки, индексно-произвольным методом доступа определить значение поля «фамилия» требуемой записи в основном файле или выдать сообщение об отсутствии искомой записи.
7. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом «Цепи подобных записей», для поиска по обоим вторичным ключам.
8. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Модифицировать основной файл, добавив в него поля ссылок, для организации доступа по каждому из вторичных ключей способом «Цепи подобных записей».
9. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике», а также поля ссылок для организации доступа способом «Цепи подобных записей». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам способом «Цепи подобных записей». Индексы размещены в дополнительных файлах. По ключу Кпоиск, содержащему оценку по математике, способом «Цепи подобных записей», определить фамилии тех, кто имеет искомую оценку.
10. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом оптимизированных цепей подобных записей для поиска по обоим вторичным ключам.
11. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике», а также поля ссылок для организации доступа способом «Цепи подобных записей». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам методом оптимизированных цепей подобных записей. Индексы размещены в дополнительных файлах. По ключам К1поиск и К2поиск, содержащим оценки по математике и физике, соответственно, методом оптимизированных цепей подобных записей определить фамилии тех, кто имеет искомые оценки.
12. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Сформировать индексы для поиска по вторичному ключу способом инвертированных файлов для поиска по обоим вторичным ключам.
13. Дан последовательный файл из N записей, содержащих поля «фамилия», «оценка по математике», «оценка по физике». Фамилия – первичный ключ, каждая из оценок – вторичный ключ. Файл упорядочен по алфавиту по полю «фамилия». Построены индексы для организации доступа к записям файла по вторичным ключам способом инвертированных файлов. Индексы размещены в дополнительных файлах. По ключу Кпоиск, содержащему оценку по математике, способом инвертированных файлов определить фамилии тех, кто имеет искомую оценку.
Деревья
Алексей
Анна Сергей
Ольга Иван Марина Станислав
Сети
женщины
Анна Марина Ольга
мать/сын жена/муж мать/сын бабушка/внук сватья/сват жена/муж теща/зять
Алексей Сергей Станислав Иван
мужчины
Здесь в записи <x>/<y> элемент <x> означает степень родства со стороны женщины, а <y> - мужчины.
1 Гносеология – это раздел философии, связанный с теорией познания; он объединяет методологические проблемы получения нового научного знания.
2 Обратите внимание на изменение формы глагола «отчислить»: для фактических данных он употребляется в прошедшем времени, фиксируя тем самым факт отчисления; для эмпирического закона он имеет смысл «обычно отчисляют» - это уже закономерность.
3 Более подробно и строго данные вопросы рассматриваются в курсе «Базы данных»
4 ER – (Entity-Relationship) – сущность-отношение (или связь)
5 Напомним, что записи файла упорядочены по возрастанию первичного ключа
6 в текущей таблице
7 в текущей таблице
8 Напомним, что ключами для структурированных данных являются поля, а не слова или словосочетания
9 Интересные описания подобных диалоговых систем и казусов, которые сопровождали их создание, можно найти в книге Б. Рафаэла «Думающий компьютер».
Производство
СУ
ОУ
АИ
НИ
КИ
ПИ
УИ
ОИ
Нормирование
Контроль
Планирование
Учет
Информация
о внешней среде
Цель
Управляющая информация (к ОУ)
Информация о
состоянии ОУ
(от ОУ)
Осведомительная информация
Анализ
Организация
Тактический уровень
Оперативный уровень
Стратегический уровень
Информация о внешней среде
Контроль
Учет
Нормирование
Планирование
Организация
АИ
НИ
КИ
ПИ
УИ
Анализ
Учет
Нормирование
Планирование
Организация
АИ
НИ
КИ
ПИ
УИ
Анализ
Планирование
Организация
АИ
НИ
КИ
ПИ
УИ
ОУ
ОИ
ОИ
ОИ
Цель
Осведомительная информация
Анализ
Информация о
состоянии ОУ
Управляющая
информация
Контроль
Контроль
Учет
Нормирование
Производство
Информационные массивы
Программное обеспечение
Интерфейс
Н
Ввод запроса
БД
Поиск элемента
Найден?
Модификация элемента
К
Нет
Да
Ключ
Данные
Размещение элемента
Н
Ввод запроса
БД
Поиск элемента
Найден?
Исключение элемента
К
Нет
Да
Ключ
Н
Ввод запроса
БД
Поиск элемента
Найден?
Вывод
К
Нет
Да
Ключ
Данные
студент
ФИО
номер зачетной книжки
числится
студент
номер зачетной книжки
ФИО
учебная группа
студент
числится
поставщик
потребитель
товар
заказ
сотрудник
ФИО
ченая степень
научное звание
контактные данные
кафедра
название
шифр в вузе
работает
числится
должность
название
образование
сотрудник
сотрудник
кафедра
сотрудник
должность
сотрудник
сотрудник
сотрудник
сотрудник
сотрудник
кафедра
сотрудник
сотрудник
сотрудник
кафедра
сотрудник
должность
название шифр в вузе
название образование
ФИО ученая научное контактные
степень звание данные
сотрудник
сотрудник
сотрудник
ФИО ученая научное контактные
степень звание данные
кафедра
должность
название шифр в вузе
название образование
сотрудник
сотрудник
сотрудник
ФИО ученая научное контактные
степень звание данные
Алгоритм рандомизации
Бакет 1
Бакет 2
.......
Бакет Nmax
К1
К2
К3
(1)
кафедра
название шифр в вузе
сотрудник
сотрудник
сотрудник
кафедра
название шифр в вузе
ФИО ученая научное контактные
степень звание данные
должность
название образование
кафедра
название шифр в вузе
кафедра
название шифр в вузе
должность
название образование
сотрудник
сотрудник
сотрудник
ФИО ученая научное контактные
степень звание данные
хронология поступления файлов в ТБД t
Ф1
Ф2
Ф3
Ф4
К1
К3
К2
К3
К1
К4
хронология поступления файлов в ТБД t
Ф1
Ф2
Ф3
Ф4
К1
К3
К2
К3
К1
К4
К1 Ф3
К3 Ф2
К2 Ф4
К3 -
К1 -
К4 -
хронология поступления файлов в ТБД t
Ф1
Ф2
Ф3
Ф4
К1
К3
К2
К3
К1
К4
С1 С2
Ф2 Ф4 Ф1 Ф2 Ф3
1
1