автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Система для поиска и обработки фактографических данных с выдачей информации в табличной форме

УДАРСТВЕННЫИ КОМИТЕТ СССР ПО НАУКЕ И ТЕХНИКЕ

АКАДЕМИЯ НАУК СССР

есоюзный институт научной и технической информации

(ВИНИТИ)

На правах рукописи

ЧИБИСОВ Валерий Иванович

удк [025.4.036:001.12]:519.688

СИСТЕМА ДЛЯ ПОИСКА И ОБРАБОТКИ ФАКТОГРАФИЧЕСКИХ ДАННЫХ С ВЫДАЧЕЙ ИНФОРМАЦИИ В ТАБЛИЧНОЙ ФОРМЕ

Специальность 05.25.05 — Автоматизированные информационные системы

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

МОСКВА 1989

Работа выполнена в Главном управлении внутренних , Мособлисполкома и во Всесоюзном институте научной и техни! кой информации ГК.НТ и АН СССР.

Научный руководитель: кандидат технических наук Черный Аркадий Иванович

Официальные оппоненты:

доктор технических наук, профессор Тарасов Евгений Васильевич, кандидат технических наук Енгалычев Али Махмудович

Ведущая организация: Всесоюзный научно-исследовательс институт информации и технико-экономических исследовани электротехнике (ИНФОРМЭЛЕКТРО)

Защита состоится « » С{ м^ёоиЯ 1ряд г. в 10 часов на седании Специализированного совета Д003.02.01 при Всесоюз] институте научной и технической информации по адресу: 1251 Москва, А-219, ул. Усиевича, д. 20А. 6'01/

С диссертацией можно ознакомиться в библиотеке Всесоюг го института научной и технической информации.

Автореферат разослан «

М

» ^¿¿-¿уэ и Ч ] дцд года.

Ученый секретарь специализированного совета, доктор технических наук

Петрова Лидия Андрее

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В современной деловой, коммерческой, правленческой и другой деятельности часто используется пред-тавление информации в виде различных таблиц. Данная работа на-равлена на автоматизацию процесса статистических наблюдений, особенных на полном или частичном (выборочном) изучении объектов явлений той или иной предметной области. Такие исследования ха-актерны для сферы работы правоохранительных органов, здравоохра-ения, социологических исследований и др.

Целью статистических наблюдений является получение информа-яи в виде статистических таблиц для последующего анализа и при-тгия управленческих решений. Получение информации в форме статис-чческих таблиц сопряжено с большими затратами как человеческого зуда по описанию таблиц, так и времени работы ЭВМ. Поэтому иссле-эвание принципов построения и разработка технически и экономичес-1 эффективных автоматизированных информационных систем, позволяю-IX непроцедурным образом описывать таблицы и получать нужную ин->рмацию с минимальными затратами времени, следует считать акту-гьной задачей, соответствующей общему направлению работ по широту внедрению автоматизированных систем во все сферы народного юяйства.

Цель работы: исследовать принципы построения системы для «иска и обработки фактографических данных и получения обобщен-й информации в виде статистических, а также атрибутивных (ре-:ционных) таблиц; разработать соответствующий комплекс языковых >едств для непроцедурного описания результатов поиска; разрабо-.ть алгоритм поиска, группировки данных и получения результатов табличной форме.

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

Практическая ценность. На основе выполненных диссертационных исследований разработана фактографическая система, которая позволяет на основе непроцедурного описания проводить информационный поиск и получать результаты в виде статистических и атрибутивных таблиц. Данная система може? использоваться в любой предметной области, где требуется проводить оперативную обработку массовых данных, представленных в объектно-атрибутивной -форме.

Реализация результатов исследования. Результаты диссертационных исследований использованы в ГУВД Мособлисполкома и Главном информационном центре (ГИД) МВД СССР при построении ряда автоматизированных информационных систем.

