Анализ сетей Петри с использованием дерева достижимости.

 

Анализ ограниченности: Сеть Петри ограничена тогда и только тогда, когда символ ω отсутствует в дереве достижимости. Если символа ω нет, то можно определить границу числа меток в позициях путем перебора вершин дерева достижимости.

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

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

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

• активность уровня 0, если он никогда не может быть активирован (пассивный или «мёртвый» переход);

• активность уровня 1, если существует состояние (достижимое из начального), в котором он активирован;(«потенциально живой» переход)

• активность уровня 2, если для всякого целого n существует последовательность срабатывания переходов, в которой данный переход присутствует по крайней мере n раз;

• активность уровня 3, если существует бесконечная последовательность срабатывания переходов, в которой данный переход присутствует неограниченно часто;

• активность уровня 4, если для любого достижимого состояния существует последовательность срабатываний, приводящая в такое состояние, в котором этот переход активирован (активный или «живой» переход).

 

Реляционная алгебра. Отношения, кортежи, атрибуты, домены.

 

Реляционная алгебра — формальная система манипулирования отношениями в реляционной модели данных.

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

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

Отношение — фундаментальное понятие реляционной модели данных. По этой причине модель и называется реляционной.

N-арным отношением R называют подмножество декартового произведения множеств , не обязательно различных. Исходные множества D1,D2,...,Dn называют в модели доменами.

(Другое определение: Отношением называется некоторое подмножество декартового произведения одного или нескольких доменов)

Под доменом будем понимать некоторое множество значений. Домен - множество значений данных какого-либо типа. Каждый атрибут может быть определен на каком-либо одном домене. На одном домене может быть определено несколько атрибутов.

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

 

Реляционная алгебра. Операции реляционной алгебры.

 

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

Основные восемь операций реляционной алгебры были предложены Э.Коддом.

· Объединение

· Пересечение

· Вычитание

· Декартово произведение

· Выборка

· Проекция

· Соединение

· Деление

Проекция

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

 

Выборка

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

 

Умножение

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

 

Соединение и естественное соединение

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

 

Пересечение и вычитание.

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