Инструментальный подход и его применение к построению систем управления базами данных тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

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

СИСТЕМНЫХ ИССЛЕДОВАНИЙ ВСЕСОЮЗНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ

СПЕЦИАЛИЗИРОВАННЫЙ СОВЕТ Д 003.63.02

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

АРЛАЗАРОВ Владимир Львович

УДК 681:3

ИНСТРУМЕНТАЛЬНЫЙ ПОДХОД И ЕГО ПРИМЕНЕНИЕ К ПОСТРОЕНИЮ СИСТЕМ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ

Специальность 01.01.11 — Системный анализ и автоматическое управление

АВТОРЕФЕРАТ

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

МОСКВА 1988

Работа выполнена во Всесоюзном научно-исследовательско институте системных исследований..

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

чл.-корр. АН СССР, д. ф.-м. н. С. С. Лавров академик АН ЭССР, д. т. н. Э. X. Тыугу д. т. н. Б. А. Чумаченко

Ведущее предприятие—Институт программных систе; АН СССР

Защита состоится «_»_ 1988 г. в_час. н

заседании Специализированного совета Д 003.63.02 Всесоюзног научно-исследовательского института системных -исследований п адресу: 117312, г. Москва, пр. 60-летия Октября, 9. Телефон Сс вета: 135-44-23.

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

Автореферат разослан «_»_1988 г.

Ученый секретарь Специализированного совета Д 003.63.02

Левченков В. С

ГОТЗЗЙ!*.

Актуальность темы. Курс на коренную перестройку всей жизни со-

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

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

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

- разработка теоретических основ инструментального подхода и построение методологии разработки и использования инструмен-1-Х

тальных систом.

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

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

- разработка архитектуры функционально полной СУБД и методологии ее использования.

Научная новизна работы. Проведенные в связи с решением крупной народнохозяйственной проблемы - разработкой СУБД ЙНЕС -теоретические исследования определили новое научное направление - развитие теории инструментальных систем - и ее применение к созданию систем математического обеспечения. В рамках этого направления получены следующие новые результаты.

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

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

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

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

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

Практическая тонкость и реализация результатов работы. Основным практическим результатом работы явилось применение инструментального подхода к решению важной народнохозяйственной задачи - разработке СУБД ИНЕС - одной из наиболее крупных и используемых систем математического обеспечения. СУБД ИНЕС, архитектура которой разработана автором, представляет собой ярко выраженную инструментальную систему, используемую в различных конфигурациях для реаения широкого класса информационных задач. Общее число организаций, использующих ИНЕС - около 1500. Годо-1-2

вой экономический эффект от внедрения системы составляет около 2 млн. рублей.

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

Апообаиия работы. Основные положения диссертации докладывались и обсуждались на "Советско-американском семинаре по байкам данных" (Москва, 1975 г.), П Всесоюзной конференции по банкам данных (Ташкент, 1983 г.), III Всесоюзной конференции по банкам данных (Таллин, 1986 г.), Конференции по применение СУБД в АСУ электротехнической промшцленностью (Таллин, 1982 г.). Школах-семинарах разработчикоков СУБД (Пярну, 1984,1985,1986 гг.), Всесоюзной школе по программному обеспечению (Новороссийск, 1983 г.), Всесоюзном совещании по проблемам АСУ МНТС (Алыа-ата, 1984 г.), Коференции по использованию СУБД (Москва, 1985 г.), / Всесоюзном совещании по системным исследованиям (МЬсква, 1986 г. У.

Публикации. По теме диссертации опубликовано 22 работы.

Структура работы. Диссертация состоит из введения, пяти глав, списка литературы и приложения. Объем основного текста составляет 278 страниц.

Глава 1 посвящена теоретическому рассмотрению инструмен-

тальных систем, методологии их создания и развития, границам применения инструментального подхода.

В главе 2 рассматриваются основные проблемы создания функционально полной СУБД, а также основные подсистемы СУБД ИНЕС.

Глава 3 посвящена теории моделей данных. Строится обобщенная модель, на которой рассматриваются проблемы эквивалентности баз данных, их представления, сложности. Сравнивается язык описания данных ИНЕС с описанием данных в алгоритмических языках.

Глава 4 содержит рассмотрение проблем восприятия данных и описание инструментального комплекса ввода СУБД ИНЕС.

В главе 5 анализируются элементарные операции работы с данными, строится набор операций реляционной алгебры над обобщенной моделью данных, разрабатываются требования к языку манипулирования, приводятся основные сродства реструктуризации ИНЕС.

В заключении суммируются основные результаты работы.

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

СОДЕРЗАНИЕ РАБОТЫ

Инструментальные системы. Новый класс систем, названных инструментальными, вводится при помощи описания свойств, выделяющих его из всего множества систем.

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

1-3

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

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

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

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

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

ментальноЯ системы является одной из важнейших характеристик ее качества.

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

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

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

Первый этап проектирования состоит в рассмотрении всего круга задач и выделении содержащихся в них потребностей. Проблема состоит в том, что граница проблемной области размыты, а кнегоциеся потребности недостаточно систематизированы. Конечно, 1-4

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

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

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

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

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

отдельных подсистем. Этот путь, уменьшая избыточность, приносит иногда большие дивиденды, но он требует специальных организационных и "информационных" механизмов.

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

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

а) появление новых потребностей, не покрытых подсистемами (недостаток средств);

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

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

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

Развитие инструментальной системы можно представить как взаимосвязанное изменение представления ее конструктора о проблемной области, самой системы и индивидуальных образов у ее пользователей. Даже исходное проектирование, учитывая традици-1-5

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

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