Апробация работы. Результаты исследований обсуждались и были одобрены на Всесоюзном совещании работников информационных центров МВД СССР (г. Вильнюс, 1982 г.; г.'Краснодар, 1986 г.).

Публикации. По результатам выполненных исследований опубликованы четыре печатные работы.

Структура и объем работы. Диссертация изложена на 146 страницах, состоит из введения, трех глав, заключения и списка литературы (102 наименования).

Краткое содержание работы.

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

3 главе I приводится краткий обзор современных прикладных систем (информационных, вычислительных, экспертных и др.); уточняется понятие таблицы и ее структурных частей, излагается принципиальный подход к организации процедуры для получения двух ти- • пов таблиц - атрибутивных (реляционных) и статистических, которые наиболее часто необходимо получать в системах коммерческого и производственного назначения; осуществляется сравнительный анализ систем, обладающих средствами представления результатов обработки информации в табличной форме.

Представление информации в табличной форме широко распространено на практике и является естественным для человека. Популярность этого представления информации объясняется обозримостью таблицы, легкостью ее понимания, компактностью и удобством поиска нужных сведений. С появлением работ по применению ЭВМ для автоматизации различных сторон человеческой деятельности, возник интерес к представлению результатов обработки в виде тех или иных таблиц и разработке соответствующих средств. В современной информационной технологии аспекты, связанные с получением информации в виде таблиц, получили отражение в таких терминах, как "генерация отчетов", "получение справки", "электронные таблицы", "табличной процессор" и др. Использование этих терминов в общем слу-

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

В данной работе в качестве базового термина для обозначения табличной формы принят термин "таблица". Таблица представляет собой множество вертикальных и горизонтальных делений, в местах пересечения которых образуются информационно значимые элементы, называемые клетками (ячейкйми). Вертикальные деления образуют столбцы, а горизонтальные - строки таблицы. Множество клеток составляет в совокупности матрицу таблицы (!Ш, в которой содержится информационный результат обработки данных - те или иные показатели в клетках. Для того, чтобы показатели в клетках ИГ могли быть интерпретированы человеком, таблица снабжается соответствующим текстовым оформлением (обрамлением), которое обычно состоит ' из трех основных элементов:-заголовка, головки (шапки) и боковика (левосторонняя головка) таблицы. Таким образом, таблица состоит из двух основных частей: матрицы таблицы и элементов текстового оформления.

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

I) для обработки табличной информации, т.е. такие системы, в которых информация на вход системы поступает в виде таблиц;

2) системы составления таблиц, которые формируют их в ре-ультате поиска и обработки данных с объектно-атрибутивным пред-тавлением. В данной работе рассматриваются принципы построения истем второго класса, т.е. с объектно-атрибутивным отображением редметной области.

Пусть ^Х = xj, xg, ..., xi, ..., xnJ- , где X - множество

бъектов некоторой предметной области. Под объектом понимаются еальные физические сущности, процессы или явления. Каждый объект ¿£Х (liiert) характеризуется набором признаков (реквизитов, арактеристик), которые в данной работе называются атрибутами: * = (aj, ag, ..., aj, .'.., а^. Атрибут имеет имя А и значение I, которое он может принимать из области допустимых значений область определения атрибута):

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

Наряду с получением атрибутивных таблиц, часто приходится решать задачу получения обобщенной информации. Под обобщением информации понимается такая процедура обработки данных, которая позв-оляет перейти от рассмотрения единичных объектов in.fi) к целостному рассмотрению всей совокупности объектов предметной области. Наиболее полно процедура обобщения проявляется в статистическом исследовании. Статистическое исследование представляет метод изучения реального мира, основанный на полном (сплошном) или частичном (выборочном) изучении объектов предметной области. Типичным примером выборочных статистических исследований могут служить социологические исследования. Примером сплошного статистического исследования может служить изучение всех кадровых анкет на том или ином предприятии. Процедура обобщения при статистическом исследовании выражается в образовании логических группировок объектов по определенной совокупности признаков. Результат обобщения в статистической исследовании представляется в форме статистических таблиц (простых или перечневых, групповых, комбинационных) . При автоматизированном получении статистических таблиц с помощью ЭВМ осуществляется поиск объектов, удовлетворяющих некоторому множеству поисковых условий, описывающих таблицу, и представление информации о количественных характеристиках всей изучаемой совокупности данных.

Атрибутивная таблица представляет собой множество кортежей значений атрибутов объектов, удовлетворяющих поисковому критерию, т.е- в этих таблицах отображается информация, которая в явном виде хранится в базе данных (ЕД). В атрибутивных таблицах может также присутствовать и производная информация, которую получают в результате некоторой переработки: итоги, средние, процентные

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

Статистические таблицы содержат производную информацию, т.е. информацию, которую получают в результате некоторой содержательной обработки исходных данных. Эта обработка заключается в идентификации объектов, которые удовлетворяют условиям, выражающим смысл строк и столбцов; в определении количества объектов, обладающих признаками тех строк и столбцов, на пересечении которых указывается количественная характеристика; в расчете специальных показателей (процентные отношения, средние и т.д.).

