11. Уровни представления информации  (синтаксический, семантический, прагматический)

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

Единицей информации называется набор символов, которому придается определенный смысл. Это понятие в основном относится к базе данных, хранящей форматированные сообщения.
Если в сообщении «На склад № 2 01.02.98 поступили генераторы от завода «Динамо» в количестве 50 шт. по цене 200 руб.» названия параметров фиксированы, то набор символов «склад № 2, з-д «Динамо», генератор, 01.02.98,200 руб., 50 шт.» является единицей информации. «01.02.98» также является единицей информации.
Минимально необходимы две единицы информации - атрибут и составная единица информации (СЕИ).
Атрибутом называется информационное отображение отдельного свойства некоторого объекта, процесса или явления.
Любое сообщение записывается в форматированном виде как указание свойств (параметров) предметов, о которых мы говорим. Поэтому информационное отображение любого явления представляет собой набор соответствующим образом подобранных атрибутов.
Составная единица информации представляет собой набор из атрибутов и, возможно, других СЕИ.
Простейшими СЕИ являются таблицы, подобные приведенной выше. СЕИ позволяет создавать произвольные комбинации из атрибутов.
База данных ЭИС хранится в запоминающих устройствах вычислительной системы (ЭВМ). Хранимые представления данных очень часто не соответствуют первоначальному множеству форматированных сообщений. Однако сейчас при рассмотрении БД будем считать, что сообщения хранятся в виде таблиц.
Концептуальная схема (от слова concept - понятие) представляет собой описание структуры всех единиц информации, хранящихся в БД. Под структурой понимается вхождение одних единиц информации в состав других единиц информации.
В рамках нашего примера можно говорить о двух единицах информации - параметре (атрибуте) и таблице (СЕИ).
Предположим, что таблица Т соответствует всей базе данных. В концептуальной схеме должно быть указано, что БД состоит из Т, а Т содержит параметры Получатель, Отправитель, Изделие, Дата, Цена, Количество. Более содержательное представление о концептуальной схеме приводится в гл. 2 книги.
Информационный процессор - это механизм, который в ответ на получение команды выполняет операции с БД и концептуальной схемой. Информационный процессор состоит из вычислительной системы и системы управления базой данных - СУБД.
Под вычислительной системой будем понимать серийно выпускаемую электронно-вычислительную машину (ЭВМ) либо несколько ЭВМ, соединенных каналами связи в вычислительную сеть.
ЭВМ состоит из ряда устройств, каждое из которых способно выполнять свойственные ему операции.
Оперативное запоминающее устройство (ОЗУ) используется для хранения программ и данных. Скорость чтения и записи для ОЗУ, как правило, одинаковы, ОЗУ является наиболее быстродействующим устройством ЭВМ.
Процессор выполняет команды, находящиеся в программе. Выполнение команды обычно предполагает обращение к ОЗУ.
ЭВМ может содержать любое число внешних устройств, чаще всего это внешние запоминающие устройства и устройства печати информации.
База данных предполагает централизованное управление данными, что обеспечивает ряд преимуществ:
•сокращение избыточности хранимых данных благодаря однократному хранению каждого сообщения в базе данных,
•совместное использование хранимых данных всеми пользователями ЭИС,
•стандартизацию представления данных, упрощающую проблемы эксплуатации БД и обмена данными между ЭИС,
•обеспечение процедур проверки достоверности информации и процедур ограничения доступа к данным,
•совмещение требований к использованию БД со стороны различных пользователей ЭИС.
Системой управления базой данных называется комплекс программ, обеспечивающий централизованное хранение, накопление, модификацию и выдачу данных, входящих в БД.
Предполагается, что в управлении базой данных принимает участие специальное должностное лицо - администратор базы данных.
13. Потребительские свойства технико-экономической информации

К потребительским свойствам информации относят: ценность, старение, достоверность, читабельность, оперативность, стоимость и др. В этой связи отмечаются такие свойства информации, как: надёжность, точность, полнота, достоверность, достаточность, оперативность и др. Среди требований, предъявляемых к информации, с точки зрения передачи и использования, выделяют следующие: адресность, актуальность, возможность кодирования, высокая скорость сбора, обработки и передачи, достаточность, достоверность, многократность использования, правовая корректность, полнота, своевременность. Рассмотрим все эти свойства более подробно. Информации обобщённо присущи атрибутивные, прагматические и динамические свойства. Каждая из этих категорий содержит соответствующие свойства информации. 1. Атрибутивные свойства - свойства, без которых информация не существует. К данной категории свойств относятся следующие свойства информации: • неотрывность информации от физического носителя и языковая природа информации. Одно из важнейших направлений информатики как науки является изучение особенностей различных носителей и языков информации, разработка новых, более совершенных и современных. Хотя информация неотрывна от физического носителя и имеет языковую природу, она не связана жестко ни с конкретным
языком, ни с конкретным носителем; • дискретность. Содержащиеся в информации сведения, сообщения, данные и знания - дискретны, т.е. характеризуют отдельные фактические данные, закономерности и свойства изучаемых объектов,
распространяемые в виде различных сообщений, состоящих из линии, составного цвета, буквы, цифры, символа или знака; • непрерывность. Информация имеет свойство сливаться с ранее зафиксированной и накопленной, тем самым, способствуя поступательному развитию и накоплению.
14. Структурные единицы информации (реквизиты, составные единицы)

Существуют две основные единицы информации - атрибут и составная единица информации. Атрибут соответствует понятию переменной в языках программирования и понятию реквизита в бухгалтерском учете.
Атрибут характеризуется именем и значением. Именем атрибута называется его условное обозначение в процессах обработки данных.
Значением атрибута называется величина, характеризующая некоторое свойство объекта, явления, процесса в конкретных обстоятельствах. Все допустимые значения атрибута образуют множество, называемое доменом этого атрибута.
Формально атрибут с именем Х представляет собой пару (X,z), где z - элемент Z. Множество Z называется доменом значений (областью определения атрибута X), величина z является значением атрибута Х в заданный момент времени.
Определение домена предполагает указание его имени и списка значений. Если число значений в домене невелико, то их список можно указать при объявлении данных в программе. Например, в языке программирования Паскаль это выглядит как
type
day=1..31;
month = (январь, февраль, март, апрель, май, июнь, июль, август, сентябрь, октябрь, ноябрь, декабрь);
year = 1900..1999;
{в описании типа атрибутов перечисляются допустимые значения атрибутов День, Месяц и Год соответственно}
Зачастую невозможно перечислить все элементы домена, поэтому для домена указываются тип и длина значения. Наиболее употребительны текстовые (символьные), числовые, логические значения, а также значения дат и другие специальные типы значений.
Пример
Домен фамилий - FАМ. Перечислить фамилии невозможно, поэтому ограничим FAM значениями текстового типа длиной до 20 символов. Для языка Паскаль получим:
var FAM:string[20];
В домене, определенном таким образом, могут оказаться элементы, заведомо не являющиеся фамилией, например ''ММММ'', но такие случаи при определении домена не учитываются.
Для ряда доменов множество входящих в них значений задается с помощью перечисления допустимых значений. Если в домене необходимо перечислить обозначения объектов из некоторого класса, то разрабатывается классификатор, содержащий условные обозначения (коды) отдельных объектов и классов, к которым эти объекты отнесены.
Рассмотрим простейшие системы классификации и кодирования, применяемые для обозначения объектов в базе данных вместо их полных названий.
В первую очередь, если классификация объектов вообще не требуется, производится их нумерация, и кодом каждого объекта служит его порядковый номер. Такая система кодирования называется порядковой.
Если все множество объектов классифицируется по одному признаку, то коды объектов целесообразно разделить на несколько частей (серий) по количеству значений этого признака и в пределах каждой серии использовать последовательные номера.
Когда используется несколько классификационных признаков и их взаимная подчиненность соответствует выделению классов объектов, подклассов внутри каждого класса и т.д., удобно использовать разрядную систему кодирования.
В качестве примера рассмотрим различные системы кодирования значений атрибута Код студента. Порядковый код студента - это просто его номер в списке всех студентов. Предположим, что необходимо различать студентов-дневников, вечерников и заочников с использованием серийной системы кодирования. Для этого последовательные номера от 1 до 5999 будем использовать при кодировании дневников, номера от 6000 до 7999 - при кодировании вечерников, от 8000 до 9999 - при кодировании заочников. Если в этих же условиях применить разрядный код, то первый знак кода будет принимать три значения (1 -дневное отделение, 2 - вечернее, 3 - заочное), а следующие 4 знака отводятся для нумерации студентов каждого отделения. В разрядном коде можно учесть больше признаков, например, первый знак - код отделения, второй - код факультета, третий - код курса, четвертый - код группы, пятый и шестой - порядковый номер студента в группе. Обратите внимание, что, увеличивая число различимых признаков в коде, мы вынуждены увеличивать и длину значения атрибута Код студента.
Разрядная система кодирования применяется для кодирования объектов, определяемых несколькими соподчиненными признаками. Кодируемые объекты систематизируются по классификационным признакам на каждой ступени классификации. Каждому признаку классификации отводится определенное число разрядов, в пределах которого кодирование начинается с единицы. Классификационные группировки по младшим признакам кодируются в зависимости от кода более старшего признака.
Если значения нескольких атрибутов определены на одном и том же домене, то такие атрибуты называются ролевыми.
На домене FAM могут быть определены атрибуты с именами: Студент, Преподаватель, Автор. Все это ролевые атрибуты.
Атрибуты Фамилия рабочего и Табельный номер рабочего неролевые, хотя описывают одних и тех же людей.
Домен значений, как правило, не хранится в базе данных как самостоятельный информационный объект. Однако среди ролевых атрибутов домена в базе данных, безусловно, существует атрибут с наиболее полным перечнем значений, и этот атрибут необходимо использовать для контроля достоверности вновь вводимой информации. Например, на предприятии наиболее полный список сотрудников должен присутствовать в базе данных отдела кадров.
Составной единицей информации (СЕИ) называется набор из атрибутов и, возможно, других СЕИ. Определение СЕИ построено рекурсивно (т. е. в определении понятия участвует само понятие), но противоречия здесь нет, поскольку «другие СЕИ» когда-нибудь будут состоять только из атрибутов (ввиду конечности сообщений).
Атрибут и отношение образуют минимально возможный набор единиц информации. На практике удобно использовать большее число единиц информации, как это показано, например, в табл. 1.2. Следует отметить, что БД в целом также является единицей информации. Если рассматривать единицы информации как информационные объекты, то можно говорить об их свойствах, как это делается в табл. 1.2. В то же время единицы информации - это нефизические объекты, так как они не занимают место в пространстве.
Множество атрибутов объединяется в одну СЕИ по следующим принципам:
• соответствующие атрибуты описывают один и тот же факт или экономический процесс,
• значения атрибутов, входящих в СЕИ, возникают одновременно, связаны логическими или арифметическими соотношениями.
Простейшими характеристиками СЕИ являются имя, структура и значение. Имя СЕИ - это ее условное обозначение в процессах обработки информации. Структурой СЕИ называется вхождение одних единиц информации в состав других единиц информации.
Аппарат СЕИ рассчитан на описание структуры экономических документов. Документом называется материальный носитель информации (обычно бланк бумаги), содержащий оформленные в установленном порядке сообщения и имеющий юридическую силу.
Существует сравнительно много способов описания структуры СЕИ. Для описания, не зависимого от конкретных языков программирования и СУБД, достаточно указывать после имени СЕИ список имен входящих в Нее атрибутов и СЕИ. Будем помещать этот список в круглые скобки, а имена внутри скобок перечислять через запятую. Имя СЕИ может сопровождаться размерностью, т.е. указанием на количество одинаковых по структуре значений этой СЕИ. Размерность, если она не равна 1, указывается в скобках после имени СЕИ.
Рассмотрим в качестве примера документа «Приходный ордер» с сокращенным составом атрибутов (рис. 1.5). СЕИ приходного ордера, названная Прих, содержит атрибуты Дата (дата поступления материалов). Пост (код поставщика материалов). Склад и таблицу, также включающую ряд атрибутов. Эта таблица является «другой» СЕИ в составе СЕИ Прих и названа Табл. Обратите внимание, что в экономических документах таблицы не имеют названий, названия всех элементов документа требуются при его машинной обработке.
Определение значения СЕИ можно дать, опираясь на значения единиц информации, входящих в структуру СЕИ. Значение атрибута, входящего в СЕИ, определяется непосредственно. Значение СЕИ, входящей в другую СЕИ, можно определить рекурсивно, однако надо учесть размерность СЕИ. Кроме того, для множества значений СЕИ в составе другой СЕИ необходимо самостоятельное понятие. Назовем собранием СЕИ множество ее значений в составе СЕИ более высокого уровня. Количество значений в собрании СЕИ равно ее размерности.
Значением СЕИ называется набор значений непосредственно входящих в нее атрибутов и набор собраний непосредственно входящих в нее СЕИ. Одно значение СЕИ приходного ордера содержит по одному значению атрибутов Дата, Пост, Склад и собрание СЕИ Табл. Собрание Табл включает в себя три значения, в каждое значение Табл входит по одному значению атрибутов Ннм, Кво-док, Кво-пр, Цена и Сумма. Всего в нашем примере определены два значения СЕИ Прих.
Одно значение СЕИ при хранении ее в памяти ЭВМ часто называется записью.
Все языки программирования содержат средства описания структуры СЕИ.
14. Структурные единицы информации (показатели)