Кроме полноты охвата проблемной области, инструментальный подход обеспечивает определенны© преимущества с точки зрения построения и применения системы.

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

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

Пинямика знаний об инструментальной системе и гхМюктив-

ность.ео использования.

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

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

Введем следующую формализацию. Инструментальную систему 3=(1г) характеризуют потенциальная эффективность € и количество элементов N. В качество знания об элементе будет выступать уровень ого освоония х(. I). Грубо говоря, уровень освоения есть вероятность того, что элемент может быть использован, когда в нем возникнет необходимость. Эффективность системы для данного пользователя Э(() измеряется ее потенциальной эффективностью и сродним количеством освоенных элементов /У(0. Потенциальная эффективность соответствует ситуации, когда все элементы полностью освоены.

_ г _ (1) Э( /)=—•//{ О = £■•*(')

N

Уровень освоония элемента х(0 очевидно зависит от частоты обращения к нему. Мы примем допущение, что существует общая частота применения системы с и каждый элемент осваивается с частотой о=а/Л'. С другой стороны, со временем происходит умонь-1-6

■ -12- :•• шение величины х( - забывание.

Будем полагать, что изменение уровня освоения элементов х(О зависит только от самого х( О (и не зависит от предыстории) и подчинено уравнению

(2) х( <)=ч>(х, о) ¿>0, и>0, где ояа/М - частота обращений к элементу системы.

В дальнейшем будет рассматриваться только решение, проходящее через точку (<=0,х=0) (полное отсутствие знаний в начале), а относительно функции ф(х,о) в области (0ос<1,0<в><а>) будет предполагаться непрерывность вместе с частными производными, а также выполнение следующих естественных условий:

(а) <р(х,0)<0, ф(0,0)=0, <»(1,о)<0

Эч> Ощ

(б)— > 0 и при в>0 —(0,в)>0 да оа

В этих условиях имеет место утверждение.

При фиксированном а решение х( О монотонно возрастает и при ¿-»оо стремится к пределу •(•), являющемуся минимальным при данном <а корнем уравнения ч>(х,е)=0.

Вообще, любое решение, начинающееся в точке (¿=0,х=хд) монотонно стремится к пределу причем <»(<», ®)=0.

Функция *(») монотонно возрастает с ростом о и ограничена сверху значением 1, так что она имеет предел при <»-»■<х>; обозначим этот предел ^¡¡¡х.

Пусть имеются две системы и Рассмот-

рим их сравнительную эффективность при различных значениях о и {. Начнем с изучения Э^ и Э2 - предельных значений эффективности при /-»оо. Пусть >£1 > н2 • Из (1) следует, что (3)

Ввиду того, что *(о) при е-*со имеет предел Хддх. существует

частота обращения к системе о^ такая, что пря о>п^ эффективность использования более мощной системы выше.

Для сравнения эффективностей систем и ^ ПРИ малых с преобразуем выражение (3) к виду

Э1 = ^-о/Л^-4.(0/^) " ' >/(0/^ )

Если функция <р(о) имеет при о=0 производную и ф' (0)^0, то в приведенной формуле можно перейти к пределу при о-»0

Э1 •"«» »2/1*1

Рассмотрим подробнее случай, когда >-^2-> 1, или, что то

же, < —■. Выполнение этого неравенства означает неко-Н2

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

При этих условиях из (4) следует: существует граничное значение Од частоты использования систешг, такое что при о эффективнее использовать систему с меньшим числом элементов.

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

Рассматриваются две конкретные модели "обучения - забывания". По-видимому наиболее исследованные допущения о поведении

величины х(О состоят в том, что ее зависимость от времени описывается следующими уравнениями х(1)=-к^хС1) (забывание); х(О) (обучение), где - константа, характеризующая скорость забывания; *2 - константа, характеризующая способность к обучению; о - количество подкреплений в единицу времени.

Обычно уравнения обучения и забывания рассматриваются отдельно. Однако, если принять, что подкрепление происходит равномерно, можно написать общее уравнение:

¿V®

В данном случае ч>(®)=-•— , а график зависимости предельной (при <-*со) реальной эффективности от частоты обращений для двух систем ^ , > и 52 <.^2 • > выглядит следующим образом

Эффективность системы ^ с ростом о постепенно "догоняет" эффективность сравнивается с нею, а затем становится и остается больше.

Представляется интересным рассмотреть величину "»(Од/уу) -

"среднев" освоение элементов в критической точке Ц) .

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

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

В обобщенной модели качественная картина может быть существенно более сложной. Мы рассмотрим пример, в котором р(о) и соотво£ственно эффективности Э! и Эз не будут непрерывными функциями частоты.

Пусть закон изменения научения задается, как и раньше, формулой х(1)=Ацш(1~х( ()), а забывание определяется уравнением х(П 0-(1-*( О)2

Это уравнение отражает гипотезу, что хорошо выученный материал забывается медленнее. Общее уравнение изменения х(О в этом случае выглядит так:

х( I )=(1-х( ОХ Л^о-А^хС '))

В терминах обобщенной модели

1 1 Ь к\

-----*-е> при оч ■ *

2 4 4*2

1 при о> —*—

4*2

График зависимости эффективности Э^ и Э2 от а представлен на рис. 2.

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

рис. 2

Развитие инструментального подхода ттля постпоения СУП1Г.

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

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

ные или неудачные решения в применяемых СУЕД прямо влияют на эффективность использования вычислительной техники. Между тем, сотни Тысяч людей, занимающихся задачами обработки данных, прод%являют столь противоорочивые критерии оценки СУБД, что вряд ли их можно положить в основу проектирования.

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

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

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

Рассматривая языковые аспекты манипулирования данными, можно придти к выводу, что наличие сложившихся (и воспринимаемых почти как канонические) приемов работы с данным толкает в сторону включения в язык емких операций; в ту яе сторону дейст-1-9

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

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

СУБД должны иметь средства, позволяющие предъявить (описать) внешнюю схему, и моханизмы, преобразующие структуры данных базы к виду, требуемому внешней схемой. Возможны, в принципе, два пути для построения такого преобразования. Физическое преобразование хранимого объекта предполагает создание, по существу, новой базы данных, над которой впоследствии и осуществляются все операции. С другой стороны, можно интерпретировать требуемые отношения и операции как действия над существующей базой (с исходной концептуальной схемой); при этом образуется объект, логически неотличимый от базы с требуемой внешней схемой. Рассматривая достоинства и недостатки каждого подхода, мы приходим к выводу о необходимости включения в состав СУБД средств реструктуризации разного уровня: от выделения подсхемы как подмножества схемы до реализации внешней схемы с моделью данных, отличной от модели данных концептуальной схемы.

Сегодняшня пользователь информационной системы мыслится, как правило, сидящим за дисплеем. Условно можно выделить три

ОБЕСПЕЧЕНИЕ ЦЕЛОСТНОСТИ

МАНИЛУЛИРОВАНИЕ ДАННЫМИ

Л физический

0 иерархический

с т элементарный

У логический

II

технология

-семантический уровень

система ведения картотек

-логический Уровень

блок контроля

•физический уровень

архивная система

системный журнал

ПОСТРОЕНИЕ ВНЕШНИХ МОДЕЛЕЙ

схемы подсхемы типы данных

ТЕРМИНАЛЬНЫЕ СРЕДСТВА

визуализация объектов

язык сценария диалога

многотерминалъный монитор

обеспечение сетей

связи

СИСТЕМЫ 1ХГОГРЖЖР0ВАНИЯ

структурное программирование

динамическая привязка

программ

организация потоков

ввода-вывода

системы редактирования

интерфейсы задач

Рис.3

-20- . ■

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

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

Кроме описанной, функциональной, классификации особенностей терминальных средств, можно рассмотреть их типизацию по ориентации на определенный класс потребностей, или уровень пользователей. Рассматриваются четыре таких типа: исследователь, технолог, абонент и менеджер и показывается, что их требования к терминальным средствам существенно различны. Указанные обстоятельства требуют предусмотреть в СУБД инструментарий для разработки неспецифического диалога и в то же время обеспечить диалоговые потребности при работе с базой данных. В ИНЕС мы имеем, с одной стороны, многотерминальный монитор, средство просмотра результатов и язык сценария диалога а, с другой -универсальный механизм просмотра и коректировки значений и структур базы и систему построения диалога конечного пользователя.

Иолели пенных. Число моделей данных, используемых в различных СУБД, весьма велико. Традиционно они разбиваются на три типа: реляционные, иерархические и сетевые. При этом только для реляционных моделей существует более или менее развитая теория. В работе развивается теория сетевых моделей, причем иерархичес-

кие и реляционные модели присутствуют в ней кал частные случаи сетевой.

Единая формализация позволяет сравнить все три типа моделей с нескольких точек зрения.

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

- множество атрибутов А, состоящее из трех непересекающихся подмножеств: Ае -простых атрибутов, Да - атрибутов массива и й5 - атрибутов структур;

- система 5/? подмножеств множества атрибутов - схем отношений;

- система НО множеств О - доменов, элементы 1КО (ОсНО обычно связаны с некоторой семантикой прикладного характера;

- отображения ф:Ад->НО и причем Ч(ДтШ5 )=5Л. Тогда определено описание данных 5<Дв,Ат,й5 НО,ф,*>

(иногда его называют схемой базы данных). Пусть имеются также:

- множество Д экземпляров отношений;

- множество С кортежей;

- двуместный предикат х(с,г), определенный на парах элементов ас и Пй, причем для каждого кортежа ас подмножество йс экземпляров отношений г, для которых х(.с,г)=1гие, не пусто;

- отображение 1:Й-*Дт 1М5, причем

а. если Ь(.г)*А3, то подмножество Сг кортежей, для которых х(е,г)=1гие, состоит из одного кортежа ас или пусто;

б. если х(с,л1)=х(с,/-2)=<г(/р то ч>(Ь(г1))=Ф(£(г2))е5/?. Таким образом, определены отображения 9=ч>£:/?-».5У? и

> Т1:С-*5Я, где п(0=5г<5Я в том и только том случае, когда для ' некоторого экземпляра отношения гей, х(.с, г)=1гие и е(г)=5Л.

1-П

Для каждого атрибута <НА можно определить подмножество Са кортежей, для которых а*п(с). Пусть еще заданы подмножества г^с са, ША и отображения ш0:Г0-»ф(о) (а(Ад) или оа : гд (о) (а(АтиА5). Тогда определена база данных х, Ь, {аа}а(А*'

Если в0(с)=г, оСЛ^и^ или ®а=<Л а*Ад, то экземпляр отношения или элемент домена ¿=ф(<7) называется значением атрибута а в кортеже С. Если съсд\га, то атрибут а в кортеже С имеет неопределенное значение. Если х(с,г)=/о/5в, то экземпляр отношения гШ называется пустым.

База данных называется финитной, если л=»лвилдаил5, Я и С -конечные множества, НО - конечная система множеств, и каждый домен ОШО имеет не более, чем счетную мощность. Таким образом, система доменов НО состоит из двух подсистем НО/ - конечных и Н01 - счетных доменов.

Описания баз данных 5' , А'т,А'$ , ,НО' ,9', ф' > и $"<А"д,А"т,А"$ ,$Я",МО", ф", ф"> называются эквивалентными, если имеются взаимно однозначные соответствия а:А'++А", й;НО'++Н0"

и Эд :0' ) (.ОЧНО'), при которых: ограничения а |' , а| ,

"в лт

а| являются взаимно однозначными соответствиями <х|л,: Ад ++А2,

я$ яд

"I л< : подмножества ¡'сА' из системы 5/?' и

Я 5

s",c^í,• из системы 5/?" находятся во взаимно Однозначном соответствии; отображения ф' и ф", ф' и ф" переходят друг в друга. Базы данных

В'<5' ,С' ,х' .V > и Я,Ч^*и.С",х,\Ь,\{®"0»}<Г«>Г>

называются эквивалентными, если эквивалентны их описания данных и а также имеются взаимно-однозначные соответствия

и 4: с , при которых переходят друг в друга: предикаты х'( с',г') и х" (. с", г"); отображения и t"; подмножества С}/ и С"; подмножества г¿, и Г"^; отображения и а"^ при

э

эквивалентных атрибутах о'(А' и о"=а(о'(при учете взаимно однозначных соответствий вр :£>' =ф(С )«*/Г=ф"(о"))•

По существу, объект, называемый реляционной базой данных, является базой в смысле определения, данного в этом параграфе при выполнении следующих условий:

1. Множество состоит из одного элемента а.

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

3. *<«>=*„

4. Множество экзе?<шляров отношений Я содержит один и только один экземпляр Р, а множество кортожей - один кортеж -у, такие что х( В, 7>=?гие. Атрибут а, отношоние Р. кортеж у -это разнио аспекты реляционной базы данных В, рассматриваемой в целом.

5. Отображение ¡.:Я(а) взаимно однозначное, т.о. каждой схеме отношения соответствует один экземпляр отношения.

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

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

X. Каждый экземпляр отношения г(Я является значенном соответствующего атрибута Ь(г) не более, чем в одном кортеже .

2. Для каждого кортежа с(С; х(с, г)=/г(/е только для одного экземпляра отношения г(в, т.о.

час Х(Л1,с)=Х(Г2.С)=(/-£/£7-^Г1=Г2

Реляционная модель, где данные разбиты на именованные от-1-12

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

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

Обратное, вообще говоря, неверно, вследствие того, что имеет место следующая

Теорема о Финитных реляционных базах данных с конечными доменами. Пусть $<Ад,Ат,А3 = (.а') ,$/1,Н0,<р,1})> - описание данных Финитных реляционных баз данных С, х, Ь, (вд),^ >, в котором

все домены 0Ш0 конечны. Тогда конечно и множество классов сильной эквивалентности таких баз данных.

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

А д'=Ат=НО=0, А5=(наследник), «л=45, ф(наследник(наследник).

На рис. 4 изображены базы данных с этим описанием, принадлежащие разным классам сильной эквивалентности.

С ншедник 3 с ншедиир ..... С наследник")

%

рис. 4

Легко видеть, что все базы данных Вп принадлежат разным классам эквивалентности, а их количество бесконечно.

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

Пусть каждое слово С формального языка С однозначно определяет базу данных В с описанием 5, т.е. задано отображение Г:С-*НВ, где МВ - некоторое множество баз данных. Мы будем называть такое слово представлением базы данных В , а множество Н баз данных, представимых с точностью до эквивалентности словами языка С,- классом баз данных, представляемых этим языком. Множество баз НВ , являющихся образами /"(О слов - собственное подмножество класса Н , так как последний содержит базы В', эквивалентные базам В(НЗ, но не принадлежащие НВ . Различные слова Ш могут представлять эквивалентные или даже совпадающие базы.

Теорема о представимости класса финитных баз данных. Су-

((тсл8ани1с)3

*вг

(ЧнасибдникО С тстник )

_ X

((тсианик))

С шсшншГ)

) п «ровней

ществует формальный язык представляющий класс НГ финитных

баз данных.

Для доказательства сначала устанавливается структура слов I языка ¿у, а затем определяется конструктивное отображение /:п-*ИГ. Слово I языка представляющее базу данных В, конструируется как последовательность подслов, представляющих по отдельности каждое множество, отображение и предикат:

В Таблице 1 показан способ представления всех элементов базы данных и, таким образом, установлена структура слова I языка I у, которая охватывает представления любой базы.

В силу перечислимости всех множеств и конечности представления, довольно очевидна возможность конструктивной проверки зависимостой, сущоствующих в базе данных между элементами. Если последовательно генерировать всо слова, состоящие из букв алфавита с и отбирать только-те, которые являются словами языка ¿у и удовлетворяют всем условиям, накладываемым зависимостями, то получится конструктивное отображение /: 1Я-*НГ.

Пусть с - конечный алфавит. Тогда существует разных слов длины к. Поэтому считается, что слово и, состоящее из символов алфавита г, содержит \v\-log\t\ бит информации. Это количество иногда можно считать мерой сложности представления финитной базы данных В. Однако, следует заметить, что часть слова и связана с семантикой рассматриваемых объоктов, и содержащаяся в ной информация формальным образом не определяется.

Чисто семантический характер носит представление элементов доконов ¿££=>©¿11к'Оу. Рассмотрим, например, бесконечный порочис-лиыыЯ доиен НО^ я пусть его элементы <1к представляются своими номерами к. Тогда длина части слова у. относящегося к продстав-

Множества Таблица 1

Имя I Содержание Имя 1 Представление

1 элемента I элемента

"в I Множество простых атрибутов ак 1

Ат I Множество атрибутов массивов °к 1

I Множество атрибутов структур ак 1.

Н01 I Множество бесконечных доменов °1к 1

НО/ [Множество конечных доменов О/к 1 описано ниже

5/? (Множество схем отношений $гк 1 описано ниже

I Коночный домен к 1

¿Р I Схема отношения (номером

Я (Множество экземпл. отношений гк 1

С (Множество кортежей ск I

ы га 1 описано ниже

га I Множество- кортежей, содержа- ас 1 номером

Iцих значение атрибута а 1

Ы "а 1 описано ниже

Отображения

Имя I Содержание Формула

Т (Атрибут -» схема отношения -*■ ЗЯ

<» ¡Атрибут -* домен \Ад-*Н01ъ)МО/

Ь |Экземпляр отношения -* атрибут

Од |Кортеж -* значение атрибута I г0 -»ь-1 (о)Цф(о)

Предикат

Имя I Содержание I Представление

х(с,г) (Принадлежность кортежа |Последовательностью пар номе-I экземпляру отношения |ров (с,/-), для которых I |х(с, г)=1гив

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

Поэтому вводится понятие структурной сложности представления базы данных. Если исключить из слова »/(I/у подпоследовательности символов, являющиеся представлениями элементов, несущих семантическую информацию, то получится слово я , определяющее структуру Сазы данных В. Структурной сложностью представления этой базы называется | »/Ыод|£|.

Для рассмотренного выше представления с двоичным алфавитом структурная сложность "больших" баз данных имеет порядок ]У\-0(\Х\-1од\й\, где X -множество пар (с,г), для которых х(с,г)=1гив. При этом сама оценка неулучшаема при любом способе представления.

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

Мозель данных ИККС образуется из рассмотренной обобщенной модели некоторыми ограничениями на способы образования сотовых связей.

Синтаксис языка описания данных ИНЕС представляется в мо-

-29-

дифицированной БНФ следующим образом.

описание данных: := [словарь;] элемент; [элемент;] ... END-, словарь: := 40C/4N= имя,0М=имя/ семантика: DON описывает имя DD предложения, IW-внутренее имя элемент::=[имя:]данное/имя'

данное::=простое/структура/массив/ссылка/словарное простое: :=вид[спецификации] ['значение'] вид:: = ¡NT/REAL/DEC/TEXT/RTEXT/L 0C/DUHHY семантика: ЙТЕХТ - текст, кодированный для сортировки по русскому алфавиту; DUHHY - данное без значения; остальные типы общеупотребительны. Спецификации задают детали внутреннего и/или внешнего представления, как то: $¿¿в=число[.число], key (элемент является ключом элемента массива).

словарное: :=VOC/COOE[/буква/] /ЯШ?£[/буква/] семантика: VOC - в базе хранится идентификатор слова;

CODE - в базе хранится "код" - первое слово связи, определяемой по данному слову, с "префиксом"- указанной буквой RCODE - хранимое слово кодированно как ЙТЕХТ структура:: =STRUC T/FS TRUС T/COND (...) семантика: FSTRUCT - "жесткая структура" - аналог записи, все подчиненны» структуры, автоматически считаются жесткими;

COND - условная структура; из всех элементов в каждый момент присутствует не больше одного. В скобках перечисляются элементы - члены кортежа

массив:: =ARRAY(oneuenT)/ARRAY//ft/ff=YES/C9^<3Mom')/ ARK{элемент [;элемент]...) Основной конструкцией данных ИНЕС является массив, соответствующий экземпляру отношения обобщенной модели.Возможны слепые массивы (элементы доступны только последовательным прос-

мотром), нумерованные (элементы доступны также по номеру) и ключевые (с каждым элементом связан ключ - данное, по которому возможен поиск элемента). Элементом массива обычно является структура (кортеж); элемент слепого и нумерованного массивов может быть и неструктурирован, т.е. быть простым данным. Элемент структуры может быть в свою очередь простым данным, структурой и массивом любого типа. В отличие от традиционной для многих СУБД трактовки кортежа, элементы структуры в ИНЕС независимы и потому не обязаны присутствовать все одновременно. Кроме того любой элемент может присутствовать, но иметь неопределенное значение.

Шаблоны и рекурсии. Язык описания данных ИНЕС позволяет использовать "шаблон" - описание данного в качестве описания типа, подобно конструкции "LIKE" в PLI. При этом, поскольку ИНЕС не накладывает никаких ограничений на сложность описания, то данная возможность является весьма мощным сродством структуризации.

Заметим, что запрет рекурсии в языке АДА, такой как

АДА ИНЕС

type FATHER Is record 01 отец: STRUCT

SON:FATHER 02 сын: /5'отец

H АНЕ". S TRI HCC 1.. 20 ) ; 02 имя: TEXT

end record;

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

Характерной особенностью языка описания данных ИНЕС является его практически полная адекватность описаниям данных в

языках программирования. В то же время семантика ЯОД ИНЕС существенно шире и, в частности, не исключает рекурсии. Это создает основу для того, чтобы сделать универсальный язык програм-мированиия одновременно языком манипулирования данными без привнесения в алгоритмический язык чуждых ему конструкций типа СЕТ, PUT и им подобных. Такие возможности предусмотрены в некоторых современных языках.

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

Одна из центральных, проблем создания и поддержания базы данных - проблема восприятия ижЬопмашти. пополняющей или корректирующей базу - рассматривается в главе 4.

Вводится понятие динамической (изменяющейся во времени) базы данных В(О. переход которой из одного состояния в другое происходит в дискретные моменты времени • '2• * * * ((1<с1+под влиянием "сообщений".

База данных £(О возникает в начальный момент времени fj, имея начальное состояние 3()=Sj (часто Sj - пустая база данных). В результате взаимодействия текущего состояния и сообщения 1л/1 - возникает следующее состояние Bl+l=F(Bl,lnfl\.

Пусть заданы множества виртуальных состояний рассматриваемых динамических баз данных ИВ и виртуальных сообщений Virtinf, тогда F-.HB*Vlrtlnf-+MB.

Однако, вследствие ошибок в реальных сообщениях, может оказаться, что In/^tYlrtinf. Для выявления таких ошибок при вводе информации осуществляется синтаксический контроль сообще-

-32- ' -

ний. Реально алгоритма синтаксического анализа выполняют еще

одну функцию^ Дело в том, что отображение Г, как правило, представляется как суперпозиция двух: В1+1=Г<.В1. ¿п/1 )=Г2(-б1 ))

Здесь отображение Г^Цп/р переводит слово языка У1г11п/ в слово другого языка Врешая соответствующую задачу синтаксического анализа. Содержательно, язык Ч1г1щ связан с представлением информации во внешнем мире, тогда как Вщ - с удобством ее обработки в ЭВМ.

Рассматривается проблема конструктивности синтаксического контроля в рамках формальных языков. В частности показано, что если х=о(л) и п=ниМ(х) - алгоритмы генерации и нумерации слов соответственно, то наличие алгоритма К1/М(.1п/еще не обеспечивает конструктивного решения задачи синтаксического контроля, поскольку может не существовать обратного алгоритма ®(л) генерации элементов, который бы позволил проверить равенство «>(.мим(.1п/¡^))=1а/1, чем и завершить синтаксический анализ. Хотя такого рода "необращаемые" алгоритмы анализа широко используются, в частности, как корректирующие, их бесконтрольное применение весьма опасно.

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

- первичное накопление документов;

- редактирование документов;

- расшифровка документа;

- контроль документов;

- ввод документов в базу.

Приведенная декомпозиция системы ввода данных на подсисте-

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

Приведен сравнительный анализ предложенной архитектуры систем восприятия данных с архитектурами интегрированных систем и многомашинных систем с распределением функций.

Далее подробно рассмотривается подсистема ввода СУБД ЙНЕС как набор инструментальных средств. Центральным механизмом всей подсистемы первичной обработки документов является служба архива, обеспечивающая хранение первичных документов, их коррекцию, возможность выборки для многократного повторного контроля и для использования в других подсистемах. Архив можно рассматривать как множество О документов, где каждый документ НО представляет собой последовательность текстовых строк снабжен протокольной информацией Р, состоящей из записей р^Р, отражающих историю создания, и текущим статусом Таким образом документ характеризуется четверкой </,Е,/',5>, где / - идентификатор документа.'

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

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

ментов.

/•(/>)=/x(tf¿iV ••• '/*<£/¿¿) ' где /„:</ </„,г ,Р .S > -* (Г <//</„>,/e(c,.)./p(¡P. >./s(í¿ ».

'л ln ln lfí ln 'л , . '/7 'л

- функция именования, /0 - функция изменения текста, fp -функция изменения протокола, }s - функция изменения статуса. В работе дано краткое описание и назначение этих функций.

Комплекс первичного ввода ИНЕС построен как система с управляющим интерфейсом: фиксированы лишь наличие и порядок взаимодействия этапов обработки, а реализация каждого этапа производится отдельным модулем - исполнителем. Информационные связи модулой фиксированы (и сведены к минимуму), а связи по управлению определяются - и обеспечиваются - интерфейсом. Пусть М=[/я) - множество сообщоний лт=( ¿(/я), с(л?)), гдо /(л?) - текст сообщения, ИТ, с(/я) - класс сообщения:

с( С = С запись",'пусто*,'конец','документ'стоп'). null - пустое сообщение: t(.null)=V, c(nul /)='пусто'. Моханизм ввода представляется как набор С f^ .fj ■ •'•-^к Э ко~ ночных, автоматов - исполнителей. Обозначим чероз r¿CH входное

сообщение исполнителя F, , и(Н - его выходное сообщоние. Состо-

1

яние исполнителя включает некоторое сообщение s¿ и, быть может,

переменные, не контролируемые интерфейсом.

Если £"=(£", .С. , — ) - фиксированная последовательность, '1 12

описывающая порядок работы исполнителей, то алгоритм интерфейса сводится к следующему

если u¿ t null; íí+j=f¿-l если и i - null;

если c(w¿) = 'стоп', то обработка заканчивается.

-35В этих терминах описывается логика стандартных исполнителей системы первичной обработки ИНЕС - модулей: чтения входного потока (£1), разбиения входного потока на документы (£2), разбиения текста документа на строки (£3), индексации (£4), записи (£5) И протоколирования (£6). Все подсистемы первичной обработки представляют собой независимые средства, которые могут использоваться (и реально используются) в различных комбинациях. Тем не менее, они нацелены на определенную технологию их совместного использования

ршктироинш

рис. 5

В системе анализа и контроля документов ИНЕС разделяется первичная фрагментация документа - выделение в нем информационных полей (окон) - от его структуризации - построения схемы. В простейшем случае для анализа текста документа оказывается достаточно двух разделителей: признака конца текста окна и признака конца имени окна. Пройдя стадию фрагментации, документ в виде "списка окон" поступает на вход системы контроля.

Для контроля документа имеется три способа действий, реа-лизованых на базе независимых инструментальных средств.

В первом случае пользователь ШЕС предоставляет таблицу

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

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

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

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

81 А 1. Встать i вершина А

82 »5 2. спиститкс! ПО кявчу, ЗНаЧвМИ» которого

находится в окне 5 83 В 3. Спуститьсв в ввриина В

94 (18.28) 4. Фганюшть цикл по группы окон документа

с номерами 18 - 28 85 »12 5. СПУСТИТЬСЯ ni климу, мятому из окна 12

86 С*14 Б. Спуститься » вврючнц С и записать я нее

значение из окна 14 8£ 0*11 7, Перейти î вервину D и записать в нее значение

из окна 11

83 X 8. Подняться на нужный уровень и перейти • X

84 (21,38) 9. Организовать цикл по группам окон документа

с номерами 21 - Зв 8S »25 18. Спуститься по ключу из окна 25

83 Y*6 11. Подняться, перейти а вериину Г и записать в

нее значение из окна 6 83 z'48 12. Перейти в вврвину Z и записать в нее

значение из окна 48

Программа загрузки.

Загрызенная база данник рис. б

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

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

Как уже отмечалось, любое преобразование базы данных можно представлять как смену состояния динамической базы данных под действием внешней информации: , ¿я/^ ). Однако, рассмат-

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

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

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

ции, не меняющие описания данных. Вводится набор элементарных операция включения и, соответственно, исключения. Операции включения таковы.

- добавление значения простого атрибута в кортеж: ®0(с)=с!

- добавление неопределенного кортежа с: С:

- добавление нового пустого экземпляра отношения г: /?:=Я+г0

- включение кортежа с в экземпляр отношения г: х(с,г):=1

- определение экземпляра отношения г как значения атрибута а в кортеже с: о(7(с):=г

Элементарные операции образуют универсальный набор, из которого могут быть построены более сложные действия, причем отношения формальной идентификации легко распространить по транзитивности на любую последовательность. Однако, хотелось бы иметь более емкие примитивы. В частности, естественным обобщением элементарных операций включения являются операции добавления данного, прежде всего включение кортежа и включение экземпляра отношения - независимого (5:=В+ьг ) или в качестве значения атрибута (£:=5+Дг -*с' ). Им соответствуют операции исключения кортежа В:=В-ОАТА(,с') и исключения экземпляра отношения 8:=В-0АТА(г! ).

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

зависят от семантики связей между данными в базе. Однако в ряде случаев правила исключения можно описать формальным образом. Вводятся множество IMS атрибутов замыкания и предикат за-

мыкания fermée,г), определенный на множестве С®/?. При выполнении операции исключения кортежа с' из базы данных В исключаются все элементы замыкания Сс1) множества {с'), состоящего из одного этого кортежа; при исключении экземпляра отношения г' -все элементы замыкания {/■'} множества {/•')•

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

Далее рассматривается преобразование описания данных при' помощи таких операций, как добавление А:=А+а йли удаление атрибута, введение sr:-sr+a или удаление sr:-sr-a атрибута из схемы отношения, добавление или исключение схемы отношения. Теперь становится возможным построить операции над отношениями, аналогичные реляционным: проецирование, объединение, прямое произведение, соединение. В случае иерархических баз данных правила выполнения этих операций формализуются однозначно.

Наиболее мощным из средств реструктуризации СУБД ИНЕС является язык запросов (ЯЗ). Язык имеет ряд черт, позволяющих говорить о нем, как о прообразе языка, в котором работа с данными во внешней памяти ведется обычными средствами, принятыми в универсальных алгоритмических языках. Перечислим эти черты.

- ЯЗ является языком высокого уровня, обладающим средства-

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

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

- Управление движением текущей точки в БД, принятое в ЯЗ. является прямым обобщением организации цикла в многоиндексном массиве.

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

В- СУБД ИНЕС имеется также средство реструктуризации, основанное на задании соответствия вершин. Это - программа переноса ветви базы, подчиненной вершине А, в вершину В, реализующая как операцию проекции и удаления из кортежей поддерева части атрибутов, не имеющих аналога в В, так и операцию слияния двух поддеревьев. Если учесть, что в ИНЕС можно произвольно добавлять или удалять вершины в схеме, не нарушая работы с данными, то эта программа является эффективным и весьма компактным по опа-

■ . -42-

санию средством реструктуризации в тех случаях, когда не нарушается взаимная подчиненность данных.

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

ЗАКЛЮЧЕНИЕ

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

Основные результаты диссертации состоят в следующем.

1. Разработаны теоретические основы инструментального подхода к конструиров анию сложных многофункциональных систем. Продемонстрировано конкретное применена е разработанных принципов конструирования на примере характерного представителя инструментальных састои - систем управления базами данных. Теоретические исследования, проведенные в диссертации, определяют' но-

В09 научное направление - развитие теории инструментальных систем и ее применение к созданию систем математического обеспечения. Основным практическим результатом является решение крупной народнохозяйственной задачи - разработка архитектуры СУБД ИНЕС.

2. Дано определение класса инструментальных систем в рамках общей теории систем. Сформулирован критерий целостности инструментальных систем. Показаны роли "индивидуального образа", критерия полноты охвата проблемной области, механизмов развития . системы. Установлена связь между принципом инструментальности и промышленным подходом.

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

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

5. Разработана обобщенная сетевая модель данных, включающая иерархическую и реляционную как частные случаи. Показано,

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

6. Разработана теория операций над данными, основанная на отношениях идентификации элементов; предложены операции реляционной алгебры для манипулирования элементами обобщенной модели данных; сформулированы требования к языку программирования, который являлся бы в то жо вромя языком манипулирования данными. В частности, показано, что расширение модели данных обычного алгоритмического языка (Р1.-1, Паскаль, Ада) понятием ключевого массива делает иерархическую или сетевую с выделенной иерархией модель данных СУБД (например, ИНЕС) эквивалентной модели данных языка программирования.

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

8. Рассмотрены основные проблемы создания математического обеспечения информационной технологии и разработана архитектура СУБД ИНЕС, функциональная полнота которой является одним из главных свойств.

СУБД ИНЕС внедрена и активно эксплуатируется в составе АСУ и информационных систем для решения широкого класса задач про-

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Арлазаров В.Л. Вопросы построения и использования инструментальных систем. - В сб.: Теория, методология и практика системных исследований. Всесоюзная конференция 29-31 января 1985 г. - Тезисы докладов, М., 1984 г., секция 1, с. 50-51.

2. Арлазаров В.Л., Диниц Е.А. Архитектура программной реализации ИНЕС. - В сб.¡Модели данных и системы баз данных. Труды совместного советско-американского семинара. - М.:Наука, 1979, с. 67-72.

3. Арлазаров В.Л., Иваницкий В.И., Фараджев И.А. и др. Многоуровневые языковые системы информационного обеспечения. Экономика и математические методы, т.XI. - М., 1975, #1, с. 63-77.

4. Арлазаров В.Л., Иваницкий В.И., Фараджев И.А. Языковые средства описания информации и процессов доступа к ней. - В сб.: Системы программного обеспечения решения задач оптимального планирования. - М..:ЦЭМИ, 1974, о. Í1-17.

5. Арлазаров В.Л.. Иваницкий В.И., Фараджев И.А. Многоуровневое языковое обеспечение информационного банка. - В сб. .-Материалы /У Всесоюзного совещания по проблемам управления. М.:ИАТ, 1974, с. 48-51.

6. Арлазаров В.Л., Вовченко Э.Л., Кирилличев A.M., Фараджев И.А. и др. Анализ проблемы построения больших информационных систем для решения задач управления АСУ ВУЗом. - В сб.¡Разработка и внедрение АСУ ВУЗ, М.:МИНХ и ГП им. Губкина,

-461976, с. 75-82.

7. Арлазаров В.Л., Вовченко Э.Л., Кирилличев A.M., Фарад-жев И.А. и др. Общие принципы построения банка данных для АСУ ВУЗ. В сб.: Разработка и внедрение АСУ ВУЗ, М. :МИНХ и ГП им. Губкина, 1976, с. 83-89.

8. Арлазаров В.Л., Филипьев H.A. Диалоговая система, обеспечивающая процесс планирования и принятия решений. - Автоматика и телемеханика, 1976, #3, с. 172-174.

9. Арлазаров В.Л., Вовченко Э.Л., Кирилличев A.M., Фарад-zoo И.А. и др. Язык описания логической структуры информации банка данных АСУ ВУЗом. В сб.'.Разработка и внедрение АСУ ВУЗ, М.:ШНХ и ГП им. Губкина, 1976, с. 89-101.

10. Арлазаров В.Л., Вовченко Э.Л., Кирилличев A.M., Фарад-жев И.А. и др. Внутронний и промежуточный язык банка данных. В сб.: Разработка и внодроние АСУ ВУЗ, М.:МИНХ и ГП им. Губкина, 1977, с. 109-119.

11. Арлазаров В.Л., Емельянов и др. Информационная система ИНЕС. - Автоматика и телемоханика, М. , 1979, #6, с. 109-121.

12. Арлазаров В.Л., Емельянов и др. Система ИНЕС. - Тезисы доклада на /~Я Всесоюзной конференции "Банки данных", Тбилиси, 1980.

13. Арлазаров В.Л., Розенфольд М.З. Один из подходов к автоматическому синтезу диалоговых систем. - В сб.:Диалог в автоматизированных системах, М.:МДНТП им. Дзержинского, 1981, с. 31-37.

14. Арлазаров В.Л.. Астахов А.Д., Брудно A.A., Кузнецова O.A. и др. Организация обменов с внешней памятью в СУБД ИНЕС. -Сб. трудов ВШП1СИ, #12, М.. 1983, с. 4-9.

15. Арлазаров В.Л., Емельянов II.Е. 0бп;ое описание системы

-47- ;

ИНЕС. - В сб.: Проблемы МЦНТИ, П. М.:МЦНТИ, 1982. с. 46-59

16. Арлазаров В.Л., Астахов А.Д. Опыт использования ИНЕС для межотраслевой АСУ. В сб: "Опыт использования баз данных ИНЕС". -М.:Знание, 1983.

17. Арлазаров В.Л., Лепошова Т.Г. Поисковая документная система на основе СУБД ИНЕС. - В сб.: Интеграция пакетов и баз данных САПР электротехнических устройств. - Таллин, 1982 с.79-85.

18. Арлазаров В.Л., Емельянов Н.Е. Теоретический анализ распространенных концепций баз данных. - В сб.:Труды 3 Всесоюзной конференции "Банки данных", Таллин, 1985, с. 191-201.

19. Арлазаров В.Л. Элементы теории инструментальных систем. - В сб.: Системные исследования. Методологические проблемы. Ежегодник 1986. - М., Наука, 1987, с.74-101.

20. Арлазаров В.Л., Диниц Е.А. К теории инструментальных систем. - В сб.: Системные исследования. Методологические проблемы. Ежегодник. М.:Наука, 1983, с. 279-292

21. Арлазаров В.Л. СУБД как инструментальная система. М.:ВНИИСИ, 1985, 32 с.

22. Арлазаров В.Л., Астахов А.Д. Технология ведения баз данных ИНЕС в межотраслевой АСУ. - В сб.:Тезисы докладов 2 Всесоюзной конференции "Банки данных". Киев, 1983. Секция 4, с.24-27.