Таким образом, различие между атрибутивными и статистическими таблицами состоит в том, что в первых таблицах представляется непосредственная информация из БД, тогда как в статистических таблицах отражаются количественные характеристики совокупности, представляющие собой производную информацию. Формальное различие между этими двумя типами таблиц проявляется в том, что статистические таблицы имеют все элементы текстового оформления (заголовок, шапка, боковик), а в атрибутивных таблицах боковик отсутствует". Головка (шапка) атрибутивной таблицы содержит наименования атрибутов. За этими формальными различиями скрыто более глубокое «тличие, связанное с выражением смысла (семантики) таблиц. Смысл

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

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

Семантика статистической таблицы выражается, как отмечено выше, смыслом отдельных ее клеток и, таким образом, для таблицы, состоящей из М строк и Ы столбцов, необходимо представить предписание, в котором количество поисковых условий равняется произведению числа строк на число столбцов, т.е. составляет (М хН). Семантику статистической таблицы можно определить гораздо меньшим количеством условий, если смысл клеток выразить через смысл строк и столбцов. В этом случае предписание будет состоять из условий, количество которых равно суммр числа строк и столбцов таблицы, т.е. составит (М +Н ).

Таким образом, формирование атрибутивной таблицы сопряжено с проверкой одного логического условия, тогда как получение статистических таблиц связано с проверкой множества поисковых уело-

>ий, минимальное количество которых равно сумме числа строк и :толбцов таблицы. Из этого следует, что получение статистических -аблиц требует больших затрат времени работы ЭВМ, а для их опилил нужны специфические языковые средства, которые позволили ;ы описывать семантику таблиц наиболее компактным образом.

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

В современной информационной технологии моото выделить три ласса систем, работа которых в той или иной форме сопряжена с, редставлением информации в виде таблиц. К первому классу отнесем истемы для обработки таблиц, в которых информация на вход сис-емы поступает в виде готовых таблиц. Обработка информации в тих системах заключается в обеспечении хранения таблиц, полу-ении суммарных таблиц, выборке по запросу отдельных показателей др. Примером систем этого класса являются система ЭЛЛИПС, раз-аботанная для ЕС ЭВМ. К этому же классу можно отнести и таблич-ые процессоры, разработанные.для применения на персональных омпьютерах (Суперкалк, Лотус 1-2-3, Визикалк и др.). Сущность аботы табличного процессора заключается в том, что польэовате-ю на экране дисплея представляется пустой бланк таблицы, кото-ый он заполняет нужной информацией. Табличный процессор обеспе-ивает при этом получение тех или иных показателей по формулам яи на основании логических условий, запоминает таблицы, осугцест-

- 10 -

вляет их чтение и печать в нужном формате и т.п.

Ко второму классу отнесем системы для получения таблиц из ЦЦ с объектно-атрибутивным представлением информации. В свою очередь эти системы можно разделить на два класса: системы для получения атрибутивных таблиц и системы для получения статистических таблиц.

Многие современные СУЕД располагают функцией для получения атрибутивных таблиц. При этом процедуру их получения обычно называют генерацией отчетов, а соогветртвующее программное средство -генератором отчетов. Например, в системах ОКА, СЕТЬ имеется функция генерации отчетов; в системе ДИСОД эта функция называется получением справки.

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

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

- II -

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

- функция генерации статистических таблиц;

- функция генерации атрибутивных таблиц;

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

Для задачи обработки массовых данных и получения статисти-юких таблиц принято логическое представление в виде плоской |умерной модели или иерархической модели с отношением "один > многим".

В настоящее время существуют два принципиально разных под-да к разработке программной части информационных систем: системы генерации программ; 2) системы интерпретирующего ти-Системы генерации программ предназначены для получения про-амм на каком-либо языке программирования. Для этого они име-входной специализированный язык и набор макроопределений, с мощью которых описываются параметры нудной программы. Полу-нная в результате генерации программа далее обрабатывается ычннм образом, т.е. транслируется с помощью средств операци-ной системы. В результате получают готовый для прикладного

- 12-

использования загрузочный модуль.

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