При анализе экономических документов ставится задача разделения документа на элементарные осмысленные фрагменты, называемые показателями. Это позволяет установить смысловые взаимосвязи между различными документами, обеспечить одинаковое понимание всеми пользователями применяемых единиц информации и их единое обозначение, использовать полученные результаты для определения структуры базы данных.
Показатель представляет собой полное описание количественного параметра, характеризующего некоторый объект или процесс. Соответствующее описание произвольного свойства (необязательно количественного) называется атомарным фактом и рассматривается в п. 4.1.
Чтобы точнее характеризовать атрибуты, образующие показатель, необходимо отметить существенные различия свойств, которые отображаются атрибутами. Материальные процессы, как известно, имеют качественную характеристику и количественную характеристику. Соответственно и атрибуты должны разделяться на два класса, которые называются «атрибуты-признаки» и «атрибуты-основания».
Атрибут-признак представляет собой информационное отображение качественного свойства некоторого объекта, предмета, процесса, а основание является отображением их количественного свойства.
В состав показателя должны входить один атрибут-основание и несколько атрибутов-признаков, однозначно характеризующих условия существования основания.
Как единица информации показатель является разновидностью СЕИ. Схематично структура показателя П представляется выражением
П(P1,P2,...,Pk,Q),
где P1, P2,...,Pk - атрибуты-признаки, Q - атрибут-основание.
Если представить себе показатель с двумя, например, атрибутами-основаниями, то его можно разделить на две части, в каждой из которых будет один атрибут-основание и характеризующие его признаки. Полученные части содержат меньше атрибутов и поэтому соответствуют определению показателя.
Таким образом, в показателях отображаются количественные свойства объектов и процессов. Вместе с тем существуют документы, не содержащие атрибутов-оснований, например анкеты кадрового учета, сведения о структуре подразделений предприятия и т. д. Следовательно, не вся экономическая информация может быть представлена в форме показателей.
Минимальный набор атрибутов показателя должен содержать:
• атрибуты, отображающие идентификаторы объектов,
• атрибуты, отображающие признак времени,
• атрибут, отображающий некоторое количественное свойство объекта или взаимодействия.
Для установления признаков и оснований в конкретных документах можно использовать следующие закономерности:
• Если значение атрибута является исходным данным или результатом арифметической операции - это основание.
• Если значение текстовое - это признак.
• Если атрибут обозначает предмет - это признак.
• Если атрибут в некотором показателе является признаком (основанием), - он будет играть эту роль и в других показателях.
• Если показатели описывают сходные процессы - их признанные части совпадают.
• Если основание показателя вычисляется по значениям других оснований, то набор признаков такого показателя есть объединение признаков, связанных с этими основаниями.
Критерием качества создания базы данных может служить минимальная избыточность хранимой информации. Обычно минимальная избыточность выражается принципом: каждое сообщение хранится в БД один раз. Соблюдение этого принципа дает ряд преимуществ:
• сокращается объем памяти ЭВМ, требуемой для хранения базы данных,
• сокращается трудоемкость ввода данных в ЭВМ и упрощаются проблемы контроля достоверности вводимой информации,
• упрощаются алгоритмы корректировки данных, так как корректировка сообщения может быть проведена за одно обращение к базе данных.
Использование аппарата экономических показателей позволяет создать структуру БД с минимальной избыточностью, если сначала расчленить все сведения, циркулирующие в ЭИС, на показатели, а потом объединить атрибуты родственных показателей по принципу: в один файл включается группа экономических показателей с одинаковым составом атрибутов-признаков.
16. Файловые системы

Информационное обеспечение ЭИС первого типа построено в виде файловых систем. В современных ЭВМ операционная система берет на себя распределение внешней памяти, отображение имен файлов в соответствующие адреса во внешней памяти и обеспечение доступа
к данным. Программное обеспечение ЭИС напрямую использует функции ОС для работы с файлами. Файловые системы обычно обеспечивают хранение слабо структурированной информации, оставляя дальнейшую структуризацию прикладным программам. В таких системах сложно решить проблемы согласования данных в разных файлах, коллективного доступа к данным, модификации структуры данных.
Банком данных (рис.1.5) называют систему специальным образом организованных баз данных, программных, технических, языковых и организационно - методических средств, предназначенных для обеспечения централизованного накопления и коллективного многоцелевого использования данных.
Файловая система - логическая организация данных на носителе информации, определяющая логическую и физическую структуру файла, идентификацию и атрибуты файла, а также алгоритмы распределения файлов по пространству носителя и организации файлов в каталоги.
Также часть операционной системы, входящая в ядро, или отдельным модулем, обеспечивающая запись и чтение и другие операции над файлами на внешних носителях, иногда называется хэндлером файловой системы.
По способу идентификации данных различают:
   1. Тривиальные ФС, определяющие хранение файлов в единственной «куче», корневом каталоге носителя. Эти системы практически вымерли, и замещены на иерархические. Из применяющихся можно назвать TR-DOS на компьютере Sinclair ZX-Spectrum.
   2. Иерархические ФС, обеспечивающие хранение файлов в древовидной структуре каталогов. Являются самым распространёным видом ФС. В настольных системах начиная с 1990-х применяются практически только они.
   3. Реляционные, ассоциативные, (?) прочие ФС, обеспечивающие другие методы идентификации данных. Применяются крайне редко по причине узкой области применения.
Файловые системы различаются по устойчивости к сбоям:
    * Неустойчивые к сбоям как правило представляю собой тривиальные структуры, полная согласованность которых обеспечивается во время работы не всегда. При сбое системы в моменты несогласованности возможна потеря данных, или даже разрушение всей ФС целиком. Восстановление часто требует длительных и нетривиальных действий.
    * Устойчивые к сбоям системы представляют полностью согласованные структуры в любой момент времени существования файловой системы, таким образом, отстутствуют моменты, когда сбой может привестик потерям данных или разрушению ФС. Как правило это журналируемые ФС, дублирующие все изменения структуры в специальной области — журнале, таким образом, в случае сбоя имеющие возможность завершить незавершённую операцию или откратить состояние ФС до сбоя.
Разделение прав доступа
Разделение прав доступа существует практически во всех файловых системах, использующихся на многопользовательских ОС. Как правило это возможность установить отдельные права доступа для владельца, группы владельца и остальных пользователей на чтение, запись и исполнение. Такая схема обычна для Posix-совместимых ОС.
В файловой системе NTFS возможна более гибкая настройка прав доступа (для каждого пользователя).
Шифрование
Шифрование — защита информации от считывания непосредственно с носителя, в обход ограничений прав доступа доступно в некоторых файловых системах. У NTFS шифрование — это одна из возможностей, пользователь может выбрать файлы и каталоги, которые он хочет зашифорвать. Некоторые файловые системы специально приспособлены для шифрования данных, это например CryptoFS, или PGPDisk.
Сжатие
Сжатие файлов может обеспечиваться как специальной фаловой системой для этого, так и дополнительной возможностью обычных ФС. Из некогда популярных можно упомянуть DriveSpace, систему, создававшую виртуальный сжатый диск под MS-DOS. Также, сжатие — одна из возможностей, предлагаемых NTFS. При этом файлы с точки зрения пользователя и приложений ничем не отличаются от несжатых, единственное различие — разница в скорости доступа (причём разница неоднозначная, с одной стороны требуется дополнительное процессорное время на сжатие/расжатие, с другой стороны есть выигрыш во времени считывания с носителя) и занимаемом пространстве.
Циклические файлы
Возможность создать циклически перезаписываемый файл (англ. rollover) — особенность некоторых файловых систем для AmigaOS. При дописывании в конец циклического файла он не увеличивается в размере, а теряет начало. Такая возможность предоставляет унифицированный механизм для ведения журналов (логов) в приложениях.
Восстановление удалённых файлов
Во многих файловых системах при удалении файла он не исчезает бесследно, а только получает отметку «удалён», что означает, что пространство, которое было занято файлом может быть повторно использовано для хранения другой информации. Как правило такие файлы, если поверх них ничего не записано можно восстановить специальными средствами.
Некоторые файловые системы (например Amiga SmartFileSystem) перемещают удалённые файлы в специальный каталог («:.recycled»), из которого их потом можно восстановить стандартным способом — копированием или перемещением. Полное же удаление файла производится лишь при нехватке места или при превышении лимитов.
Потоки
Возможность создания «потоков» файла — специальная возможность файловой системы NTFS. Поток — отдельный массив данных, связанный с файлом, но с доступом через специальный суффикс в пути к файлу. В этом потоки похожи на отдельные файлы, но отличаются тем, что копируются и удаляются вместе с основным потоком, а также имеют общие атрибуты.
17. Базы данных

В отличие от файловых систем, структура базы данных меньше зависит от прикладных программ, а все функции по работе с БД сосредоточены в специальном компоненте – системе управления базами данных (СУБД), которая играет центральную роль в функционировании банка данных, так как обеспечивает связь прикладных программ и пользователей с данными. Сведения о структуре БД сосредоточены в словаре-справочнике (репозитории) АБД, этот вид информации называется метаинформацией. В состав метаинформации входит семантическая информация, физические характеристики данных и информация об их использовании. С помощью словарей данных автоматизируется процесс использования метаинформации в ЭИС.
Интеллектуальный банк данных (ИБД) (рис.1.6) - это сравнительно новый способ построения ЭИС, при котором информация о предметной области условно делится между двумя базами.
База данных содержит сведения о количественных и качественных характеристиках конкретных объектов. База знаний содержит сведения о закономерностях в ПО, позволяющие выводить новые факты из имеющихся в БД; метаинформацию; сведения о структуре предметной области;
сведения, обеспечивающие понимание запроса и синтез ответа.
Диалоговый процессор предназначен для понимания смысла запроса и его перевода в термины знаний, заложенных в БЗ. Планировщик преобразует полученный запрос в рабочую программу, составляя ее из модулей, имеющихся в БЗ. Подсистема пополнения знаний позволяет ЭИС обучаться.
Если в традиционном банке данных знания о предметной области заложены программистом в каждую прикладную программу, а также в структуру БД, то в интеллектуальном банке данных они хранятся в базе знаний и отделены от прикладных программ. В отличие от данных, знания активны: на их основе формируются цели и выбираются способы их достижения. Например, ИБД в системе складского учета может автоматически реагировать на такое событие, как уменьшение количества деталей на складе до критической нормы, при этом ИБД без участия пользователя генерирует документы для заказа этих деталей и отправляет их по электронной почте поставщику.
Другое характерное отличие знаний от данных - связность, причем знания отражают как структурные взаимосвязи между объектами предметной области, так и вызванные конкретными бизнес - процессами, например такие связи, как “происходит одновременно”, “следует из...”,
"если - то" и др.
Наконец, существенную роль в ИБД играет форма представления информации для пользователя: она должна быть как можно ближе к естественным для человека способам обмена данными (профессиональный естественный язык, речевой ввод / вывод, графическая форма).
В настоящее время в корпоративных базах данных накоплены гигантские объемы информации, однако она недостаточно эффективно используется в процессе управления бизнесом, поэтому бурно развивается новая форма построения ЭИС - склады (хранилища) данных.

