ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
Modelagem de processos baseados em restrições: uma
comparação entre abordagens declarativas
Sauro Schaidt, Gustavo Dering Barddal, Eduardo Alves Portela Santos, Agnelo
Denis Vieira, Eduardo de Freitas Rocha Loures
PPGEPS e PPGTS – Pontifícia Universidade Católica do Paraná (PUCPR) Escola
Politécnica - 80.215-901 – Curitiba – PR – Brasil.
gustavo.barddal, eduardo.portela, agnelo.vieira, eduardo.loures,
sauro.schaidt}@pucpr.br
Abstract. Constraints based processes are modeled from a set of rules that
restrain their behavior to certain limits. The appropriate way to model such
processes is by declarative languages. Any language, ultimately, can be
converted in an automaton describing the allowed events sequences of a
process. The goal of this paper is to start a comparing between the automata
generated by three declarative languages: Declare, DCRGraphs and
Supervisory Control Theory (SCT). The comparing has been done from an
oncology treatment process modeling using the three approaches.
Resumo. Processos baseados em restrições são modelados a partir de um
conjunto de regras que restringem o seu comportamento a certos limites. A
forma adequada de modelar tais processos é através de linguagens
declarativas. Qualquer linguagem, em última análise, pode ser convertida em
um autômato que descreve as sequencias de eventos permitidas de um
processo. O objetivo deste artigo é iniciar uma comparação entre os
autômatos gerados por três linguagens declarativas: Declare, DCRGraphs e
Teoria de Controle de Supervisório (TCS). Esta comparação foi realizada a
partir da modelagem de um processo de tratamento oncológico com cada uma
das três abordagens.
1. Introdução
Dentre os diversos tipos de processos de negócio, dois são de particular interesse neste
artigo: os processos denominados fortemente estruturados (ou repetitivos) e os
processos baseados em conhecimento [Reichert et al. 2012]. Os processos baseados em
conhecimento podem ser ainda classificados em processos baseados em restrições e
processos baseados em dados. Processos fortemente estruturados são caracterizados pela
estruturação rígida da ordem entre as suas atividades com poucas alternativas de
execução para o usuário final, enquanto processos baseados em conhecimento são
caracterizados pela influência do usuário na determinação da sequência adequada do
processo [Van Der Aalst et. al 2009].
Os modelos imperativos são associados aos processos fortemente estruturados e os
modelos declarativos são associados aos processos baseados em conhecimento [Reichert
et al. 2012] [Pesic 2008] [Fahland et. al 2009, 2010]. Modelos imperativos impõem uma
ordem rígida entre as atividades enquanto modelos declarativos permitem especificar
58
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
poucas regras entre as atividades [Pesic 2008]. Como exemplos de modelos imperativos
na representação de processos de negócio destacam-se o BPMN e as Redes de Petri
[Reichert et al. 2012]. Como exemplos de modelos declarativos destacam-se o
DECLARE [Pesic et. al. 2007], a Teoria de Controle Supervisório (TCS) [Ramadge et
al. 1987, 1989], o Dynamic Condition Response Graphs (DCRGraphs) [Hildebrandt et
al. 2011, 2012] entre outros.
Este artigo apresenta os resultados preliminares de um projeto de pesquisa que investiga
diferentes abordagens para modelagem de processos baseados em restrições. Em
particular, pretende-se comparar as linguagens admissíveis que descrevem as sequencias
de eventos que um processo pode executar empregando três abordagens distintas,
(DCRGraphs, Declare e TCS) na modelagem de um mesmo processo. As sequencias de
eventos são representadas por autômatos de forma que o objetivo da comparação é
identificar se os autômatos gerados por DCRGraphs, Declare e TCS possuem alguma
similaridade. Considerada a importância de linguagens declarativas e processos
baseados em restrições, a importância de tal estudo está no fato de tentar evidenciar
aspectos em comum entre as abordagens escolhidas, suas características e inter-relações.
A comparação das linguagens admissíveis visa estabelecer o grau de flexibilidade das
linguagens declarativas correspondentes. Pretende-se verificar se existe sequência de
eventos permitida em uma linguagem e não permitida em outra. Dessa forma, para um
mesmo conjunto de restrições, é possível que uma linguagem seja mais restritiva (menos
flexível) que outra.
2. Exemplo de aplicação
O processo escolhido para análise corresponde a um processo de tratamento oncológico
hospitalar [Hildebrandt et al. 2011]. As Tabelas 1 e 2 apresentam respectivamente as
três atividades que constituem o processo e as quatro restrições impostas ao mesmo. O
médico deve preencher e assinar a prescrição médica enquanto o enfermeiro é
responsável por ministrar a medicação prescrita pelo médico e estas ações devem
ocorrer obedecendo algumas restrições de ordem.
3. Modelagem utilizando Declare, DCRGraphs e TCS
A seguir será apresentada a modelagem do processo de tratamento de acordo com os três
modelos citados anteriormente.
3.1. Declare
Declare é um sistema de modelagem e execução de processos baseados em restrições
[Pesic et. al. 2008]. Utiliza a Lógica Linear Temporal (LTL) para representar as
restrições. Declare oferece um conjunto com mais de 20 modelos de restrições. Os
modelos gráficos de atividades e restrições do Declare são convertidos em autômatos
para suporte a execução e verificação do processo (conflito, bloqueio, atividades mortas)
[Pesic et. al. 2007][Pesic 2008].
A Figura 1 apresenta o processo de tratamento oncológico hospitalar modelado no
Declare. Para modelar as quatro restrições do processo foram utilizados dois modelos de
restrições disponíveis: precedence(a,b) e reponse(a,b). O modelo precedence(a,b)
estabelece que todas as instâncias de execução de b só poderão ocorrer depois que a
59
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
tiver sido executado pelo menos uma vez [Pesic 2008] – este modelo foi usado para
modelar as restrições R1 = precedence(a1,a2) e R4 = precedente(a2, a3).
Tabela 1. Atividades do processo de tratamento oncológico
Nome
a1
prescrever medicação
a2
assinar prescrição
a3
dar medicação
Descrição
Registrar no histórico do paciente quais medicamentos devem ser
ministrados a ele.
Assinar as prescrições já emitidas.
Medicar o paciente de acordo com a prescrição emitida e
assinada pelo médico.
Tabela 2. Restrições do processo de tratamento oncológico
Nome
Descrição
R1
prescrever medicação (a1) deve ser executada antes que assinar prescrição (a2)
seja executada.
R2
prescrever medicação (a1) não precisa ser executada, mas se prescrever
medicação (a1) for executada então assinar prescrição (a2) deve ser executada.
R3
prescrever medicação (a1) não precisa ser executada, mas se prescrever
medicação (a1) for executada então dar medicação (a3) deve ser executada
R4
assinar prescrição (a2) deve ser executada antes que dar medicação (a3) seja
executada
Figura 1. Processo de tratamento oncológico modelado no Declare
O modelo response(a,b) estabelece que a não precisa ser executada, mas se ocorrer uma
sequência de uma ou mais execuções de a então b deve ser executada depois, pelo
menos uma vez [Pesic 2008] - este modelo foi usado para modelar as restrições R2 =
response(a1, a2) e R3 = response(a1, a3). Cada atividade no Declare é composta de três
eventos: iniciar (si), completar (ci) e cancelar (xi). Assim, uma atividade a1 terá os
eventos s1, c1 e x1. A Figura 2 apresenta o autômato gerado por Declare, para a
modelagem apresentada na Figura 1, com as transições rotuladas com os eventos do
processo. A linguagem reconhecida deste autômato engloba as sequencias de eventos
que levam a um estado marcado (1 e 6). As sequencias que levam ao estado não coacessivel 2 representam sequencias que violam as restrições, por exemplo, a sequencias
s1.s2 e s1.c1.s3 levam ao estado 2 e portanto violam as restrições.
3.2. DCRGraphs
No modelo DCRGraphs cada atividade é uma unidade atômica de forma que a sua
execução é representada por um único evento com significado equivalente a sua
60
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
finalização. As restrições impostas ao processo são representadas por relações sobre o
conjunto de eventos [Hildebrandt et al. 2011, 2012]. A Figura 3 apresenta o processo de
tratamento oncológico hospitalar modelado no ambiente Process Model [Hildebrandt et
al. 2011]. A restrição R1 é modelada usando a operação causalidade(a1,a2) que
especifica que a deve preceder b; R2 é modelada usando a operação resposta(a1,a2) que
especifica que se a é executada então b deve ser executada; R3 foi modelada usando a
operação resposta(a1,a3), e R4 foi modelada usando a operação causalidade(a2,a3).
Figura 2. Autômato gerado por Declare
Os autômatos gerados por DCRGraph possuem transições cujos rótulos são o próprio
nome da atividade [Hildebrandt et al. 2011]. Isso significa que a ocorrência de uma
transição em um autômato gerado pelo DCRGraph é equivalente a execução completa
de uma atividade ai, o que por sua vez é equivalente a ocorrência do evento completar
(ci) da mesma atividades ai quando modelada no Declare. Como há equivalência entre
as nomenclaturas e por questão de padronização, adotamos a nomenclatura ci para
rotular os eventos dos autômatos gerados pelo DCRGraphs. A Figura 4 apresenta o
autômato gerado por DCRGraphs para a modelagem apresentada na Figura 3. Portanto,
para sair do estado s0 e atingir o estado s1, é necessário que ocorra o evento c1, ou seja,
que a atividade a1 seja completada. O mesmo raciocínio serve para as demais
transições. A linguagem reconhecida deste autômato engloba as sequencias de eventos
que levam a um estado marcado (s0 e s4), que correspondem aquelas sequencias que
não violam as restrições impostas.
3.3. Teoria de Controle Supervisório
A Teoria de Controle Supervisório (TCS) foi desenvolvida como uma metodologia
formal para a síntese automática de controladores para sistemas a eventos discretos
(SED). Nesta teoria supõe-se que um conjunto de atividades tem um comportamento
que possa violar restrições do sistema, de forma que o comportamento do sistema deve
ser modificado através de um agente de controle denominado supervisor. O supervisor
mapeia a sequência de eventos que ocorreram no processo e atua sobre o conjunto de
atividades impedindo a execução de eventos a fim de que o sistema não viole as
restrições impostas [Ramadge et al. 1987, 1989]. Para aplicar a TCS na modelagem de
processos baseados em restrições é necessário obter dois modelos: o modelo das
atividades que constituem o processo (G) e o modelo das especificações que restringem
o comportametno do mesmo (E) [Ramadge et al. 1989] [Schaidt et al. 2013]. Cada
61
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
atividade pode ser representada por um autômato de dois estados: o estado "1"
representa que a atividade está sendo executada e "0" a atividade está aguadando a
entrada de uma instância (inativa). A Figura 5 apresenta o autômato que representa uma
atividade, onde i é um subíndice que identifica a atividade em questão. Os eventos
apresentam o seguinte siginificado: si - início da atividade, ci - conclusão da atividade,
xi - cancelamento da atividade. A TCS estabelece o conceito de controlabilidade de
eventos. Um evento é controlável se sua ocorrrência pode ser impedida pelo supervisor,
e não-controlável em caso contrário. Considera-se controlável apenas o evento si.
Figura 3. Processo de tratamento oncológico modelado no DCRGraph
Figura 4. Autômato gerado por DCRGraph
Figura 5. Autômato que representa a atividade ti
Cada uma das três atividades, a1, a2 e a3 do processo de tratamento oncológico é
representada por um autômato correspondente. Para a construção dos autômatos
utilizou-se o software IDES [Rudie 2006]. A Figura 6 apresenta os autômatos das
atividades. O produto síncrono calculado através do IDES gerou o autômato G com 8
estados e 24 transições. Cada restrição deve ser representada por um autômato [Santos
et al. 2012] [Schaidt et al. 2013]. A Figura 7 apresenta os autômatos de cada uma das
quatro restrições e o produto síncrono entre estas denominado R.
Figura 6. Autômatos das atividades e o produto síncrono resultante
62
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
Figura 7. Autômatos das restrições e produto síncrono correspondente
4. Comparação de resultados
O comportamento apresentado pelo processo quando submetido a um conjunto de
restrições corresponde a uma linguagem regular que por sua vez pode ser representada
através de autômato [Hopcroft et al. 2002]. Neste artigo, a comparação do
comportamento do processo quando modelado segundo as diferentes abordagens foi
realizada através da comparação dos respectivos autômatos gerados. Os autômatos
analisados foram o da Figura 2 (Declare), da Figura 4 (DCRGraphs) e o autômato R da
Figura 7 (TCS).
Sobre a linguagem representada pelo autômato Declare foi realizada a operação de
projeção sobre o alfabeto {c1, c2, c3} com o objetivo de excluir as possíveis sequências
de eventos constituídas por eventos em {s1, x1, s2, x2, s3, x3} preservando, contudo, as
sequências constituídas por eventos em {c1, c2, c3}. Esta operação é necessária para
poder comparar o resultado obtido com o Declare e o DCRGraphs, pois neste último o
modelo do processo considera apenas os eventos {c1, c2, c3}. O resultado desta
operação é representado pelo autômato P_Declare (Figura 8). Deste autômato foram
excluídos os estados que não são co-acessíveis [Hopcroft et al. 2002]. Estados que não
são co-acessíveis (a partir dos quais não é possível atingir um estado marcado)
representam uma situação de bloqueio do sistema. Durante a execução do processo o
sistema computacional Declare impede a ocorrência de eventos que conduzam a tais
estados, desta forma a representação dos mesmos é desnecessária. O resultado desta
operação resulta no autômato TP_Declare (Figura 8).
A Teoria de linguagens e autômatos estabelece que dois autômatos são equivalentes
quando reconhecem a mesma linguagem e que existe uma representação única para tais
autômatos que emprega um número mínimo de estados. Este é denominado autômato
mínimo. Sobre o autômato TP_Declare foi realiza a operação de minimização
resultando no próprio autômato. Sobre o autômato DCRGraphs foi realizada a operação
de minimização resultando no autômato M_DCRGraphs (Figura 9).
63
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
Figura 8. Autômatos P_Declare e TP_Declare
Figura 9. Autômato M_DCRGraphs
Analisando os autômatos TP_Declare, M_DCRGraphs e TCS (autômato R da Figura 7)
concluímos que eles são isomorfos e que portanto reconhecem a mesma linguagem. O
autômato TCS utilizado é o produto síncrono das restrições apresentadas na Figura 7, o
que nos permite concluir que, para este caso em particular, podemos utilizar tanto o
autômato TP_Declare como o autômato M_DCRGraphs como especificação para
sintetizar o autômato do supervisor na abordagem TCS. Esta análise, no entanto, ainda
não pode ser generalizada para todos os modelos de processos por não termos uma
comprovação formal de que tal equivalência é válida para o caso geral.
5. Conclusão e trabalhos futuros
O presente artigo apresenta a modelagem de um processo de tratamento oncológico
usando três abordagens distintas, Declare/LTL, DCRGraphs e TCS, a fim de comparar
os autômatos gerados. Os resultados apontaram que, especificamente para o caso do
processo de tratamento oncológico, aplicando um conjunto de operações conhecidas
sobre os autômatos Declare e sobre o autômato DCRGraphs, obtém-se um autômato
igual ao produto síncrono das restrições na abordagem TCS. Este resultado não deve ser
generalizado ainda, dependendo de futuro estudo para se compreender se tal
generalização pode ser feita ou não. Se tal generalização for possível, então pode haver
uma equivalência entre estas três abordagens e isso deve conduzir a um estudo mais
avançado para verificar se, de fato, há ou não diferenças no poder de representação ou
de execução de cada uma.
Referências
Fahland, D., Lubke, D., Mendling, J., Reijers, H., Weber, B., e Weidlich, M., Zugal, S.,
2009, “Declarative versus imperative process modeling languages: The issue of
64
ISSN 2177-885X (Vol. 2) WBPM
X SBSI - Londrina, Brasil - Maio 2014
understandability”, In: Enterprise, Business-Process and Information Systems Modeling,
Springer, 353-366.
Fahland, D., Mendling, J., Reijers, H.A., Weber, B., Weidlich, M., e Zugal, S., (2010),
“Declarative versus imperative process modeling languages: the issue of
maintainability,” In: Business Process Management Workshops, Springer, 477-488.
Hildebrandt, T. T., e Mukkamala, R. R., 2011, “Declarative Event-Based Workflow as
Distributed Dynamic Condition Response Graphs,” Electronic Proceedings in
Theoretical Computer Science, 69, 59-73. doi:10.4204/EPTCS.69.5.
Hildebrandt, T., Mukkamala, R., e Slaats, T., 2012,” Nested Dynamic Condition
Response Graphs,” In F. Arbab & M. Sirjani (Eds.), Fundamentals of Software
Engineering SE - 23, vol. 7141, 343-350. Springer Berlin Heidelberg. doi:10.1007/9783-642-29320-7_23.
Hopcroft, J.E.; Motwani, R.; Ullman, J.D.; 2002. Introdução à Teoria de Autômatos,
Linguagens e Computação. Ed. Campus.
Pesic, M., Schonenberg, H., van der Aalst, W.M., 2007, “Declare: Full support for
loosely structured processes,” In: Enterprise Distributed Object Computing Conference,
EDOC 2007, 11th IEEE International, 287-287.
Pesic, M., 2008, “Constraint-based workflow management systems: shifting control to
users,” Ph.D. dissertation, The Eindhoven University of Technology.
Ramadge, P.J., e Wonham, W.M., 1987, “Supervisory control of a class of discrete
event processes,” SIAM journal on control and optimization 25(1), 206-230.
Ramadge, P.J., Wonham, W.M., 1989, “The control of discrete event systems,”
Proceedings of the IEEE 77(1), 81-98.
Reichert, M.U., e Weber, B., 2012, “Enabling flexibility in process-aware information
systems: challenges, methods, technologies”, Springer.
Rudie, K. “The Integrated Discrete-Event Systems Tool”. Proceedings of the 8th
International Workshop on Discrete Event Systems, Ann Arbor, Michigan, USA, p. 1012, Julho 2006.
Santos, E., Francisco, R., Vieira, A., Loures, E., e Busetti, M., 2012, “Modeling
business rules for supervisory control of process-aware information systems,” In
Business Process Management Workshops (BPM 2011) - Lecture Notes in Business
Information Processing, Springer, number 100, 447-458.
Schaidt, S., Vieira, A.D., Loures, E.d.F.R., Santos, E.A.P., 2013, “Processos baseados
em Restrições: uma Aplicação da Teoria de Controle Supervisório,” 9° Simpósio
Brasileiro de Sistemas de Informação, João Pessoa –PB- Brasil, Maio/2013.
Van Der Aalst, W.M., Pesic, M., e Schonenberg, H., 2009, “Declarative workflows:
Balancing between flexibility and support,” Computer Science-Research and
Development, 23(2), 99-113.
65