Применительно к задаче получения информации в, табличном виде, системы генерации программ целесообразны для подготовки программ с перспективой их длительного использования. Однако испол! зование этих систем для оперативной выдачи информации вряд ли целесообразно, так как процедура получения информации является многоэтапной и достаточно громоздкой. Для оперативной ввдачи информации более предпочтительными являются системы интерпретирующего типа, так как они ориентированы на конечного пользователя и тем самым обеспечивают быстрое формулирование запроса и представление его к исполнению. Но получение информации в системе интерпретирующего типа может быть сопряжено с большим расходом времени работы ЭВМ, особенно при получении информации большого объема. В диссертации была поставлена задача разработки таких принципов построения системы интерпретирующего типа, характеристики которой не уступали бы системам, со специально подготовленной для выполнения той или иной функции программой.

Системы интерпретирующего типа, предназначенные для получения информации в табличном виде (для генерации таблиц), могут выполняться по схеме последовательного получения строк таблицы

системы строкового типа) или по схеме получения в оперативной амяти ЭВМ сразу всей матрицы таблицы (системы матричного типа), строковых системах генерация таблиц осуществляется последова-ельно строка за строкой, начиная с какой-либо начальной строки, ля получения статистических таблиц по такой схеме поисковый айл должен быть предварительно отсортирован по значениям атрибу-а, определяющего смысл строк таблицы. При получении атрибутив-ых таблиц упорядоченность поискового файла не обязательна, так ait необходимый порядок строк таблицы можно обеспечить сортиров--эй самой таблицы, если ее предварительно вывести на магнитный лек или магнитную ленту. Достоинство построчной генерации таб-яц состоит в том, что системы строкового типа не требуют много леративной памяти, так как в процессе генерации нужно сохранять формацию только об одной строке таблицы.

В системах матричного типа для хранения всей матрицы табли-i резервируется некоторая часть оперативной памяти, объем кото-)й при генерации статистических таблиц определяется следующим 5разом: V= M х H xL, где: V- требующийся объем оперативной шяти, M - количество строк, a fi - количество столбцов, в таблн-i, L - количество байтов, резервируемое для клетки матрицы, ютемы матричного типа более технологичны и удобны для получе-[Я статистических таблиц, тогда как системы строкового типа >лее удобны для получения атрибутивных таблиц. Для исследуемой [Стемн принят матричный метод получения статистических таблиц, получение атрибутивных таблиц выполняется по строковой схеме.

Системы генерации таблиц различаются и по способу доступа данным: это системы последовательного сканирования и системы прямым доступом к данным поискового файла. Известно, что по-

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

Рассматриваемую систему определим как систему с замкнутыми возможностями (закрытая система). Все функции такой системы описываются на непроцедурном языке высокого уровня, ориентированном на конечного пользователя или пользователя, входящего в состав администрации базы данных. Языковые средства системы представим в виде двух компонентов: языка описания данных и языка запросов. Состав языковых средств системы показан на рис. I.

Языковые средства

Язык, описания данных

Язык запросов

г

г

-г

Т

уровень

логический физический Язык Язык Язык Язык уповень генера- генера- кон- изые-•'ри о ции ции тро- нений статис- атрибу- ля тичес- тивных ких таблиц таблиц

Рис. I. Языковые средства системы

Язык управления запросами

- 15 -

Современный уровень той или иной системы предполагает ее независимость по данным, что означает: а) на логическом уровне -независимость представления от конкретного документа; б) на физическом уровне - независимость от конкретных характеристик среды хранения. Логическую структуру документов представим в виде совокупности атрибутов и будем выражать в терминах наименований атрибутов, в качестве которых используем трехзначные номера из десятичных цифр. Описание логической структуры отображается в виде специальной таблицы, которая в данной работе называется таблицей описания записи (ТОЗ) поискового файла. В запросах указывается лишь ссылка на имя этой таблицы. Кроме наименования, в ТОЗ указываются следующие характеристики атрибутов: тип, длина, координата от начала записи и некоторые другие. Допускаются следующие типы атрибутов: цифровой (информация представляется п виде десятичных цифр в зонном формате), упаковашшй десятичный (представление информации в виде десятичных цифр в упакованном фермате) , символьный (буквенно-цифровая информация), вектор (атрибут в впде совокупности подполей - в этом случае зиаченло атрибута представляет собой комбинацию значетЯ этих , полей).

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

Язык запросов позволяет выразить смысл той или иной функции, указать реяиыы ее исполнения, описать формат получаемых результатов и т.д. Ту часть запроса, которая служит для описания сгасла (семантики) функции, назовем поисковым предписанием (1Ш) за-

1-8