База данных (БД) в строгом смысле слова представляет собой совокупность взаимосвязанных файлов данных определенной организации. БД, как правило, включает целый ряд файлов, но может состоять и из единственного файла. Данные, составляющие БД, отражают характеристики объектов и их отношений в соответствующей прикладной области. Каждый файл, входящий в БД, содержит определенное число записей (изменяемое в процессе функционирования БД), отражающих ту или иную сторону (это определение таблицы а не файла БД) предметной области, на которую ориентирована БД. Как правило, файлы БД содержат большое число однотипных записей(совершенно не правило. Думаю лучше ввести понятие таблица или набор записей). Записи, в свою очередь, состоят из полей, представляющих определенные типы информации об объектах. Поле является наименьшей информационной единицей, непосредственно доступной в записи. Если файл_1 БД (рис. 1) содержит п однотипных записей (имеющих одинаковую структуру полей и их смысловую нагрузку),то j-запись (1<j<n) файла состоит из фиксированного набора (кортежа полей А1—Ак), каждое из которых содержит в общем случае различного типа информацию. При наличии БД прикладные программы могут использовать ее информацию (записи и их поля) для решения конкретных задач в прикладной области, на которую ориентирована данная БД.
TODO: таблица Файловая организация баз данных
Пользователями БД являются четыре основные категории потребителей ее информации и/или поставщиков информации для нее: (1) конечные пользователи, (2) программисты и системные аналитики, (3) персонал поддержки БД в актуальном состоянии и (4) администратор БД. Хорошо спроектированные системы управления БД (СУБД), используют развитые графические интерфейсы и поддерживают системы отчетов, отвечающие специфике пользователей указанных четырех категорий. В этом случае персонал поддержки БД и конечные пользователи могут легко осваивать и использовать СУБД для обеспечения своих потребностей без какой-либо специальной подготовки, т.е. специфика функционирования данных систем скрыта от пользователя. Более того, хорошо спроектированные СУБД предоставляют опытному пользователю средства для создания собственных БД-приложений, не требуя от него специальной программистской подготовки. Конечным пользователям для обеспечения доступа к информации БД предоставляется графический интерфейс, как правило, в виде системы окон с функциональными меню, позволяющими легко получать необходимую информацию на экран и/или принтер в виде удобно оформленных отчетов.
Программисты и системные аналитики используют СУБД совершенно в ином качестве, обеспечивая разработку новых БД-приложений, поддерживая и модифицируя (при необходимости) уже существующие. Для данной группы пользователей СУБД требуются средства, обеспечивающие указанные функции (создание, откладка, редактирование и т.д.). Пользователи третьей категории нуждаются в интерфейсе, как правило, графическом для обеспечения задач поддержания БД в актуальном состоянии. Эти пользователи состоят в штатах подразделений функциональных и/или обработки информации, обеспечивающих прикладную область, и отвечают за актуальное состояние соответствующей ей БД (контроль текущего состояния, удаление устаревшей информации, добавление новой и т.д.). Программисты выполняют своего рода посреднические функции между БД и конечными пользователями. И если на первых этапах развития БД-технологии они составляли весьма многочисленную группу пользователей, то в процессе развития СУБД и, прежде всего, массового использования ПК эта категория сходит на нет. Особую и ответственную роль выполняет администратор, отвечающий как за актуальность находящейся в БД информации, так и за корректность функционирования и использования БД и СУБД.
В случае больших БД может быть достаточно много конечных пользователей, ряд программистов и несколько администраторов БД; в случае небольших БД (что особенно характерно для ПК) все эти функции могут обеспечиваться одним человеком. Важные функции выполняет администратор БД, отвечающий за выработку требований к БД, ее проектирование, реализацию, эффективное использование и сопровождение. Необходимость в таком специалисте вытекает из принципа независимости данных, а также диктуется важностью БД в деятельности организаций и более крупных объединений — поставщиков и потребителей информации БД. Администратор БД взаимодействует с пользователями в определении требований к базе в процессе выработки требований к системе в целом, пользуется языков описания данных для определения БД в процессе проектирования системы, взаимодействует с программистами, которые создают ПС использующее доступ к БД, отвечает за загрузку БД информацией в процессе реализации системы, контролирует работоспособность БД, используя соответствующие программные и аппаратные средства, и определяет, когда следует реорганизовывать данные в базе или начать работы по созданию новой, более совершенной БД. В целом функции администратора БД сводятся к поддержанию целостности БД, необходимого уровня защиты ее данных и эффективности. Среди его наиболее важных обязанностей — согласование конфликтующих требований, которое требуется достаточно часто, ибо БД обслуживает, как правило, целый ряд различных прикладных процессов.
Как уже отмечалось, БД представляет собой совокупность логически взаимосвязанных файлов данных определенной организации; для определения и обращения к такой файловой совокупности используют средства системы управления БД (СУБД). СУБД представляет собой совокупность лингвистических и программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями. Тогда как под системой БД понимается СУБД с наполненной соответствующей информацией БД, управляемой ее средствами. Это означает, во-первых, что совокупность файлов БД определяется посредством схемы, не зависящей от программ, которые к ней обращаются, и, во-вторых, что она реализована на основе ВП прямого доступа. Использование СУБД обеспечивает лучшее управление данными, более совершенную организацию файлов и более простое обращение к ним по сравнению с обычными способами хранения информации. Вследствие более совершенных механизмов доступа БД, как правило, имеют более сложную организацию, чем обычные файлы, объединяя данные, ранее хранящиеся во многих отдельных файлах. Размер и сложность не являются определяющими характеристиками БД — наличие СУБД для ПК и даже в среде ряда пакетов (например, табличных процессоров, интегрированных и др.) приводит к созданию большого числа относительно простых и небольших БД, достоинством которых (при наличии соответствующих СУБД) являются простота определения и доступа к данным. Под банком данных (БнД) понимается система лингвистических, программных, аппаратных и организационных средств, основанная на БД-технологии и предназначенная для централизованного накопления и коллективного использования данных в той или иной прикладной области. Тогда как система обработки информации (СОИ) реализует автоматизированный сбор, обработку и хранение информации, включая соответствующие лингвистические, программные, аппаратные, организационные средства и обслуживающий их персонал.
Под целостностью БД понимается актуальное состояние ее данных, отражающих состояние некоторой реальной прикладной области и подчиняющихся правилам непротиворечивости. Под языком БД понимается один или совокупность языков, обеспечивающих описание данных, манипулирование с данными. Конкретный язык БД всегда ассоциируется с конкретной СУБД. СУБД представляет собой средства обработки на языке базы данных, позволяющие обрабатывать обращения к БД, поступающие от прикладных программ и/или конечных пользователей, и поддерживать целостность БД. Таким образом, СУБД имеет свойства, характерные как для компиляторов, так и для ОС, однако по сравнению с первыми обеспечивается более высокий уровень абстрагирования, что оказывается очень полезным как для программистов, так и для конечных пользователей.
Каждая БнД содержит и обрабатывает информацию из конкретной прикладной области, представляющей интерес для определенных приложений. Описание предметной области без акцента на ее последующие БнД-реализации определяет инфологическую модель предметной области (рис. 2). Инфологическая модель является исходной для построения даталогической модели БД и служит промежуточной моделью для специалистов предметной области (для которой создается БнД) и администратора БД в процессе проектирования и разработки конкретной БнД.
Под даталогической понимается модель, отражающая логические взаимосвязи между элементами данных безотносительно их содержания и физической организации. При этом даталогическая модель разрабатывается с учетом конкретной реализации СУБД, также с учетом специфики конкретной предметной области на основе ее инфологической модели. Для конкретной реализации даталогической модели проектируется физическая модель (рис. 2), oтображающая первую на конкретные программные и аппаратные средства (ОС, внешняя память, работа с данными на физическом уровне и т.д.). Наполненная конкретной информацией физическая модель и составляет собственно БД. Система, обеспечивающая cоответствующее совместное функционирование указанных компонентов и составляет суть конкретной СУБД.
Современные СУБД допускают целый ряд классификаций в зависимости от уровня их рассмотрения (в целом либо по совокупности их функциональных характеристик): по интерфейсу с пользователем в зависимости от поддерживаемых моделей, по назначению и режиму функционирования, по способу обработки информации и т.д. Мы кратко остановимся на моделях даталогического уровня, который берется за основу большинства современных классификаций СУБД.
Обычно различают три класса СУБД, обеспечивающих работу иерархических, сетевых и реляционных моделей. Однако различия между этими классами постепенно стираются, причем, видимо, будут появляться другие классы, что вызывается прежде всего интенсивными работами в области баз знаний (БЗ) и объектно-ориентированной инфотехнологией, о которой будет идти речь ниже. Поэтому традиционной классификацией пользуются все реже, но мы пока будем придерживаться именно ее, как наиболее устоявшуюся. Каждая из указанных моделей обладает характеристиками, делающими ее наиболее удобной для конкретных приложений. Одно из основных различий этих моделей состоит в том, что для иерархических и сетевых СУБД их структура часто не может быть изменена после ввода данных, тогда как для реляционных СУБД структура может изменяться в любое время. С другой стороны, для больших БД, структура которых остается длительное время неизменной, и постоянно работающих с ними приложений с интенсивными потоками запросов на БД-обслуживание именно иерархические и сетевые СУБД могут оказаться наиболее эффективными решениями, ибо они могут обеспечивать более быстрый доступ к информации БД, чем реляционные СУБД.

18. Хранилище данных

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

Хранилище данных (англ. Data Warehouse) — очень большая предметно-ориентированная информационная корпоративная база данных, специально разработанная и предназначенная для подготовки отчётов, анализа бизнес-процессов с целью поддержки принятия решений в организации. Строится на базе клиент-серверной архитектуры, реляционной СУБД и утилит поддержки принятия решений. Данные, поступающие в хранилище данных, становятся доступны только для чтения. Данные из промышленной OLTP-системы копируются в хранилище данных таким образом, чтобы построение отчётов и OLAP-анализ не использовал ресурсы промышленной системы и не нарушал её стабильность. Данные загружаются в хранилище с определённой периодичностью, поэтому актуальность данных несколько отстает от OLTP-системы.
Принципы организации хранилища:
   1. Проблемно-предметная ориентация. Данные объединяются в категории и хранятся в соответствии с областями, которые они описывают, а не с приложениями, которые они используют.
   2. Интегрированность. Данные объединены так, чтобы они удовлетворяли всем требованиям предприятия в целом, а не единственной функции бизнеса.
   3. Некорректируемость. Данные в хранилище данных не создаются: т.е. поступают из внешних источников, не корректируются и не удаляются.
   4. Зависимость от времени. Данные в хранилище точны и корректны только в том случае, когда они привязаны к некоторому промежутку или моменту времени
