Дипломная работа - Тырин А.А. (АП-91). Назначение и область применения
 Скачать 0.55 Mb.
|
4.4 Математическое и информационное обеспечение4.4.1 Теория конечных автоматовКонечным автоматом называется формальная система M = (Q, Σ, δ, q0, F), где Q – конечное непустое множество состояний; Σ – конечный входной алфавит; δ – отображение типа Q × Σ → Q; q0 ∈ Q – начальное состояние; F ⊆ Q – множество конечных состояний [17]. Конечный автомат состоит из конечного управления и входной ленты, разбитой на ячейки. В каждой ячейке записан один символ из входного алфавита Σ, и все они образуют конечную входную цепочку. Конечное управление первоначально находится в состоянии q0 и сканирует крайнюю левую ячейку ленты. По мере чтения входной цепочки слева направо автомат переходит в другие состояния из множества Q. Если, прочитав входную цепочку, автомат оказывается в некотором конечном состоянии из множества F, то говорят, что он принял ее. Множество цепочек, принимаемых конечным автоматом, называется языком, распознаваемым данным конечным автоматом. Конечные автоматы подразделяются на детерминированные и недетерминированные: Детерминированным конечным автоматом называется такой автомат, в котором нет дуг с меткой ε (неопределённым символом) и из любого состояния по любому символу возможен переход в точности в одно состояние. Все остальные конечные автоматы являются недетерминированными. Конечные автоматы описывают с помощью двух способов [24]: Таблица переходов Таблица переходов – табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу – один допустимый входной символ. В ячейке на пересечении строки и столбца записывается состояние, в которое должен перейти автомат, если в данном состоянии он считал данный входной символ. На рисунке 4.2 приведен пример описания конечного автомата с помощью таблицы переходов.
Рис. 4.2 Таблица переходов Диаграмма состояний (или иногда граф переходов) – графическое представление множества состояний и функции переходов. Представляет собой размеченный ориентированный граф, вершины которого – состояния конечного автомата, дуги – переходы из одного состояния в другое, а метки дуг – символы, по которым осуществляется переход из одного состояния в другое. Если переход из одного состояния в другое может быть осуществлен по одному из нескольких символов, то все они должны быть надписаны над дугой диаграммы. На рисунке 4.3 изображена диаграмма состояний конечного автомата, который был описаны выше с помощью таблицы переходов.  Рис. 4.3 Диаграмма состояний Для решения поставленной задачи систему маршрутизации запросов можно интерпретировать с помощью конечного автомата следующим образом [31]: Конечное непустое множество состояний Q – состояния, которые может принимать запрос, проходя по схеме маршрутизации; Конечный входной алфавит Σ – набор возможных пользователям действий для перемещения запроса из одного состояния в другое; Функция переходов δ – набор переходов, связывающих состояния межу собой; Начальное состояние q0 – состояние, в котором пользователь создаёт запрос; Множество конечных состояний F – состояние «обработан», обозначающее правильность вносимых изменений и позволяющее фактическую запись в базу данных. В данном случае множество конечных состояний будет состоять из одного элемента. Главным отличием работы схемы маршрутизации от традиционного конечного автомата, будет являться отсутствие заранее составленной входной цепочки. Группа пользователей не может заранее знать, какие действия они будут совершать с запросом и в какой последовательности. В данном случае конечный автомат будет совершать анализ действия и последующий переход в требуемое состояние по факту получения этого действия. 4.4.2 МетаязыкМетаязык – это язык, используемый для выражения суждений о другом языке, языке-объекте. С помощью метаязыка изучают структуру выражений языка-объекта, его свойства и отношения к другим языкам. Изучаемый язык называется также предметным языком по отношению к данному метаязыку. Как предметный язык, так и метаязык могут быть естественными языками. Метаязык может отличаться от языка-объекта, но может и совпадать с ним или отличаться лишь частично, например специальной терминологией. Другими словами метаязык – это «сверхязык», предназначенный для описания языка. В информатике метаязыком принято считать дополнительные данные, служащие для описания уже имеющихся. В математической логике метаязык используется для определения истинности или ложности выражения предметного языка. Примером метаязыка может служить русский язык в учебнике английского языка для русских, в то время как английский язык будет являться его предметным языком. Одной из задач данной дипломной работы является создание механизма описания правил для остановки запроса в конкретном состоянии схемы маршрутизации. Этот механизм будет реализован с помощью метаязыка, где предметным языком будут являться сведения о параметрах и свойствах запроса. Для вычисления истинности или ложности выражения метаязык должен обладать операторами, которые однозначно смогут определить значение описанного условия. Необходимо также создать интерпретатор для разбора описанного условия на метаязыке [25]. В основе работы интерпретатора лежит теория конечных автоматов, о которой написано выше. Интерпретатор разбивает выражение на условия, соединенные друг с другом булевскими операторами «и», «или», «не», а также учитывает скобки для определения порядка вычисления логических действий. 4.4.3 Система управления базами данныхВся информация об объектах системы АСОТ, в том числе и графическая, содержится в базах данных. Манипуляции с этой информацией происходят с помощью системы управления базами данных. База данных – представленная в объективной форме совокупность самостоятельных материалов (статей, расчётов, нормативных актов, судебных решений и иных подобных материалов), систематизированных таким образом, чтобы эти материалы могли быть найдены и обработаны с помощью электронной вычислительной машины [6]. Система управления базами данных (СУБД) – совокупность программных и лингвистических средств общего или специального назначения, обеспечивающих управление созданием и использованием баз данных [5]. СУБД выполняет следующие функции: управление данными во внешней памяти; управление данными в оперативной памяти; журнализация изменений, резервное копирование и восстановление базы данных после сбоев; поддержка языков БД. По модели данных СУБД подразделяются на следующие виды: Иерархические Сетевые Реляционные Объектно-ориентированные Объектно-реляционные Транзакция – это последовательность операций над БД, рассматриваемых СУБД как единое целое. Либо транзакция успешно выполняется, и СУБД фиксирует изменения БД, произведенные этой транзакцией, во внешней памяти, либо ни одно из этих изменений никак не отражается на состоянии БД [3]. Одним из основных требований к СУБД является надежность хранения данных во внешней памяти. Под надежностью хранения понимается то, что СУБД должна быть в состоянии восстановить последнее согласованное состояние БД после любого аппаратного или программного сбоя. Обычно рассматриваются два возможных вида аппаратных сбоев: так называемые мягкие сбои, которые можно трактовать как внезапную остановку работы компьютера (например, аварийное выключение питания), и жесткие сбои, характеризуемые потерей информации на носителях внешней памяти. Примерами программных сбоев могут быть: аварийное завершение работы СУБД (по причине ошибки в программе или в результате некоторого аппаратного сбоя) или аварийное завершение пользовательской программы, в результате чего некоторая транзакция остается незавершенной [11]. Первую ситуацию можно рассматривать как особый вид мягкого аппаратного сбоя; при возникновении последней требуется ликвидировать последствия только одной транзакции. Понятно, что в любом случае для восстановления БД нужно располагать некоторой дополнительной информацией. Другими словами, поддержание надежности хранения данных в БД требует избыточности хранения данных, причем та часть данных, которая используется для восстановления, должна храниться особо надежно. Наиболее распространенным методом поддержания такой избыточной информации является ведение журнала изменений БД. Журнал – это особая часть БД, недоступная пользователям СУБД и поддерживаемая с особой тщательностью, в которую поступают записи обо всех изменениях основной части БД. Иногда поддерживаются две копии журнала, располагаемые на разных физических дисках для увеличения надёжности. В разных СУБД изменения БД журнализуются на разных уровнях: иногда запись в журнале соответствует некоторой логической операции изменения БД (например, операции удаления строки из таблицы реляционной БД), иногда – минимальной внутренней операции модификации страницы внешней памяти; в некоторых системах одновременно используются оба подхода [27]. Во всех случаях придерживаются стратегии "упреждающей" записи в журнал, так называемого протокола Write Ahead Log – WAL. Эта стратегия заключается в том, что запись об изменении любого объекта БД должна попасть во внешнюю память журнала раньше, чем измененный объект попадет во внешнюю память основной части БД. Известно, что если в СУБД корректно соблюдается протокол WAL, то с помощью журнала можно решить все проблемы восстановления БД после любого сбоя. Для работы с базами данных используются специальные языки, называемые языками баз данных. В современных СУБД обычно поддерживается единый интегрированный язык, содержащий все необходимые средства для работы с БД, начиная от ее создания, и обеспечивающий базовый пользовательский интерфейс с базами данных. Стандартным языком наиболее распространенных в настоящее время реляционных СУБД является язык SQL (Structured Query Language). Прежде всего, язык SQL позволяет определять схему реляционной БД и манипулировать данными. При этом именование объектов БД (для реляционной БД – именование таблиц и их столбцов) поддерживается на языковом уровне в том смысле, что компилятор языка SQL производит преобразование имен объектов в их внутренние идентификаторы на основании специально поддерживаемых служебных таблиц-каталогов. Внутренняя часть СУБД (ядро) вообще не работает с именами таблиц и их столбцов. Наконец, авторизация доступа к объектам БД производится также на основе специального набора операторов SQL. Идея состоит в том, что для выполнения операторов SQL разного вида пользователь должен обладать различными полномочиями. Пользователь, создавший таблицу БД, обладает полным набором возможных действий для работы с этой таблицей. В число этих действий входит возможность передачи всех или части полномочий другим пользователям. Ограничение возможностей пользователей описываются в специальных таблицах-каталогах, а их контроль поддерживается на языковом уровне. |