проса. Для описания семантики статистических таблиц представим ГШ' в виде трех компонентов, которые назовем: общие условия выборки (ОУВ), условия формирования строк (УСТР), условия формирования столбцов (УСТЦ). ОУВ выражают общий критерий отбора информации и соответствуют по смыслу заголовку таблицы. УСТР и УСТЦ выражают смысл катдой строки и кавдого столбца таблицы. Представление ПП в виде этой трехкомпонентной совокупности позволяет, с одной стороны, достаточно компактно выразить сммсл статистической таблицы, а с другой стороны, осуществить такое первоначально« разбиение ПП на части, которое позволяет сократить время обработки запроса и получения информации.

Предложения, входящие в состав ОУВ, УСТР, УСТЦ, представляют собой логические условия отбора информации, с помощью которых осуществляется первоначальное формирование матрицы таблицы, или описывают ту или иную вычислительную процедуру над клетками матрицы, полученной по логическим условиям.

Формат предложений ПП имеет следующий вид:

N Т < выражение. >,

где: И - трехзначный номер предложения, соответствующий номеру строки или столбца (или порядковый номер предложения в ОУВ);

Т - символ типа выражения;

"Выражение" - совокупность символов, соответствующая типу предложения;

"." (точка) - символ для обозначения конца выражения.

Предложения логического типа можно представить в конъюнктивной нормальной форме (КШ?), в дизъюнктивной нормальной форме

ДНФ) или в скобочной форме записи. Соответственно символ типа редложения может принимать следующие значения: ":" - выражение • КНФ, "?" - выражение в ДШ, "х" - предложение в скобочной форе записи.

Вычислительные предложения могут быть двух типов: аркфмети-еские и сравнительные. Арифметические предложения оперируют с омерами строк, столбцов или с координатами отдельных клеток матицы таблицы и позволяют выполнять над ними операции сложения, ычитания, умножения и деления. С помощью предложений сравнитель-ого типа осуществляется сопоставление результатов за текущий и рошлый годы. Символ типа вычислительных предложений соответствен-о может быть одним из следующих: "А" - арифметическое предложив, "5 " - сравнительное предложение с отображением относитель-ых величин приращения,- "С" - сравнительное предложение с отобра-:ением абсолютных величин.

Логические выражения описывают критерий отбора информации в оисковом файле в терминах наименований и значений атрибутов. Ло-'ические выражения могут быть простыми и сложными. Простое логи-еское выражение соответствует элементарному предикату, который южно представить в одной из трех форм: А^ИЕ, А-^А^, Ат-А^К 2,

■де А^, Л^ - наименования атрибутов, 2 - сопоставимая величина,

>' - символ типа отношения: "=" (равно), "ч=" (не равно), "^ " больше), "< " (меньше) и др. Выражение А-^ИХ описывает крите-

1ИЙ отбора записей (документов),, в которых атрибут А| имеет знание Z ; выражение А^ИА^ соответствует критерию отбора, в кото-' юм атрибуты А2 и А^ связаны отношением Б; выражение А|-А2К£

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

Ат и А^ связана отношением Н с 2 , причем атрибуты А^ и ^ мог>

представлять собой календарные даты. Сопоставимая величина 2 в выражении А^И 2 может представлять собой не одно, а некоторс

множество значений атрибута А^ из области его определения, пер< числяемых через запятую (запятая в этом случае выполняет роль соединительного ИЛИ).

Сложное логическое выражение строится из простых логичесю выражений,указанных выше типов посредством соединения их логич* кими связками И, ИЛИ. Для обозначения логического И использует! символ " и ", а логическая связка ШШ изображается символом "!'

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

с Г » Зл Уп ,

г>Н •

где ь; (¿«I, 2, ...,П) - начальный номер строки-столбца, а (¿=1, 2, .. 4, П ) конечный номер строки-столбца матрицы таблицы. V; (I «I, 2, ..., П ) обозначает цепочку из знаков ар1 метическях операций и операндов:

У-^ЬТц }ягл... ^ ху ... <рк гк ,

где (^«1. . .., к) - знак арифметической операции {"+" -сложение, - вычитание, "я" - умножение, "/" - деление); Ту - операнд, которым может быть номер строки-столбца таблицу литерал, элемент внешнего одномерного массива, отдельная клетк< ИГ.

- 19 -

о*

Посредством задания начального ( £>,; ) и конечного ( S¿ ) еров строк-столбцов таблицы определяется интервал действия фметического выражения V; . При этом в интервале указываются !ера строк, если операции выполняются над столбцами матрицы, :омера столбцов, если операции нужно выполнить над строками.