Существуют два архитектурных направления – нормализованные хранилища данных и размерностные хранилища.
В нормализованных хранилищах, данные находятся в предметно ориентированных таблицах третьей нормальной формы – витрины данных. Нормализованные хранилища характеризуются как простые в создании и управлении, недостатки нормализованных хранилищ – большое количество таблиц как следствие нормализации, из-за чего для получения какой-либо информации нужно делать выборку из многих таблиц одновременно, что приводит к ухудшению производительности системы.
Размерностные хранилища используют схему "звезда" или "снежинка". При этом в центре звезды находятся данные (Таблица фактов), а размерности образуют лучи звезды. Различные таблицы фактов совместно используют таблицы размерностей, что значительно облегчает операции объединения данных из нескольких предметных таблиц фактов (Пример – факты продаж и поставок товара). Таблицы данных и соответствующие размерности образуют архитектуру "ШИНА". Размерности часто создаются в третьей нормальной форме (медленно изменяющиеся размерности), для протоколирования изменения в размерностях. Основным достоинством размерностных хранилищ является простота и понятность для разработчиков и пользователей, также, благодаря более эффективному хранению данных и формализованным размерностям, облегчается и ускоряется доступ к данным, особенно при сложных анализах. Основным недостатком является более сложные процедуры подготовки и загрузки данных, а также управление и изменение размерностей данных.
Источниками данных могут быть:
   1. Традиционные системы регистрации операций (БД)
   2. Отдельные документы
   3. Наборы данных
Источники данных классифицируются:
   1. Территориальное и административное размещение.
   2. Степень достоверности.
   3. Частота обновляемости.
   4. Система хранения и управления данными.
Операции с данными:
   1. Извлечение – перемещение информации от источников данных в отдельную БД, приведение их к единому формату.
   2. Преобразование – подготовка информации к хранению в оптимальной форме для реализации запроса, необходимого для принятия решений.
   3. Загрузка – помещение данных в хранилище, производится атомарно, путем добавления новых фактов или корректировкой существующих.
   4. Анализ – OLAP, Data Mining, Reporting и т. д.
   5. Представление результатов анализа.
Вся эта информация используется в словаре метаданных. В словарь метаданных автоматически включаются словари источников данных. Здесь же форматы данных для их последующего согласования, периодичность пополнения данных, согласованность во времени.
Задача словаря метаданных состоит в том, чтобы освободить разработчика от необходимости стандартизировать источники данных.
Создание хранилищ данных не должно противоречить действующим системам сбора и обработки информации.
Специальные компоненты словарей должны обеспечивать своевременное извлечение из словарей и обеспечить преобразование к единому формату на основе словаря метаданных.
Логическая структура данных хранилища данных отличается от структуры данных источников данных.
Для разработки эффективного процесса преобразования необходима хорошо проработанная модель корпоративных данных и модель технологии принятия решений.
Данные для пользователя удобно представлять в многоразмерных БД, где в качестве размерности могут выступать время, цена или географический регион.
Кроме извлечения данных из БД, принятия решений важен процесс извлечения знаний, в соответствии с информационными потребностями пользователя.
С точки зрения пользователя в процессе извлечения знаний из БД должны решаться след. преобразования: данные → информация → знания → полученные решения.
19. Система документации ЭИС

Состав документов, которые обрабатываются ИС, определяется на этапе формулировки требований к ЭИС. При этом могут использоваться формальные модели типа DFD, а может быть составлен и простой перечень входных и выходных документов. В любом случае после определения состава документов необходим их анализ, чтобы определить, как же информация об объектах предметной области будет отображается в ИС.
Пусть, например, требуется хранить сведения о деталях, поступивших на склад. Как объект реального мира - деталь - будет отображена в базе данных? Для того чтобы ответить на этот вопрос, необходимо знать, какие свойства детали будут необходимы для работы ИС. Среди них могут быть название детали, ее вес, размер, цвет, дата изготовления, материал, из которого она сделана и т.д. Состав этих свойств зависит от решаемых системой задач. Значения этих свойств объектов являются единицами информации, и именно они хранятся в БД.
Каждый документ, как правило - это свидетельство какого-либо события реальной жизни, в процессе которого взаимодействуют два или несколько объектов. Например, Приходный ордер отображает факт поступления товара на склад, поэтому он содержит названия этих объектов и другие их свойства (количество, цена товара, номер склада, ФИО кладовщика, сведения о поставщике товара), дату события. То есть приходный ордер отображает взаимодействие таких объектов, как товары, склад, поставщик товаров.
Целью анализа документов является выявление актуальных, существенных для ИС свойств объектов и их группировка по смыслу.
Отдельные поля документа называют "реквизитами". Каждый реквизит отображает одно свойство какого-либо объекта, имеет имя и значение. Множество всех допустимых значений реквизита называется областью определения. Реквизиты делятся на два вида:
- признаки, которые определяют обстоятельства события (место, время, действующих лиц, единицы измерения, номера документов и т.п.);
- основания, которые определяют количественные свойства объектов или процессов (цена,      количество, сумма, вес и др.).
Реквизит является элементарной единицей информации. Они могут группироваться и образуют
составные единицы информации (СЕИ), среди которых особо выделяют экономический показатель - элементарный осмысленный фрагмент документа, содержащий один атрибут - основание и ряд логически связанных с ним признаков П (О, Р1, Р2,….Рn). Минимальный набор атрибутов показателя включает основание, имена объектов, участвующих в процессе, и время действия. Для наглядного изображения логических и расчетных связей между показателями и для показа последовательности их расчета применяют граф взаимосвязи показателей, в котором вершины соответствуют показателям, а дуга идет от П1 к П2, если при расчете П2 используется основание П1.
Пример. На рис.2.2 показан примерный вид приходного ордера. Выделим признаки, снования и
показатели. Признаки: Номер ордера, Дата, Наименование п.п, Адрес, Код поставщика, Ном.№,
Наим. Товара.
Таким образом, анализ документов проводят в следующем порядке:
1. Анализ структуры документов, выделение существенных признаков, оснований,
показателей.
2. Выявление взаимосвязей между показателями, запись расчетных формул.
3. Построение графа взаимосвязи показателей.
После этого начинается следующий этап: определение структур данных, хранящихся в базе данных. Для этого чаще всего применяют диаграммы структуры данных (DSD) и ERD-диаграммы.
20. Унифицированные системы документации
Документ содержит в фиксированном типе набор полей, характеризующемся законченным смысловым содержанием.
Базовыми характеристиками документов являются:
• Соответствие функции управления(анализ)
1. Виды учетов:
2. Оперативный
3. Бухгалтерский
4. Налоговый
5. Статистический
6. Управленческий

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

Макет – форма документа представлен:
Заголовочная зона

Для реквизитов, характеризующих форму предоставления документа, сферу его действия, реквизиты конкретного экземпляра заполненного документа Наименование предприятия
Название ИС
Код документа Код формы документа
Постоянные характеристики формы

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

Текстовый документ – структурированный или не структурированный текст

Документы:
• Первичные
• Промежуточные (результаты)
• Выходные (результаты обработки данных)
Структура данных документа рассматривается как структурные единицы(СЕИ), могут быть представлены аналитически и графически
УСД – унифицированные системы документации, создаются по функциональному признаку.
Цели создания УСД:
Уменьшение разнообразия содержания и форм документов
Обеспечение экономической эффективности и каличества для различных этапов обработки документов
Для УСД семизначный код. Например финансовая, отчетная документация бюджетных организаций: 0500000
Основные направления  развития УСД:
1) создание общей модели построения документов(формуляр-образец, шаблон формы)
2) Уменьшение количества форм документов, сокращение количества пользователей форм. Документа
3) Использование информационных технологий в обработке документов
4) Единая терминология(наименование реквизитов, показателей)
5) Типизация и трафаретизация текстов
6) Унификация форматов реквизитов
7) Расположение реквизитов в соответствии с посл. Заполнения или использования
УСД должны готовиться на бланках стандартного форматного ряда «А» (ГОСТ 93 27 – 60)
Необходимо обеспечить однократную запись информации в документ
Форма документа является основой для типографного изг бланка, либо программирования(экр формы, формы отчетных (выходных) документов)

30. Последовательные линейные структуры данных (методы поиска)