В статистических таблицах весьма полезной может оказаться ¡рация по получению информации, отображающей изменение тех или ис показателей по сравнению с показателями за аналогичный пе->д прошлого года (показатели динамики). Для получения такой ин->мации в языке запросов предусматривается задание предложений *ак называемым сравнительным типом выражения. Само по себе шнительное выражение лишь символ, задание которого в той или >й строке-столбце таблицы указывает на получение в этой стро-'столбце показателей динамики. Показатели динамики выражаются )иде относительных величин (приращение к данным прошлого года) I абсолютных величин.

Язык логических выражений составляет основу языков генера-1 атрибутивных таблиц и контроля (синтаксического и семантиче-эго) информации.

Поисковое предписание, выражающее семантику статистической 5лицы, в данной системе представляется в виде трех компонентов:

- общие условия выборки (ОУВ) язи

- условия формирования строк (УСТР) юш

- условия формирования столбцов (УСТЦ) ххх

мволами "ххя" (3 звездочки) обозначается разделитель этих тонеит.

- 20 -

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

Процедура информационного поиска при генерации таблиц состс ит в последовательной проверке этих трех компонентов^. Алгоритм* ческая сложность создания систем для получения статистических таблиц заключается в том, что для каждой записи файла необходимо осуществить последовательное сканирование большого числа поисковых условий, равного суше предложений УСТР и УСТЦ, которая может составить несколько сотен условий. Кроме того, атрибутам в предложениях ПП могут соответствовать длинные последовательности сопоставимых величин. Все это приводит к большим затратам машинного времени при попытке создания генераторов таблиц интерпрети-.рующего типа.

Для минимизации времени формирования таблиц в данной системе применен специальный алгоритм минимизации, основанный на понятии определяющего и ведущего атрибутов. Определяющим атрибутом назовем первый атрибут в предложениях УСТР или УСТЦ, полагая, что именно он в основном выражает смысл соответствующей строки/столбца.

Другие атрибуты, соединенные логическими связками И, ИЛИ и следующие за определяющим атрибутом, назовем дополнительными. Дополнительный'атрибут сужает смысл определяющего атрибута, если он соединен с ним связкой И. Смысл определяющего атрибута расширяется, если дополнительный атрибут связывается с ним логическим ИЛИ. Так как во многих таблицах, один и тот же определяющий

- 21 -

грибут используется для большинства строк/столбцов, то это эзволяет существенно сократить время сканирования. Для этого зедем понятие ведущего атрибута, который представляет собой тот ни иной определяющий атрибут с общей цепью сопоставимых величин, ри поиске осуществляется сканирование не строк/столбцов, а ве-ущих атрибутов (число которых значительно меньше числа строк/сто-5цов). А поиск в последовательности сопоставимых величин можно гуществлять одним из следующих способов: последовательным скани-ованием (линейный поиск), дихотомическим, вычисляемым, шаговым, качестве основного метода поиска в исследуемой системе принят ихотомический (метод последовательного деления пополам, логариф-нческий). Для этого поисковое предписание сортируется по номерам пределяющих атрибутов (сортировка осуществляется по методу Шел-а) и цепочка сопоставимых величин дополняется, если необходимо, о количества, кратного степени числа 2. Вычисляемый метод при-еняется тогда, когда цепочка сопоставимых величин образует моно-онную последовательность кодов. Шаговый способ (поиск через ин-ервал) применяется при поиске в последовательности символьных еличмн. Линейный поиск используется при малом количестве сопо-тавимых величин. Им же заканчивается процесс дихотомического оиспа, так как цепочка сопоставимых величин может содержать невольно одинаковых значений атрибутов; Выбор того или иного мето-,а поиска производится системой автоматически на основании пред-арительного анализа поискового предписания.

Внутреннее представление 1Ш на генерацию статистической 'аблицы представляет собой следующую совокупность векторов и •аблиц, связанных в единую списковую структуру: - вектор атрибутов ОУВ;

-22 -

вектор ведущих атрибутов УСТР;

- вектор ведущих атрибутов УСТЦ;

- таблица предложений УСТР;

- таблица предложений УСТЦ;

- вектор дополнительных атрибутов;

- вектор сопоставимых величин ведущих атрибутов УСТР и УСТЦ,

- вектор сопоставимых величин дополнительных атрибутов.

Поиск в этой списковой структуре для компонента ПП (ОУВ,

УСТР или УСТЦ) начинается со сканирования вектора ведущих атрибутов, из которого выбирается адрес начала цепочки сопоставимых величин. В векторе сопоставимых величин, в зависимости от длины вектора и типа атрибута, осуществляется пбиск по тому или иному алгоритму поиска (линейное сканирование, дихотомический или шаговый Поиск). Элемент вектора сопоставимых величин содержит, кроме самого значения атрибута, также и адрес строки таблицы •предложений, которой соответствует данное »качение. Таблица предложений в свою очередь несет информацию о номере строки или столбца таблицы и имеет адрес связи с вектором дополнительных атрибутов. Таким образом, если в записи поискового файла имеется значение, соответствующее ведущему атрибуту, то определяется, какой строке или столбцу соответствует это значение, а затем проверяется цепочка дополнительных атрибутов к этой строке или столбцу и вырабатывается признак соответствия записи тому пли иному условию. В результате проверки записи поискового файла по совокупности предложений ПП формируется последовательность номеров строк и столбцов, удовлетворяющих условиям поиска. На основании пересечения множества номеров строки и множества номеров столбцов определяются клетки матрицы таблицы, в которые нужно занести

(формации.

Таким образом, сокращение времени обработки запроса и полу-, тия результата при генерации статистических таблиц обеспечивайся, во-первых, раздельной проверкой частей трехкомпонентного I и принятия решения о целесообразности дальнейшей проверки; )~вторых, рациональной проверкой в структуре внутреннего пред-:авления того или иного компонента ПЛ.

В главе 3 описан ППП ГОТ (ГенератОр Таблиц), предназначенный m поиска и обработки фактографических данных и представления гзультатов в форме статистических и атрибутивных таблиц. ППП ГОТ заработан в соответствии с принципами, изложенными в главе 2, и зедназначен для работы на ЭВМ Единой системы, начиная с модели ЫО22, на ЭВМ с емкостью оперативной памяти не менее 512 Кб среде операционной системы ОС ЕС редакции бЛ и выше.

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

Основной единицей работы ППП ГОТ является "запрос", который эстоит из трех частей:

- управляющей информации (УИ);

- поискового предписания (ПШ;

г описания выходного результата (ОВР).

УИ содержит индексы, задающие режимы выполняемой работы, мл таблицы описания записи (ТОЗ) и другую необходимую информацию. И имеет объем в 160 байт.

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

языке системы ту или иную функцию. ОВР позволяет задать необходимый формат представления выходной информации. Например, при генерации таблиц ОВР включает в себя информацию о координатах вццеляемой из матрицы таблицы, адреса элементов текстового оформления (заголовок, шапка, боковик), информацию о ширине столбцов и т.д.

Архитектура ППП ГОТ показана на рис. 2. Основными частями пакета являются:

- управляющая программа (на рисунке не показана), обеспечивающая общее управление процессом обработки потока запросов;

- загрузчик, выполняющий чтение ПП и некоторую их предварительную обработку;

- транслятор, переводящий ПП во внутреннее представление;

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

- интерпретатор, осуществляющий проверку записей поискового файла на выполнение критерия отбора и формирующий в оперативной памяти ЭВМ матрицу таблиц;

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

- генератор атрибутивных таблиц, осуществляющий формирование и печать сведений о найденных объектах.

ППП ГОТ обеспечивает высокий уровень автоматизации прохождения запросов, что достигается посредством построения цепи связанных запросов по специальному полю УИ, в котором содержится адрес следупцего запроса. Возможности ввода отдельных частей запроса с тех или иных носителей информации (перфокарт, дисплея, магнитного диска) обеспечивают дополнительные удобства при работ« с пакетом.

Транслятор ТОЗ

ПП

Внутреннее пред ставле-ние ПП

Интерпретатор

Матрица таблиц

Генератор печати стаг тистичес-ких таблиц

Система управления файлами

Формат

1

Генератор атрибутивных таблиц

О

йлена атрибутов

Печать ста| тистиче-ских таблИ1

Текст

Рис. 2. Архитектура ППП ГОТ

выводы

В диссертации получены следующие основные результаты:

1. Исследованы задачи и условия функционирования систет предназначенной для обработки массовых данных и получения информации в виде статистических и атрибутивных (реляционных) таблиц.

2. Осуществлена экспликация понятия "таблица". Выделены типы таблиц: атрибутивные (реляционные), статистические, стрз турные, которые служат для представления результатов информах онного поиска в современных АИС; определены отличительные пр> знаки втих таблиц.

3. Выполнен сравнительный анализ некоторых современных С в отношении возможности их использования для получения и пре; ставления информации в виде таблиц.

4. Определены характерные особенности и требования, связанные с получением информации в табличной форме. Показано, ' получение статистических таблиц сопряжено с подготовкой преда саний большого объема, а сама процедура поиска,логической грз пяровки и представления информации в табличной форме, наэваш генерацией статистических таблиц, требует больших затрат врв! ни работы ЭВМ.

5. Определены следующие базисные функции системы:

- поиск сведений об отдельных объектах и представление информации в форме атрибутивной таблицы (функция генерации атрибутивных таблиц);

- поиск информации, ее логическая группировка по критер! ям, выражающим смысл строк и столбцов таблицы, и представлен]