Для поиска задается критерий, которому должен удовлетворять ключ записи. Поиск осуществляется при условии равенства ключа критерию.
Методы:
• Последовательное сканирование(среднее число сканирований = n/2)
• Блочный поиск: массив разбивается на блоки при условии, что массив предварительно упорядочен. Искомый ключ последовательно сравнивается с ключом последней записи в блоке; определяется блок, внутри которого находится запись и внутри него осуществляется последовательное сканирование.(количество просмотров = n/2d+d/2, где d - размер блока, n – количество элементов).
Поиском называется процедура выделения из некоторого
множества записей определенного подмножества, записи которого
удовлетворяют некоторому заранее поставленному
условию. Условие поиска часто называют запросом на поиск.
Простейшим условием поиска является поиск по совпадению,
т. е. равенство значения ключевого атрибута i-й записи
р(0 и некоторого заранее заданного значения q. Алгоритмы
всех разновидностей поиска можно получить из алгоритмов
поиска по совпадению, которые и рассматриваются в дальнейшем.

Базовым методом доступа к массиву является ступенчатый
поиск. Этот метод предполагает упорядоченность обрабатываемых
записей, причем безразлично, по возрастанию
или по убыванию. Для определенности будем считать, что
массив отсортирован по возрастанию значений ключевого
атрибута p(i).
Простейшим вариантом ступенчатого поиска (его можно
назвать одноступенчатым) является последовательный поиск.
Искомое значение q сравнивается с ключом первой записи,
если значения не совпадают, с ключом второй записи и т. д. до
тех пор, пока q не станет больше ключа очередной записи.
Алгоритм последовательного поиска может быть представлен
следующей программой на языке Паскаль:
program poisk;
const M=20;
var i,q:integer;
p: array[l..M] of integer;
begin
шгке('ввод q');
readln(q);
fori:=l toM do
begin
>&тке('ввод', i,' элемента массива'); readln(p[i])
end;
i:=l;
while q < p[i] do i:= i+1;
if q <> p[ij then writeln('B массиве нет значения', q)
else writeln('HOMep ',i,' значение', q)
end.
Число сравнений в цикле while может быть выражено как
С= Z i*r(i), где суммирование по i ведется в пределах от 1 до М.
Поиск с одинаковой вероятностью r(i)=l/M может окончиться
на любой записи, поэтому
С = (1/М)- Е i = (М + 1)/2 или С ~ М.
147
Рассмотрим двухступенчатый поиск в массиве, состоящем
из М записей. Для заданного М выбирается константа dl, называемая
шагом поиска. Если необходимо отыскать запись со
значением ключевого атрибута, равным q, производятся следующие
действия.
Значение q последовательно сравнивается с рядом величин
р(1), p(l+dl), p(l+2*dl),..., p(l+k*dl) до тех пор, пока будет
впервые достигнуто неравенство p(l+m*dl)=>q. Здесь заканчивается
первая ступень поиска. На второй ступени q последовательно
сравнивается со всеми ключами, которые имеют
номер l+m*dl и больше, до тех пор, пока в процессе сравнений
будет достигнут ключ, больший, чем q. Извлеченные при
этом записи с ключом q образуют результат поиска.
Эффективность поиска измеряется количеством произведенных
сравнений. Для двухступенчатого поиска среднее число
сравнений примерно составит:
C = M/(2*dl) + dl/2.
Параметр dl выбираемый и естественно выбрать его так,
чтобы минимизировалось С. Будем считать dl непрерывной
переменной и вычислим производную
C'=-M/(2*dlA2)+l/2.
Из условия С'= 0 получаем dl=SQR(M). Вторая производная
С" в точке х = dl положительна, следовательно, достигнуто
минимальное значение С.
При п-ступенчатом поиске заранее выбираются константы
п и S. На первом этапе ключевые атрибуты для сравнения с
искомым ключом q выбираются из массива по закону арифметической
прогрессии, начиная с р(1) и шагом dl=M/S (округление
в меньшую сторону). Когда будет впервые достигнут
ключ p(k) > q, выбирается шаг d2 = dl/S и организуются
сравнения с этим шагом, начиная с p(k-dl). Описанные действия
повторяются п раз, -причем шаг на последней ступени
поиска dn= 1.
Минимальное число сравнений достигается при S=MA(l/n),
и, кроме того, существует оптимальное п=1п(М).
148
Ступенчатый поиск имеет важный частный вариант -
бинарный поиск, когда S=2.
Для бинарного поиска вводятся левая граница интервала
поиска А и правая граница В. Первоначально интервал охватывает
весь массив, т. е. А=0, В=М+1. Вычисляется середина
интервала i по формуле i=(A+B)/2 с округлением в меньшую
сторону. Ключ i-й записи p(i) сравнивается с искомым значением
q. Если p(i) =q, то поиск заканчивается. В случае p(i)>q
записи с номерами i+1, i+2,..., М заведомо не содержат ключа
q, и надо сократить интервал поиска, приняв B=i. Аналогично
при p(i)<q надо взять A=i. Далее середина интервала вычисляется
заново, и все действия повторяются. Если будет достигнут
нулевой интервал, то требуемой записи в массиве нет.
Алгоритм бинарного поиска может быть представлен следующей
программой на языке Паскаль:
program bin;
const M=10;
var i,A,B,q: integer;
p:array[l..M] of integer;
begin
write('BBOfl q');
readln(q);
fori:=l toMdo
begin
write('BBOfl\ i,' элемента массива'); readln(p[i])
end;
A:=0;B:=M+1;
i:=(A+B) div 2; {определение середины интервала}
{цикл до встречи p[i]=q или до нулевого интервала A=i}
while (p{i]<>q) and (A<i) do
begin
if q>p[i] then A:=i else B:=i;
i:=(A+B) div 2; {середина нового интервала}
end;
149
if A=i then writeln('B массиве нет значения', q)
else writeln('HOMep \i,' значение',^
end.
Достаточно легко оценить максимальное число сравнений
Cm при поиске данных бинарным методом. Сокращение интервала
поиска на каждом шаге в худшем случае приведет к
интервалу нулевой длины, что соответствует отсутствию в
массиве искомого значения ключевого атрибута. После первого
сравнения интервал поиска составит М/2 записей, после
второго - М/4 и т. д. Когда интервал поиска впервые станет
меньше 1, применяемая схема округления результата деления
даст нулевой интервал и поиск закончится. Это соответствует
неравенству
М/(2АСга)<=1
(знак Л обозначает возведение в степень), откуда Cm~log M.
Среднее число сравнений при бинарном поиске составляет
C=log(M) -1. Для обоснования представим все возможные
разветвления алгоритма бинарного поиска в виде дерева. Число
уровней дерева соответствует Ст. Половина возможных
сравнений расположена на последнем уровне и половина— на
первых (log(M)-l) уровнях.
Определение лучшего метода поиска (из рассмотренных
выше последовательного, двухступенчатого и бинарного) опирается
на следующие рассуждения. Во всех трех случаях время
поиска является функцией от числа записей М. Конкретные
выражения составляют:
• для последовательного поиска
Т1~МилиТ1=к1*М;
• для двухступенчатого поиска
T2~SQR(M) или T2=k2(SQR(M));
• для бинарного поиска
ТЗ-logM или T3=k3*logM.
150
Коэффициенты пропорциональности в каждом случае неизвестны
(они определяются в зависимости от быстродействия
ЭВМ и применяемого языка программирования). Однако очевидно,
что функция логарифма растет с увеличением М медленнее,
чем две другие функции (для Т1 и Т2), как это показано
на рис. 3.2.
Рис. 3.2. Сравнение методов поиска данных в массиве
Поэтому можно утверждать даже при неизвестных коэффициентах
kl, k2, k3, что при достаточно большом числе записей
М бинарный метод поиска выполняется, безусловно,
быстрее двух остальных. Значения kl, k2, кЗ влияют на граничную
величину М, выше которой преимущество бинарного
поиска безусловно.

31. Строчные линейные структуры данных (однонаправленные списки)

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

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

Рис.1. Схематичное изображение однонаправленного списка без заглавного звена
   
Над списками выполняются следующие операции:
• начальное формирование списка (запись первой компоненты);
• добавление компоненты в конец списка;
• определение первого элемента в линейном списке;
• чтение компоненты с заданным ключом; с заданным свойством;
• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);
• исключение компоненты с заданным ключом из списка.
• упорядочивание узлов линейного списка в определенном порядке.
    Описание компоненты однонаправленного списка дадим следующим образом:
    Type
       PtrRec = ^Rec;
       Rec = Record
             Element : TypeElement;   {Информационное поле}
             pNext   : PtrRec;        {Ссылка на следующую компоненту}
         End;
    Для формирования однонаправленного списка и работы с ним необходимо описать четыре переменных типа указатель на запись. Договоримся, что pBegin определяет начало списка, а pCKey, pPredRec, pAux определим как вспомогательные (указатель на компоненту с заданным ключем, указатель на компоненту перед заданным ключем, временный указатель):
    Var
      pBegin, pCKey, pPredRec, pAux : PtrRec;

32. Строчные линейные структуры данных (двунаправленные списки)

Двунаправленные списки
     Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 4 приведена графическая интерпретация двунаправленного списка [3].

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

33. Индексы и инвертированные списки

Для ускорения поиска записей в массиве используется дополнительная информация, организованная в виде массива индексов.
Индексом называется набор ключей и адресов записей, которые выбираются из основного массива по определенному закону. Отдельный элемент набора индексов также называется индексом, хотя это не соответствует значению слова index - список.
Имеются три важные разновидности индексов:
• информация о каждой записи основного массива попадает в индекс (сплошная индексация);
• номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d> 1.
Основной массив, дополненный таким индексом, обычно называется индексно-последовательным;
• ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию.
Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Этот случай уже рассмотрен в п. 2.4.
Индексно-последователъный массив представляет собой
последовательный массив, отсортированный по значениям ключевого
атрибута, к которому создается дополнительный массив
индексов.
В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. На рис. 3:11
показаны ключевые атрибуты основного массива и состояние
массива индексов для d=3.
Индекс
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Номера записей
Рис. 3.11. Индексно-последовательная организация данных
172
Поиск значения q в индексно-последовательном массиве происходит в две стадии:
• в массиве индексов (который отсортирован в силу упорядоченности
основного массива);
• среди записей основного массива, расположенных между двумя соседними индексами, найденными на первой стадии.
Применение индексов приводит к ускорению доступа, если основной массив располагается на внешнем запоминающем устройстве, а массив индекса может быть полностью размещен в оперативной памяти ЭВМ. Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию,
мы получаем ситуацию с адресной функцией для индекса (рандомизация индекса).
Точное описание рандомизированного индекса состоит в следующем. Индекс с номером n хранит адрес записи основного массива, ключ которой равен или непосредственно больше значения p (1)+z(n-1), где z - константа (шаг арифметической прогрессии);
р(1) - значение ключа первой записи основного массива.
На рис. 3.12 показаны ключевые атрибуты основного массива
(идентичные с предыдущим примером) и состояние массива
рандомизированных индексов для г= 10. Примечательно,
что значения ключей в таком индексе хранить не нужно.
Рассмотрим поиск с использованием рандомизированных индексов.
На первой стадии номер требуемого далее индекса определяется
по формуле
„ - q - p w + i .
Z
Результат деления округляется в меньшую сторону. Интервал
записей основного массива на второй стадии поиска определяется
адресами, указанными в n-м и (п+1)-м индексах.
173
Рандомизированный индекс
24 126 31 I 35 39 42 47 52 54 58 63 66 68 72 75
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Номера записей
Рис. 3.12. Рандомизация индекса
Важной разновидностью доступа к данным, которая требует специальных методов ускорения доступа, является обработка информации по нескольким ключевым признакам. В структуре записи массива определяется несколько ключевых атрибутов, причем в различных прикладных программах требуется доступ к записям по различным сочетаниям этих атрибутов и, возможно, требуется последовательная обработка
всего массива.
Среди ключевых атрибутов записи устанавливается порядок старшинства. Извлекаемые на обработку записи должны быть упорядочены в пределах всего массива по самому старшему ключу. В пределах группы записей с одинаковым значением старшего ключа должна соблюдаться упорядоченность по значениям следующего по старшинству ключа и т. д. Проще всего представить упорядоченность по нескольким ключам с помощью следующей схемы.
Пример
Рассмотрим записи с четырьмя атрибутами в порядке старшинства слева направо А1, А2, A3, А4. Значения А1 упорядочены (для примера) по возрастанию. На каждом множестве записей, которые соответствуют одинаковому значению А1, реализована порядоченность
по возрастанию значений А2 для записей, у которых значение А1 одинаково. Далее, на каждом множестве записей с одинаковыми парами значений атрибутов А1 и А2 соблюдается упорядоченность значений по атрибуту A3. И, наконец, на каждом множестве записей с одинаковыми значениями атрибутов А1, А2, A3 должна  соблюдаться упорядоченность по возрастанию для атрибута А4.             Последовательный массив с такой упорядоченностью может обеспечивать быстрый доступ к данным по следующим сочетаниям ключевых атрибутов al+a2+a3+a4, al+a2+a3, al+a2 и al. Количество сочетаний атрибутов, необходимых для реализации максимально широкого круга запросов, в нашем примере составляет 15. Хранение нескольких по-разному рассортированных дублей массива или систематическая сортировка единственного массива в соответствии с поступающими запросами не является
хорошим решением проблемы.
Рассмотрим возможности создания нескольких массивов индексов в этой ситуации. Индекс удобно формировать не для одного ключевого атрибута, а для набора атрибутов.
Естественно, что индекс ключевых атрибутов al+a2+a3+a4 может также использоваться для быстрого доступа по атрибутам al+a2+a3, al+a2 и al. Поэтому в нашем примере
максимально необходимо создание 4 индексов с упорядоченностью атрибутов al+a2+a3+a4, al+a2+a4, al+a3+a4, а2+аЗ+а4.
Для доступа к данным по нескольким ключевым атрибутам используется также мультисписковая организация данных.
Мультисписком называется множество списков, организованных
на общем множестве записей. Если требуется доступ к записям
по t ключам, то формируется t списков для каждого ключевого
атрибута в отдельности.
Рассмотрим особенности организации мультисписков, которые
предназначены для обработки записей по нескольким
ключевым атрибутам.
Пример
В табл. 3.2 показаны 14 записей с ключевыми атрибутами Фамилия
и Профессия (остальные атрибуты в данном случае несущественны).
На пересечении строки с некоторой фамилией и столбца
с некоторой профессией указан номер записи, которая содержит
именно эти значения в качестве ключей.
175
В простейшем случае мультисписок будет содержать два списка
- с указателем Фамилия - (А(1), А(2), А(3), ... , А(13), А(14)) и
с указателем Профессия- (А(3), А(6), А(12), А(1), А(7), А(10), А(13),
А(2), А(4), А(8), А(14), А(5), А(9), А(11)).
Таблица 3.2. Мультисписок для двух ключевых атрибутов
Фамилия
Бардин
Басов
Батов
Белов
Иванов
Исаев
слесарь
А(3)
А(6)
А(12)
Профессия
токарь
АО)
А(7)
А(Ю)
А(13)
штамповщик
А(2)
А(4)
А(8)
А(14)
электрик
А(5)
А(9)
А(11)
При размещении мультисписка во внешней памяти необходимо
размещать каждый список в небольшом числе рядом расположенных
участков, что позволит уменьшить время доступа.
Эффективная организация мультисписка предполагает
выполнение следующих условий:
• число записей в каждом списке должно быть небольшим,
• адреса хранения записей должны монотонно возрастать.
Для сокращения длины списков в мультисписке необходимо
детализировать содержимое указателей. Например, указатель
Фамилия = "Ба" определяет список (А(1), А(2), А(3), А(4),
А(5), А(6), А(7)), указатель Фамилия = "Бе" - список (А(8),
А(9)), указатель Фамилия = "И" - список (А(10), А(11), А(12),
А(13), А(14)). Поскольку атрибут Профессия содержит четыре
значения, возможно существование следующих четырех
списков: (А(3),А(6),А(12)); (А(1),А(7),А(10),А(13)); (А(2),
А(4),А(8), А(14)); (А(5),А(9),А(11)).
При поиске в сокращенных списках необходимо сначала
проанализировать все указатели, чтобы выбрать одну строку,
заведомо содержащую требуемую информацию.
Рассмотрим запрос с условием
Фамилия ="Иванов" и Профессия = "электрик"
Потребуются три обращения к памяти для выбора списка
(А(10), А,(П), А(12)),А(13), А(14)) и четыре обращения для
выбора списка (А(5),А(9), А(11)). В указателях хранится длина
каждого списка. Вторая строка короче, поэтому она просматривается
полностью до извлечения нужной записи А(11).__

Инвертированные списки
До сих пор мы рассматривали структуры данных, которые использовались для ускорения доступа по первичному ключу. Однако достаточно часто в базах данных требуется проводить операции доступа по вторичным ключам. Напомним, что вторичным ключом является набор атрибутов, которому соответствует набор искомых записей. Это означает, что существует множество записей, имеющих одинаковые значения вторичного ключа. Например, в случае нашей БД "Библиотека" вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в один год.
Для обеспечения ускорения доступа по вторичным ключам используются структуры, называемые инвертированными списками, которые послужили основой организации индексных файлов для доступа по вторичным ключам.
Инвертированный список в общем случае — это двухуровневая индексная структура. Здесь на первом уровне находится файл или часть файла, в которой упорядоченно расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепочка блоков, содержащих номера записей, содержащих одно и то же значение вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа.
И наконец, на третьем уровне находится собственно основной файл.
Механизм доступа к записям по вторичному ключу при подобной организации записей весьма прост. На первом шаге мы ищем в области первого уровня заданное значение вторичного ключа, а затем по ссылке считываем блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа, а далее уже прямым доступом загружаем в рабочую область пользователя содержимое всех записей, содержащих заданное значение вторичного ключа.
Инвертированный (метод вторичного индексирования)
Значения ключей физических записей необязательно находятся в логической последовательности. Метод применяется только для выборки данных. Индекс может быть построен для каждого инвертированного поля. Эффективность доступа зависит от числа записей БД, числа уровней индексации и распределения памяти для размещения индекса.
Инвертированные списки формируются системой для поисковых атрибутов, причем для каждого возможного значения такого атрибута составляется список уникальных номеров записей, в которых это значение атрибутов присутствует. Записи с одним и тем же значением поля группируются, а общее для всей группы значение используется в качестве указателя этой группы. Тогда при поиске записей по значениям поисковых атрибутов системе достаточно отыскать списки, соответствующие требуемым значениям, и выбрать номер записи согласно заданной «схеме» пересечения или объединения условий на значениях поисковых атрибутов, а также отрицания некоторого условия.
Индексные наборы данных  обеспечивают ускорение доступа к записям последовательной или строчной структуры данных. Существует несколько видов индексов:
• Сплошной: каждому элементу индекса соответствует единственная запсись последовательной линейной структуры данных или строки.
• К-индексы: указатель содержит адрес и ключевой реквизит записи. Номера записи образуют арифметическую прогрессию с шагом d.
• А-индексы: в индекс входят ключи записей, которые образуют арифметическую прогрессию. Первый индекс адресует первую запись.
По искомому значению и известному ключу 1 записи, шагу арифметической прогрессии определяется номер записи в А-индексе

2. Задание «Разработать иерархический классификатор»

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

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

Для моделирования бизнес-процессов используется несколько различных методов, основой которых являются как структурный, так и объектно-ориентированный подходы к моделированию. Однако деление самих методов на структурные и объектные является достаточно условным, поскольку наиболее развитые методы используют элементы обоих подходов. К числу наиболее распространенных методов относятся:
• метод функционального моделирования SADT (IDEF0);
• метод моделирования процессов IDEF3;
• моделирование потоков данных DFD;
• метод ARIS;
• метод Ericsson-Penker;
• метод моделирования, используемый в технологии Rational Unified Process.

Метод SADT (Structured Analysis and Design Technique) считается классическим методом процессного подхода к управлению. Основной принцип процессного подхода заключается в структурировании деятельности организации в соответствии с ее бизнес-процессами, а не организационно-штатной структурой.
Метод SADT представляет собой совокупность правил и процедур, предназначенных для построения функциональной модели объекта какой-либо предметной области. Функциональная модель SADT отображает функциональную структуру объекта, т.е. производимые им действия и связи между этими действиями.
Результатом применения метода SADT является модель, которая состоит из диаграмм, фрагментов текстов и глоссария, имеющих ссылки друг на друга. Диаграммы – главные компоненты модели, все функции организации и интерфейсы на них представлены как блоки и дуги соответственно. Место соединения дуги с блоком определяет тип интерфейса. Управляющая информация входит в блок сверху, в то время как входная информация, которая подвергается обработке, показана с левой стороны блока, а результаты (выход) показаны с правой стороны. Механизм (человек или автоматизированная система), который осуществляет операцию, представляется дугой, входящей в блок снизу.
Одной из наиболее важных особенностей метода SADT является постепенное введение все больших уровней детализации по мере создания диаграмм, отображающих модель.
Построение диаграмм начинается с представления всей системы в виде простейшего компонента – одного блока и дуг, изображающих интерфейсы с функциями вне системы. Поскольку единственный блок отражает систему как единое целое, имя, указанное в блоке, является общим. Это верно и для интерфейсных дуг– они также соответствуют полному набору внешних интерфейсов системы в целом. Затем блок, который представляет систему в качестве единого модуля, детализируется на другой диаграмме с помощью нескольких блоков, соединенных интерфейсными дугами. Эти блоки определяют основные подфункции исходной функции. Данная декомпозиция выявляет полный набор подфункций, каждая из которых показана как блок, границы которого определены интерфейсными дугами. Каждая из этих подфункций может быть декомпозирована подобным образом в целях большей детализации.
Модель SADT представляет собой серию диаграмм с сопроводительной документацией, разбивающих сложный объект на составные части, которые изображены в виде блоков. Детали каждого из основных блоков показаны в виде блоков на других диаграммах. Каждая детальная диаграмма является декомпозицией блока из диаграммы предыдущего уровня. На каждом шаге декомпозиции диаграмма предыдущего уровня называется родительской для более детальной диаграммы.
Общее число уровней в модели (включая контекстный) не должно превышать 5-6. Практика показывает, что этого вполне достаточно для построения полной функциональной модели современного предприятия любой отрасли. Метод SADT в наибольшей степени подходит для описания процессов верхнего уровня управления. Его основные преимущества заключаются в следующем:
• полнота описания бизнес-процесса (управление, информационные и материальные потоки, обратные связи);
• комплексность декомпозиции;
• возможность агрегирования и детализации потоков данных и информации (разделение и слияние дуг);
• наличие жестких требований, обеспечивающих получение моделей стандартного вида;
• простота документирования процессов;
• соответствие подхода к описанию процессов стандарту ISO 9000:2000.
В то же время метод SADT обладает рядом недостатков:
• сложность восприятия (большое количество дуг на диаграммах);
• большое количество уровней декомпозиции;
• трудность увязки нескольких процессов, представленных в различных моделях одной и той же организации.

35 билет
Диаграммы потоков данных (анализ документооборота)
3.3. Моделирование потоков данных
Диаграммы потоков данных (Data Flow Diagrams– DFD) представляют собой иерархию функциональных процессов, связанных потоками данных. Цель такого представления – продемонстрировать, как каждый процесс преобразует свои входные данные в выходные, а также выявить отношения между этими процессами.
Модель системы определяется как иерархия диаграмм потоков данных, описывающих асинхронный процесс преобразования информации от ее ввода в систему до выдачи потребителю. Источники информации (внешние сущности) порождают
информационные потоки (потоки данных), переносящие информацию к подсистемам или процессам. Те, в свою очередь, преобразуют информацию и порождают новые потоки, которые переносят информацию к другим процессам или подсистемам, накопителям данных или внешним сущностям – потребителям информации.
Диаграммы верхних уровней иерархии (контекстные диаграммы) определяют основные процессы или подсистемы с внешними входами и выходами. Они детализируются при помощи диаграмм нижнего уровня. Такая декомпозиция продолжается, создавая многоуровневую иерархию диаграмм, до тех пор, пока не будет достигнут уровень декомпозиции, на котором детализировать процессы далее не имеет смысла.
Состав диаграмм потоков данных
Основными компонентами диаграмм потоков
данных являются:
• внешние сущности;
• системы и подсистемы;
• процессы;
• накопители данных;
• потоки данных.

Внешняя сущность (квадрат с тенью) представляет собой материальный объект или физическое лицо, являющиеся источником или приемником информации, например, заказчики, персонал, поставщики, клиенты, склад. Определение некоторого объекта или системы в качестве внешней сущности указывает на то, что она находится за пределами границ анализируемой системы. В процессе анализа некоторые внешние сущности могут быть перенесены внутрь диаграммы анализируемой системы, если это необходимо, или, наоборот, часть процессов может быть вынесена за пределы диаграммы и представлена как внешняя сущность.
Процесс представляет собой преобразование входных потоков данных в выходные в соответствии с определенным алгоритмом. Физически процесс может быть реализован различными способами: это может быть подразделение организации (отдел), выполняющее обработку входных документов и выпуск отчетов, программа, аппаратно реализованное логическое устройство и т.д.
Накопитель данных – это абстрактное устройство для хранения информации, которую можно в любой момент поместить в накопитель и через некоторое время извлечь, причем способы помещения и извлечения могут быть любыми. Накопитель данных идентифицируется буквой «D» и произвольным числом. Имя накопителя выбирается из соображения наибольшей информативности для проектировщика.
Поток данных определяет информацию, передаваемую через некоторое соединение от источника к приемнику. Реальный поток данных может быть информацией, передаваемой по кабелю между двумя устройствами, пересылаемыми по почте письмами, магнитными лентами или дискетами, переносимыми с одного компьютера на другой и т.д.
Поток данных на диаграмме изображается линией, оканчивающейся стрелкой, которая показывает направление потока. Каждый поток данных имеет имя, отражающее его содержание.
Главная цель построения иерархии DFD заключается в том, чтобы сделать описание системы ясным и понятным на каждом уровне детализации, а также разбить его на части с точно определенными отношениями между ними.

Перекрестки
Перекрестки (Junction) обеспечивают отображение логики взаимодействия стрелок при слиянии и разветвлении.
Таблица 8
Обозначение Наименование Смысл в случае слияния стрелок
(Fan-in-Junction) Смысл в случае разветвления стрелок
(Fan-out-Junction)
Асинхронное «И» Все предшествующие процессы должны быть завершены Все следующие процессы должны быть запущены
Синхронное «И» Все предшествующие процессы завершены одновременно Все следующие процессы запускаются одновременно
Асинхронное «ИЛИ» Один или более предшествующих процессов должны быть завершены Один или несколько следующих процессов должны быть запущены
Синхронное «ИЛИ» Один или более предшествующих процессов завершены одновременно Один или несколько следующих процессов запускаются одновременно
Исключающее «ИЛИ» Только один предшествующий процесс завершен Только один следующий процесс запускается

Перекрестки нумеруются, префикс – J, стрелки могут сливаться или разветвляться только через перекрестки.
Правила создания перекрестков:
1. Каждому перекрестку для слияния должен предшествовать перекресток для разветвления.
2. Перекресток для слияния «И» не может следовать за перекрестком для разветвления типа синхронного или асинхронного «ИЛИ».
3. Перекресток для слияния «И» не может следовать за перекрестком для разветвления типа исключающего «ИЛИ».
4. Перекресток для слияния типа исключающего «ИЛИ» не может следовать за перекрестком для разветвления типа «И».
5. Перекресток, имеющий одну стрелку на одной стороне, должен иметь более одной стрелки на другой стороне.

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

Можно по-разному характеризовать понятие модели данных СУБД. С одной стороны, модель данных СУБД – это способ структурирования данных, которые рассматриваются как некоторая абстракция в отрыве от предметной области. С другой стороны,модель данных СУБД – это инструмент представления концептуальной модели предметной области и динамики ее изменения в виде базы данных.
Учитывая обе вышеуказанные стороны, определим основные структуры моделей данных СУБД, используемые для представления концептуальной модели предметной области (сущностей, атрибутов, связей).
Элемент данных (поле) – наименьшая поименованная единица данных. Используется для представления значения атрибута.
С элементом данных неразрывно связано понятие "тип данных", который может принимать соответствующее поле. В разных СУБД могут использоваться разные типы данных, наиболее распространенными из которых (используемые во многих СУБД) являются следующие: числовой (numeric), символьный (char), дата (date) и т.д.
Запись – поименованная совокупность полей. Используется для представления совокупности атрибутов сущности (записи о сущности).
Экземпляр записи – запись с конкретными значениями полей.
Первичный ключ – минимальный набор полей записи, однозначно идентифицирующих экземпляр записи файла.
Файл – поименованная совокупность экземпляров записей одного типа. Используется для представления однородного набора сущностей.
Набор файлов – поименованная совокупность файлов, обрабатываемых в системе. Используется для представления нескольких наборов сущностей.
Введем понятие "группа", обобщающее понятия "файл" и "запись".
Группа – это поименованная совокупность элементов данных и других групп.
Важнейшим понятием концептуальной модели является понятие связи между сущностями (наборами сущностей). В моделях данных СУБД соответствующее понятие отражается понятием "групповое отношение".
Групповое отношение – поименованное бинарное отношение, заданное на двух множествах экземпляров рассматриваемых групп. По характеру бинарных связей различают групповые отношения вида 1:1, 1:M, M:1, M:N. Пары чисел называют коэффициентами группового отношения. В групповом отношении один член группы назначается владельцем отношения, другой – членом.
База данных – поименованная совокупность экземпляров групп и групповых отношений.
Для представления группового отношения используется две формы:
а) Графовая. Группы изображаются вершинами графа, связи между группами – дугами, направленными от группы-владельца к группе-члену с указанием имени отношения и коэффициента.
По типу графов различают:
• иерархическую модель (граф без циклов – дерево);
• сетевую модель (ориентированный граф общего вида).
б) Табличная. Связь между группами изображается таблицей, столбцы которой представляют ключи соответствующих групп. Для формального описания таблицы используется математическое (теоретико-множественное) понятие отношения. Соответствующаямодель данных называется реляционной моделью.
Модель данных СУБД описывается следующим образом:
• определены возможные типы и характеристики логических структур данных (полей, записей, файлов);
• заданы правила составления структур более общего типа из структур более простых типов (например, записей из полей, файлов из записей и т.д.);
• определен способ представления связей (отношений) между файлами и записями) с помощью дополнительных полей ;
• определены возможные действия над структурами и правила их выполнения, включающие:
o основные элементарные операции над данными;
o обобщенные операции (процедуры);
o средства контроля относительно простых условий корректности операций добавления, обновления или удаления данных (ограничения), реализуемые автоматически запускаемыми при выполнении вышеуказанных операций специальными процедурами (триггерами);
o средства контроля сколь угодно сложных условий корректности выполнения определенных действий (правила);
o специальный класс процедур (триггеры).
В качестве основных элементарных операций обычно рассматриваются следующие: поиск записи с заданным значением ключа, чтение нужной записи, добавление записи, корректировка, удаление. В моделях данных СУБД также предусматриваются специальные операции для установления групповых отношений.
Обобщенные операции или процедуры – последовательность операций, реализующая определенный алгоритм обработки данных. Процедуры могут инициироваться СУБД автоматически, а также могут запускаться пользователем. Примерами процедур являются процедуры копирования БД, восстановления БД, процедуры, вычисляющие значения определенных атрибутов в БД по значениям других атрибутов, и т.п.