- 27 -г

гльтатов в виде статистических таблиц (функция генерации ■истических таблиц);

- обеспечение технологических операций по накоплению, хра-по и актуализации данных, контролю поступающей информации и (функция ведения базы данных).

6. Разработано лингвистическое обеспечение системы. Языко-средства состоят из языка описания данных (ЯОД) и языка юсов (Я3)„ ЯОД служит для настройки системы на обработку тентов, представляемых в объектно-атрибутивной форме, и ¡печивает независимость от данных на логическом и физическом |нях. ЯЗ представляет собой ряд языков, предназначенных для мнения поиска информации, генерации таблиц, выполнения син-:ического и семантического контроля.

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

7. Разработаны алгоритмы поиска и специальные алгоритмы «цения для получения информации в виде статистических таб-

Семантика таблиц выражается посредством раскрытия смысла" (ой строки и каждого столбца>таблицы. Поисковое предписание юлучение таблиц имеет большой объем и представляет множест-'словий, число которых равно суше числа строк и столбцов, иботанные алгоритмы минимизируют время проверки »того мно-

- 28 -

жесгва условий и получения результатов.

8. На основе выполненных исследований осуществлена разработка и практическая апробация программно-математического обеспечения, которое выполнено в форме ППП, названного ГОТ (Генерэ-тОр Таблиц). ППП представляет собой систему с замкнутыми возмо; носяями и обеспечивает полный набор функций, связанных с приемом, хранением, контролем информации и ее дальнейшей обработке!

ППП ГОТ может использоваться на ЭВМ Единой системы, начиная с модели EC-I022, на ЭВМ с емкостью оперативной памяти не менее 512 Кбайт.

9. Проведены экспериментальные исследования и определены характеристики системы. Время получения статистической таблицы с суммарным количеством строк и столбцов порядка 100 единиц (100 поисковых условий) и объеме поискового файла в 100 тыс. записей на ЭВМ EC-I022 составляет в среднем от 5 до 15 минут.

Время ответа на запрос при генерации статистических табли в общем случае зависит от следушцих факторов:

- объема поискового файла и его коэффициента активности;

- объема предписания, описывающего ту или иную таблицу;

- характеристик предписания и его сложности, определяемой количеством конъюнктивных и дизъюнктивных членов, количеством сопоставимых значений атрибутов и др.

10. Результаты диссертационной работы использованы при создании ряда информационных систем и для решения отдельных возникающих задач в правоохранительных органах (ГУВД Мособлис-полкома, Главный информационный центр МВД СССР).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ . В РАБОТАХ:

Чибисов В.И. Автоматизированная фактографическая информаци-онно=поисковая система: структура и функционирование. - Сб. "Научн.-техн.информ.", 1984, сер. 2, (Р 12, с. 1-4. Чибисов В.И. Автоматизированная фактографическая информаци-онно=поисковая система: языковые средства и алгоритм поиска. - Сб. "Научн.-техн.информ.", 1984, сер. 2, К? 7, с. 15-18. Чибисов В.И. Возможности автоматизации статистико-криминоло-гических исследований на основе пакета прикладных программ ГОТ. - Москва, 1983. Депонирована в ГИЦ МВД СССР 28.11.83, Я? 83ДЦ, 38 с.

Чибисов В.И. Принципы построения пакета прикладных программ для статистической обработки информации. - Проблемы интеграции информационных ресурсов автоматизированных центров НТй. Тезисы докладов ХШ научного семинара "Системные исследования ГАСНТИ" (г.' Тбилиси, 23-26 ноября 1982 г.). М., 1982, с.89-91.