Структура данных и операции над ними
Структура данных строится с помощью элементов данных, связанных между собой логич и физич связями, физич положением.
Существуют структуры данных внемашинного и внутримашинного уровня представления. На внемашинном уровне рассматриваются единицы инфы с учетом их связей для бумажных носителей – форм документов, классификаторов и кодификаторов технико-эк. Инфы.
Во внутримашин структуре данных элементами структуры являются поля и логич записи. Логич запись рассматривается как объединение нескольких полей. Набор экземпляров, записей образуют массив(файл).
В качестве основных элементарных операций обычно рассматриваются следующие: поиск записи с заданным значением ключа, чтение нужной записи, добавление записи, корректировка, удаление. В моделях данных СУБД также предусматриваются специальные операции для установлеания групповых отношений.
37 Архитектура многоуровневого представления данных БД
Американск нац институт стандартов разработал многоуровневую модель БД ANSI/SPARC.
В этой модели выделяется 3 уровня абстракции, т.е. 3 различных уровня описания элементов данных. Эти уровни формируют трехуровневую архитектуру, которая охватывает внешний, концептуальный и внутренний уровни. Цель трехуровневой архитектуры заключается в отделении пользовательского представления базы данных от ее физического представления.
Уровень, на котором воспринимают данные пользователи, называется внешним уровнем (external level), тогда как СУБД и операционная система воспринимают данные на внутреннем уровне (internal level). Именно на внутреннем уровне данные реально сохраняются с использованием всех тех структур и файловой организации. Концептуальный уровень (conceptual level) представления данных предназначен для отображения внешнего уровня на внутренний и обеспечения необходимой независимости друг от друга.

Рисунок 1 Трехуровневая архитектура ANSI-SPARC

Внешний уровень. Внешний уровень состоит из нескольких различных внешних представлений БД. Каждый пользователь имеет дело с представлением предметной области, выраженным в наиболее удобной для него форме. Внешнее представление содержит только те сущности, атрибуты и связи предметной области, которые интересны пользователю.
Помимо этого, различные представления могут по-разному отображать одни и те же данные. Например, один пользователь может просматривать даты в формате (день, месяц, год), а другой - в формате (год, месяц, день). Некоторые представления могут включать производные или вычисляемые данные, которые не хранятся в базе данных как таковые, а создаются по мере надобности. Представления могут также включать комбинированные или производные данные из нескольких объектов.
Концептуальный уровень. Промежуточным уровнем в трехуровневой архитектуре является концептуальный уровень. Этот уровень содержит логическую структуру всей базы данных (с точки зрения АБД). Фактически, это полное представление требований к данным, которое не зависит от любых соображений относительно способа их хранения. На концептуальном уровне представлены следующие компоненты: все сущности, их атрибуты и связи; накладываемые на данные ограничения; семантическая информация о данных; информация о мерах обеспечения безопасности и поддержки целостности данных.
Концептуальный уровень поддерживает каждое внешнее представление, в том смысле, что любые доступные пользователю данные должны содержаться (или могут быть вычислены) на этом уровне. Однако этот уровень не содержит никаких сведений о методах хранения данных.
Внутренний уровень. Внутренний уровень описывает физическую реализацию базы данных и предназначен для достижения оптимальной производительности и обеспечения экономного использования дискового пространства. Он содержит описание структур данных и организации отдельных файлов, используемых для хранения данных в запоминающих устройствах. На этом уровне осуществляется взаимодействие СУБД с методами доступа операционной системы с целью размещения данных на запоминающих устройствах, создания индексов, извлечения данных и т.д. На внутреннем уровне хранится следующая информация: сведения о распределении дискового пространства для хранения данных и индексов; описание подробностей сохранения записей (с указанием реальных размеров сохраняемых элементов данных); сведения о размещении записей; сведения о сжатии данных и выбранных методах их шифрования.
38. Иерархическая модель данных
Это также одна из наиболее ранних моделей данных. Реализация групповых отношений в иерархической модели, как и в сетевой, может осуществляться с помощью указателей и представляется в виде графа. Однако, в отличие от сетевой модели, здесь существует ряд принципиальных особенностей.
1. Групповые отношения являются отношениями соподчиненности. Группа (запись) – владелец отношения имеет подчиненные группы – члены отношений. Исходная группа называется предком, подчиненная – потомком.
2. Групповые отношения образуют иерархическую структуру, которую можно описать как ориентированный граф следующего вида:
o имеется единственная особая вершина (соответствующая группе), называемая корнем, в которую не заходит ни одно ребро (группа не имеет предков);
o во все остальные вершины входит только одно ребро (все остальные группы имеют одного предка), а исходит произвольное количество ребер (группы имеют произвольное количество потомков);
o отсутствуют циклы.
3. Иерархическая модель данных может представлять совокупность нескольких деревьев. В терминологии иерархической модели деревья, описывающие структуру данных, называются деревьями описания данных, а сами структурированные данные (база данных) – деревьями данных.
Особенностью реализации операций поиска в иерархической модели является то, что операция всегда начинает поиск с корневой вершины и специфицирует иерархический путь (последовательность связанных вершин) от корня до вершины, экземпляры которой удовлетворяют условиям поиска.
Необходимо отметить, что программы, реализующие операции иерархической модели, существенно проще, чем аналогичные программы для сетевой модели, т.к. здесь много легче осуществлять навигацию по структуре. Целесообразность появления иерархической модели обусловлена, конечно, тем, что большинство организационных систем реального мира имеют иерархическую структуру (административное деление страны, организационная структура предприятия и т.п.). Соответствующее концептуальное представление также будет иметь иерархическую структуру и естественным образом может быть описано в терминах иерархической модели. В качестве недостатков иерархической модели можно назвать вышеуказанные недостатки сетевой.
СУБД, поддерживающие иерархическую модель, достаточно широко использовались на вычислительных системах IBM 360/370 (ЕС ЭВМ). В качестве примеров таких систем можно указать IMS, OKA и широко тиражируемую в СССР отечественную разработку ИНЕС. Примером иерархической СУБД для персональных ЭВМ является отечественная система НИКА (адаптация системы ИНЕС к IBM PC).
Достоинства иерархической модели:
• простота и естественность представления экономических данных;
• минимальный расход памяти по сравнению с другими моделями.
Недостатки иерархической модели:
• сложность отображения связей М : N без увеличения избыточности;
• сложность включения информации о новых объектах и удаления устаревших данных;
• доступ к данным возможен только через корень дерева, следовательно большое время поиска данных для некоторых запросов.

39. Сетевая модель данных
Это одна из наиболее ранних моделей данных СУБД. Типовая сетевая модель данных была предложена рабочей группой по базам данных (Data Base Task Group – DBTG) системного комитета CODASYL (Conference of Data System Languages), основными функциями которого были анализ известных фирменных систем обработки управленческих данных с единых позиций и в единой терминологии, обобщение опыта организации таких систем и разработка рекомендаций по созданию соответствующих систем. Структура данных сетевой модели определяется в терминах раздела 6.1 (элемент, запись, группа, групповое отношение, файл, база данных).
Реализация групповых отношений в сетевой модели осуществляется с использованием специально вводимых дополнительных полей - указателей (адресов связи или ссылок), которые устанавливают связь между владельцем и членом группового отношения. Запись может состоять в отношениях разных типов (1:1, 1:N, M:N). Заметим, что если один из вариантов установления связи 1:1 очевиден (в запись – владелец отношения, поля которой соответствуют атрибутам сущности, включается дополнительное поле – указатель на запись – член отношения), то возможность представления связей 1:N и M:N таким же образом весьма проблематична. Поэтому наиболее распространенным способом организации связей в сетевых СУБД является введение дополнительного типа записей (и соответственно, дополнительного файла), полями которых являются указатели.
Рассмотрим для примера представление группового отношения M:N. В модель вводится дополнительная группа (дополнительный вид записей). Элементы этой записи представляют собой указатели на две исходные группы и указатели на экземпляры рассматриваемой дополнительной записи, связывающие их в список (цепь), соответствующий M и (или) N членам группового отношения (рис. 6.1.).

Рис. 6.1.  Представление связей типа M:N
Представление связей 1:1, 1:M, N:1 является частным случаем связи типа M:N и осуществляется аналогично рассмотренному выше.
Заметим, что группа может быть членом более чем одного группового отношения. В этом случае вводится несколько дополнительных групп-указателей, а в группе – владельце отношений вводится несколько полей – указателей на дополнительные группы. Тогда множество записей (групп) и связей между ними образует некую сетевую структуру (ориентированный граф общего вида). Вершинами графа являются группы; дугами графа, направленными от владельца к члену группового отношения, – связи между группами.
Сетевая модель данных поддерживает все необходимые операции над данными, реализованные как действия со списковыми структурами. Сетевая модель данных является, вероятно, наиболее общей по возможностям представления концептуальной модели. По сути, любая ER-диаграмма без каких-либо изменений представляется средствами сетевой модели. К недостаткам сетевой модели обычно относят сложность получаемой на её основе концептуальной схемы и большую трудоемкость понимания соответствующей схемы внешним пользователем.
Рассмотрим пример записи части ER-диаграммы (СТУДЕНТ и ФАКУЛЬТЕТ) из предыдущей лекции в терминах сетевой СУБД. Для примера рассмотрим несколько экземпляров сущности СТУДЕНТ и сущности ФАКУЛЬТЕТ (рис. 6.2.).

Рис. 6.2.  Примеры экземпляров сущностей
Пусть студенты Иванов, Петров, Мишин учатся на факультете ВМК, Сидоров и Кашин на механико-математическом факультете. Тогдасетевая модель соответствующего фрагмента ER-диаграммы будет выглядеть следующим образом (рис. 6.3).

Рис. 6.3.  Пример сетевой модели концептуального представления
Заметим, что в дополнительном файле один из указателей не потребовался, так как рассматриваемая связь имеет тип 1:N, а не M:N. Значок × обозначает отсутствие дальнейшей связи.
Наиболее существенным недостатком сетевой модели является "жесткость" получаемой концептуальной схемы. Связи закреплены в записях в виде указателей. При появлении новых аспектов использования этих же данных может возникнуть необходимость установления новых связей между ними. Это требует введения в записи новых указателей, т.е. изменения структуры БД, и, соответственно, переформирования всей базы данных.
СУБД, поддерживающие сетевую модель, широко использовались на вычислительных системах серии IBM 360/370 (ЕС ЭВМ). В качестве примеров таких систем можно указать IDMS, UNIBAD (БАНК), и их аналоги СЕДАН, СЕТОР. На персональных компьютерах сетевые СУБД не получили широкого распространения. Примером сетевой СУБД для персонального компьютера является db_VISTA III. Отметим, что система db_VISTA реализована на языке С и поэтому является переносимой. Система может эксплуатироваться на ПЭВМ типа IBM PC, SUN, Macintosh.

Сетевые структуры данных
Если в отношении между данными порожденный элемент имеет более одного исходного, отношение называется сетевой структурой («сетью»): любой элемент может быть связан с любым числом других элементов. Сетевую структуру можно описать с помощью исходных и порожденных элементов. Для сетевых структур данных характерно отношение «многие-ко-многим», рис. 45.

Сетевая модель данных
Отличие сетевой модели от иерархической заключается в том, что в сетевой структуре любой элемент данных может быть связан с любым другим, то есть иерархическая модель является разновидностью сетевой. Различают простую и сложную сетевую структуру. В простой сетевой структуре между исходным и порожденными узлами реализуется связь 1:М. Сложной сетевой структурой называют такую схему, в которой присутствует хотя бы одна связь N : M.

40. Реляционная модель данных
Учитывая отмеченные в предыдущих разделах недостатки сетевых и иерархических моделей, можно сформулировать желательные требования к модели данных:
• модель должна быть понятна пользователю, не имеющему особых навыков в программировании;
• появление новых аспектов использования данных и необходимость введения новых связей не должны приводить к реструктуризации всей модели данных и базы данных в целом.
Моделью данных, удовлетворяющей вышеуказанным требованиям, является реляционная модель, часто называемая также табличной.
Основным используемым понятиям здесь является понятие отношения, представляемого в виде таблицы, столбцы которой соответствуют атрибутам сущности (структура строки таблицы аналогична структуре записи). Каждый атрибут может принимать определенное множество значений, называемое доменом. Строка таблицы с конкретными значениями полей здесь называется кортежем (соответствует понятию "экземпляр записи"). Поля таблицы предполагаются элементарными (неделимыми). Таким образом, понятие "таблица" здесь соответствует понятию "файл" модели данных. Первичный ключ здесь –минимальный набор атрибутов, однозначно идентифицирующий кортеж в отношении.
Групповое отношение может представляться двумя способами. При первом способе в таблицы, соответствующие группам – членам отношения, добавляются столбцы ключевых полей (атрибутов) другого члена отношения (связь описывается через ключевые атрибуты). При втором способе групповое отношение определяется как дополнительная группа (дополнительная таблица). Столбцами этой дополнительной таблицы являются ключи групп – членов отношения. Таким образом, при любом способе соответствующая модель данных представляет собой совокупность структур таблиц.
Рассмотрим пример записи ER-диаграммы (см. рис. 5.2.) в терминах реляционных баз данных.
Сначала представим таблицы, соответствующие сущностям.
Таблица СТУДЕНТ
Код Фамилия Дата рождения Место рождения
Таблица ФАКУЛЬТЕТ
Номер Название
Таблица СПЕЦИАЛЬНОСТЬ
Номер Название
Представим таблицы, описывающие связи.
Таблица "Студент учится на факультете"
Код студента Номер факультета
Таблица "Студент учится по специальности"
Код студента Номер специальности
Таблица "На факультете имеются специальности"
Номер факультета Номер специальности
Заметим, что здесь реализован вышеописанный второй способ представления групповых отношений. Очевидно, что можно построить много вариантов таблиц, представляющих соответствующую ER-диаграмму.
Для приведенных таблиц не указаны домены атрибутов. Отсутствие указания доменов приводит к неоднозначной интерпретации содержания таблицы. Например, две таблицы с одинаковыми атрибутами
Код студента Фамилия Дата рождения Место рождения
могут иметь разное смысловое значение и, соответственно, разное содержание (в одной таблице содержатся сведения о всех студентах факультета, в другой таблице сведения только о старостах факультета). Для устранения неоднозначной интерпретации в случае отсутствия указания доменов используют имя таблицы (СТУДЕНТ; СТАРОСТА)
Для формального описания таблицы используется теоретико-множественное понятие отношения.
Схемой отношения R называется перечень имен атрибутов отношения (соответствующих столбцам таблицы) с указанием доменов этих атрибутов и обозначается R(A1, A2, ..., An); {Ai}   Di, где {Ai} – множество значений, принимаемых атрибутом Ai(i=1,n).
Совокупность схем отношений, используемых для представления концептуальной модели, называется схемой реляционной базы данных, а текущие значения соответствующих отношений – реляционной базой данных.
В качестве основного недостатка реляционной модели можно указать дублирование информации при представлении связей.
Необходимо отметить, что большинство СУБД для персональных ЭВМ поддерживают именно реляционную модель данных. В качестве примеров таких наиболее распространенных СУБД можно указать все dBase-подобные системы, DB2, Paradox, Access, FoxPro, Oracle, MS SQL Server.

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

Реляционные модели
Первой формализованной и общепризнанной моделью данных была реляционная модель Е. Кодда. В этой модели выделялись - структурный, целостный и манипуляционный аспекты:
• структура данных - нормализованное N-арное отношение;
• средства манипуляции данными - совокупность  реляционной алгебры, основу которой   составляет теория множеств, и реляционного исчисления, основанного на логическом аппарате исчисления предикатов первого порядка;
• средства обеспечения целостности данных на уровне сущностей – любое отношение должно обладать первичным ключом) и на уровне ссылок – использование внешних ключей для связи отношений (внешний ключ в одном  отношении является первичным ключом другого отношения). Способы поддержки целостности ссылок:
 запрет удаления кортежа, если на них имеются ссылки ( сначала нужно удалить ссылающиеся кортежи, либо изменить значение их внешнего ключа);
 при удалении кортежа, на который имеются ссылки, во всех ссылающихся кортежах значение внешнего ключа автоматически становится неопределенным;
 при удалении кортежа из отношения, на которое ведет ссылка, из ссылающегося отношения автоматически удаляются все ссылающиеся кортежи (каскадное удаление).
Структуры данных в реляционной модели основываются на плоских нормализованных отношениях, ограничения целостности выражаются с помощью средств логики первого порядка и, наконец, манипулирование данными осуществляется на основе реляционной алгебры или равносильного ей реляционного исчисления. Реляционная модель данных опирается на строгий математический аппарат теории множеств, отношений и логики первого порядка.
Достоинства реляционных баз данных:
• возможность моделирования предметных областей на достаточно точном и интуитивно понятном уровнях с помощью небольшого набора абстракций;
• простой и одновременно мощный математический аппарат(теория множеств, математическая логика), обеспечивающий теоретический базис реляционного подхода к организации баз данных;
• непроцедурное манипулирование данными (без необходимости знания конкретной физической организации баз данных во внешней памяти).
Недостатками реляционных систем являются ограниченность реляционных моделей (следствие их простоты); невозможность адекватного отражения семантики предметной области средствами реляционной модели.

Основные термины:
1) тип данных - соответствует типам данных в языках программирования (символьные, числовые данные, битовые строки, специализированные числовые данные, дата, время);
2) домен - базовый тип данных, к которому относятся элементы домена, а также логическое выражение, применяемое к элементу типа данных (если логического выражения дает истина, элемент данных является элементом домена);
3) атрибут - свойство (реквизит, поле) некоторого объекта или сущности, принадлежащий домену;
4) схема отношений -  именованное множество пар {имя атрибута, имя домена/типа данных)}. Степень  (арность) схемы отношения – мощность этого множества;
5) схема БД - набор именованных схем отношений;
6) кортеж - множество пар {имя атрибута, значение}, имена атрибутов принадлежат схеме отношения, значения атрибутов является допустимыми значениями домена данного атрибута (типа данных). Степень (арность) кортежа - число элементов в нем, совпадает с арностью схемы отношения;
7) первичный ключ – набор атрибутов, значения которых однозначно определяют кортеж отношения;
8) отношение – множество кортежей, соответствующих одной схеме отношения (обычное представление - таблица, заголовок которой - схема отношения, строки - кортежи).
9) реляционная БД – набор отношений, имена которых совпадают с именами схем отношений в схеме БД.
Свойства отношений:
• отсутствие кортежей-дубликатов (множества не содержат одинаковые элементы);
• наличие первичного ключа отношения, обеспечивающего целостность БД;
• отсутствие упорядоченности кортежей;
• отсутствие упорядоченности атрибутов;
• атомарность значений атрибутов (основа нормализации отношений - 1 нормальная форма).

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