ads:
1.
FUNDAÇÃO EDSON QUEIROZ
UNIVERSIDADE DE FORTALEZA
CENTRO DE CIÊNCIAS TECNOLÓGICAS
Frank Stefan Araújo de Alencar
SESAMO
Um Controlador de Concorrência que Implementa a Serialidade
Semântica de Forma Descentralizada em Sistemas de Bancos de
Dados Múltiplos com Suporte à Mobilidade
Fortaleza-CE
Novembro / 2005
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
1.
FUNDAÇÃO EDSON QUEIROZ
UNIVERSIDADE DE FORTALEZA
CENTRO DE CIÊNCIAS TECNOLÓGICAS
Frank Stefan Araújo de Alencar
SESAMO
Um Controlador de Concorrência que Implementa a Serialidade
Semântica de Forma Descentralizada em Sistemas de Bancos de
Dados Múltiplos com Suporte à Mobilidade
Dissertação apresentada ao Corpo Docente
do Mestrado em Informática Aplicada da
Universidade de Fortaleza como parte dos
requisitos necessários para a obtenção do
Título de Mestre em Informática Aplicada,
na linha de pesquisa Banco de Dados.
Orientador: Prof. Ângelo Roncalli de A. Brayner, Dr-Ing.
Fortaleza-CE
Novembro / 2005
ads:
- iii -
SESAMO
Um Controlador de Concorrência que Implementa a Serialidade
Semântica de Forma Descentralizada em Sistemas de Bancos de
Dados Múltiplos com Suporte à Mobilidade
Data de Aprovação:
Banca Examinadora:
Prof. Ângelo Roncalli Alencar Brayner, Dr.-Ing.
(Universidade de Fortaleza – UNIFOR) - Orientador
Prof. Javam de Castro Machado, Docteur
(Universidade Federal do Ceará – UFC)
Prof. André Luís Vasconcelos Coelho, D.Sc.
(Universidade de Fortaleza – UNIFOR)
- iv -
FRANK STEFAN ARAÚJO DE ALENCAR, SESAMO – Um Controlador de
Concorrência que Implementa a Serialidade Semântica de Forma Descentralizada em
Sistemas de Bancos de Dados Múltiplos com Suporte à Mobilidade. Fortaleza: Universidade
de Fortaleza (UNIFOR). Mestrado em Informática Aplicada. Dissertação de Mestrado. 2005.
PERFIL DO AUTOR: Tecnólogo em Processamento de Dados (Universidade Federal do
Ceará - UFC, 1987), Bacharel em Administração de Empresas (Universidade Estadual do
Ceará – UECE, 1991), Especialista em Informática (Universidade Federal do Ceará – UFC,
1997).
RESUMO
Muitas propostas de controladores de concorrência distribuídos para SBDMs com
suporte à computação móvel violam a consistência dos dados ou a autonomia dos SBDCs,
devido, respectivamente, à flexibilização ou imposição da Serialidade como critério de
controle de concorrência de transações globais. Esta dissertação propõe o SESAMO, que é
um controlador de concorrência distribuído para SBDMs com suporte à mobilidade.
SESAMO é baseado na identificação de que um SBDM com suporte à mobilidade, cujo
controle de concorrência de transações globais é realizado pela execução simultânea de
múltiplos controladores de concorrência autônomos que implementam o critério de correção
da Serialidade Semântica, preserva a consistência dos dados e a autonomia dos SBDs-
componentes. SESAMO pode proporcionar um alto grau de concorrência, conforme ficou
evidenciado nos resultados experimentais.
ÍNDICE PARA CATÁLOGO SISTEMÁTICO:
1.Banco de Dados
2.Sistema de Banco de Dados Múltiplo
3.Computação móvel
4.Gerenciamento de Transações
5.Controle de Concorrência
- v -
Dedicatória
Aos meus pais Jean e Yélita, por serem os grandes
responsáveis pela formação do cidadão que hoje sou.
À minha esposa Clícia, por seu apoio e incentivos nos
momentos importantes de minha vida, tal como foi a
realização deste trabalho.
Aos meus filhos Pedro e Danilo, pela compreensão da minha
ausência nos momentos dedicados a este trabalho.
- vi -
Agradecimentos
Ao Prof. Dr. Ângelo Brayner, por todos os momentos de orientação, confiança, apoio e
incentivo, além das críticas construtivas que recebi durante esta jornada. Agradeço também
pela seriedade e pelo grau de exigência que demonstrou durante o desenvolvimento deste
trabalho, no sentido de produzir um resultado de alto nível técnico.
Aos Profs. que compuseram a banca examinadora desta dissertação, Dr. André Coelho e
Dr. Javam Machado, por seus valiosos questionamentos sobre este trabalho, os quais foram de
grande importância para os aspectos de aprimoramento técnico e clareza.
Ao Profs. Dr. Nabor Mendonça e Dr. Porfírio Farias, por seus valiosos questionamentos
sobre este trabalho, na fase de qualificação do projeto desta dissertação. Agradeço também ao
Prof. Dr. Porfírio pela gentileza em me conceder acesso a importantes fontes bibliográficas, as
quais foram de grande utilidade para a fase de levantamento bibliográfico.
Ao Prof. Dr. Plácido Pinheiro, Coordenador do MIA, pela disposição em ouvir nossas
considerações e reivindicações para obter um melhor aproveitamento do curso de mestrado.
Aos colegas do MIA, pelo coleguismo e pela interessante experiência da troca constante
de idéias que tivemos durante o curso. Agradeço também a todos os colegas que juntamente
comigo se dispuseram a participar das reuniões discentes que objetivavam discutir propostas
de melhoria do curso.
À Tânia, secretária do MIA, pelo seu apoio em resolver todas as nossas necessidades
burocráticas relacionadas ao curso.
Ao Josieudes, aluno graduado em computação pela Unifor, por sua participação na fase
de implementação do projeto de construção do simulador usado para avaliar o desempenho da
proposta desta dissertação.
Finalmente, agradeço à instituição que trabalho, Ministério Público Federal, por ter
financiado 50% do valor deste curso de mestrado.
- vii -
Abstract
In a mobile multidatabase system, there is a collection of autonomous, distributed,
heterogeneous and mobile component database systems which are interconnected by means of
a wireless network. In such an environment, each network node can access multiple databases
of that collection by means of global transactions whose concurrency is managed by a
scheduler, which should be preferably distributed. Several distributed schedulers proposed for
mobile multidatabase systems do violate either the consistency or the autonomy of the
component database systems, due either to the relaxation or the enforcement, respectively, of
the Serializability as the criterion for controlling the concurrency of global transactions. This
paper proposes SESAMO, which is a distributed scheduler for mobile MDBSs. SESAMO is
based on the finding that a mobile MDBS, in which the concurrency control is performed by
the simultaneous execution of multiple autonomous schedulers implementing the Semantic
Serializability correctness criterion, does preserve the autonomy and the data consistency of
the component database systems. As could be evidenced in experimental results, SESAMO
may provide a high degree of concurrency.
Keywords: Multidatabase System – Mobile computing - Transaction Management -
Concurrency Control.
- viii -
Resumo
Em um sistema de banco de dados múltiplo (SBDM) com suporte à computação móvel,
há uma coleção de SBDs-componentes (SBDCs) autônomos, distribuídos, heterogêneos e
móveis, os quais são interconectados através de uma rede de comunicação sem fio. Nesse
ambiente, cada nó da rede pode acessar múltiplos bancos de dados da referida coleção por
meio de transações globais, cuja concorrência é gerenciada por um controlador de
concorrência, o qual deve ser distribuído, preferencialmente. Muitas propostas de
controladores de concorrência distribuídos para SBDMs com suporte à computação móvel
violam a consistência dos dados ou a autonomia dos SBDCs, devido, respectivamente, à
flexibilização ou imposição da Serialidade como critério de controle de concorrência de
transações globais. Esta dissertação propõe o SESAMO, que é um controlador de
concorrência distribuído para SBDMs com suporte à mobilidade. SESAMO é baseado na
identificação de que um SBDM com suporte à mobilidade, cujo controle de concorrência de
transações globais é realizado pela execução simultânea de múltiplos controladores de
concorrência autônomos que implementam o critério de correção da Serialidade Semântica,
preserva a consistência dos dados e a autonomia dos SBDs-componentes. SESAMO pode
proporcionar um alto grau de concorrência, conforme ficou evidenciado nos resultados
experimentais.
Palavras-chaves: Sistema de Banco de Dados Múltiplo – Computação Móvel -
Gerenciamento de Transações - Controle de Concorrência.
- ix -
Sumário
LISTA DE DEFINIÇÕES.................................................................................................................................XII
LISTA DE TABELAS.......................................................................................................................................XII
LISTA DE FIGURAS ......................................................................................................................................XIII
LISTA DE ACRÔNIMOS ...............................................................................................................................XIII
1. INTRODUÇÃO ...............................................................................................................................................17
1.1. C
ONCEITOS
..................................................................................................................................................17
1.2. M
OTIVAÇÃO
................................................................................................................................................18
1.3. O
BJETIVO
.................................................................................................................................................... 20
1.4. P
REMISSAS
..................................................................................................................................................20
1.5. E
STRUTURA
.................................................................................................................................................21
2. GERENCIAMENTO DE TRANSAÇÕES EM UM SISTEMA DE BANCO DE DADOS.......................24
2.1. V
ISÃO GERAL DE UM
S
ISTEMA DE
B
ANCO DE
D
ADOS
..................................................................................24
2.2. G
ERENCIADOR DE
T
RANSAÇÕES
.................................................................................................................26
2.3. T
RANSAÇÕES
...............................................................................................................................................27
2.3.1 Conceitos básicos .................................................................................................................................27
2.3.2 Propriedades ACID..............................................................................................................................30
2.4. C
ONTROLADOR DE
C
ONCORRÊNCIA
............................................................................................................31
2.4.1 Conceitos básicos .................................................................................................................................31
2.4.2 Serialidade: o padrão de correção de históricos ................................................................................. 33
2.4.3 Serialidade de históricos por conflito...................................................................................................35
2.4.4 Níveis de isolamento e problemas relacionados...................................................................................36
2.4.5 Confiabilidade de históricos................................................................................................................. 39
2.5. P
ROTOCOLOS PARA
C
ONTROLE DE
C
ONCORRÊNCIA
....................................................................................42
2.5.1 Protocolos agressivos...........................................................................................................................42
2.5.2 Protocolos conservadores .................................................................................................................... 44
2.5.3 Níveis de isolamento baseados em bloqueios.......................................................................................45
2.5.4 Problemas no término de transações ...................................................................................................46
2.5.5 Protocolos com múltiplas versões de dados.........................................................................................47
2.5.6 Comentários finais................................................................................................................................ 48
2.6. B
LOQUEIO
B
IFÁSICO
................................................................................................................................... 49
2.6.1 Lidando com bloqueios cíclicos ........................................................................................................... 49
2.6.2 Variações do BBF................................................................................................................................. 50
2.6.3 Aumento da concorrência..................................................................................................................... 51
2.6.4 Vazão de processamento de transações................................................................................................52
2.6.5 Comentários finais................................................................................................................................ 53
2.7. G
ERENCIADOR DE
R
ECUPERAÇÃO
............................................................................................................... 53
2.7.1 Visão geral ........................................................................................................................................... 53
2.7.2 Sistema ARIES......................................................................................................................................54
2.8. R
ESUMO DO CAPÍTULO
................................................................................................................................ 56
3. GERENCIAMENTO DE TRANSAÇÕES EM SBDS DISTRIBUÍDOS, MÚLTIPLOS E MÓVEIS.....58
3.1. C
ONCEITOS GERAIS EM
SBD
S DISTRIBUÍDOS
...............................................................................................58
3.1.1 Visão geral de um SBD distribuído ......................................................................................................58
3.1.2 Transação distribuída ..........................................................................................................................59
3.1.3 Arquiteturas de SBDs distribuídos ....................................................................................................... 60
3.1.4 Requisitos do gerenciamento de transações distribuídas.....................................................................62
3.2. C
ONTROLE DE CONCORRÊNCIA EM
SBD
S DISTRIBUÍDOS
.............................................................................62
3.2.1 Protocolos de Controle de Concorrência em SBDs distribuídos .........................................................63
3.2.2 BBF-distribuído.................................................................................................................................... 64
3.3. R
ECUPERAÇÃO DE
SBD
S DISTRIBUÍDOS
......................................................................................................66
SESAMO – F.Stefan - x -
3.3.1 Efetivação Bifásica............................................................................................................................... 66
3.3.2 Topologias de comunicação no EBF....................................................................................................68
3.3.3 Problemas do EBF ...............................................................................................................................69
3.3.4 Efetivação Trifásica.............................................................................................................................. 70
3.4. C
ONCEITOS GERAIS EM
SBD
S MÚLTIPLOS
...................................................................................................71
3.4.1 Visão geral ........................................................................................................................................... 72
3.4.2 Transações globais............................................................................................................................... 73
3.4.3 Esquemas de dados em um SBD múltiplo.............................................................................................73
3.4.4 Taxonomia de SBDs múltiplos..............................................................................................................74
3.4.5 SBDs federados ....................................................................................................................................76
3.4.6 SBDMs.................................................................................................................................................. 77
3.5. C
ONTROLE DE CONCORRÊNCIA EM
SBDM
S
................................................................................................77
3.5.1 Requisitos .............................................................................................................................................77
3.5.2 Problemas.............................................................................................................................................78
3.6. C
ONCEITOS GERAIS EM
SBD
S MÓVEIS
........................................................................................................79
3.6.1 Sistema de computação móvel.............................................................................................................. 79
3.6.2 SBD móvel ............................................................................................................................................ 80
3.7. R
EQUISITOS DO
G
ERENCIAMENTO DE
T
RANSAÇÕES EM
SBD
S MÓVEIS
.......................................................81
3.8. R
ESUMO DO CAPÍTULO
................................................................................................................................ 83
4. SESAMO – FUNDAMENTOS.......................................................................................................................85
4.1. I
NTRODUÇÃO
...............................................................................................................................................85
4.2. S
ERIALIDADE
S
EMÂNTICA
...........................................................................................................................86
4.3. P
REMISSAS
..................................................................................................................................................88
4.4. M
ODELO DE ESTRUTURA
.............................................................................................................................89
4.4.1 ISBDM ..................................................................................................................................................89
4.4.2 GTG......................................................................................................................................................90
4.4.3 SBDC....................................................................................................................................................91
4.5. M
ODELO DE OPERAÇÃO
...............................................................................................................................91
4.6. G
ARANTIA DE CONSISTÊNCIA DOS DADOS E DESEMPENHO
..........................................................................93
4.6.1 Consistência via SSM centralizada ......................................................................................................94
4.6.2 Consistência via SESAMO....................................................................................................................97
4.6.3 Melhoria do desempenho......................................................................................................................98
4.7. R
EQUISITOS DE UMA TRANSAÇÃO
SESAMO ..............................................................................................98
4.8. E
STUDO DE
C
ASO
:
SISTEMA MÚLTIPLO DE VENDAS
...................................................................................100
4.8.1 Descrição do cenário ......................................................................................................................... 100
4.8.2 Discussão............................................................................................................................................104
4.9. R
ESUMO DO CAPÍTULO
..............................................................................................................................104
5. TRABALHOS CORRELATOS ...................................................................................................................106
5.1. K
ANGAROO
...............................................................................................................................................106
5.2. P
RO
-
MOTION
............................................................................................................................................. 107
5.3. PSTM .......................................................................................................................................................108
5.4. V-L
OCK
..................................................................................................................................................... 109
5.5. GTM......................................................................................................................................................... 111
5.6. A
NÁLISE COMPARATIVA DO
SESAMO
COM TRABALHOS CORRELATOS
....................................................112
5.6.1 Modelo de transação e critério de correção ...................................................................................... 113
5.6.2 Infra-estrutura de gerenciamento de dados........................................................................................114
5.6.3 Infra-estrutura de gerenciamento de transações globais ................................................................... 116
5.6.4 Análise adicional................................................................................................................................118
5.7. R
ESUMO DO CAPÍTULO
..............................................................................................................................121
6. AVALIAÇÃO EXPERIMENTAL...............................................................................................................123
6.1. S
IMULADOR
...............................................................................................................................................123
6.1.1 Critérios de desempenho .................................................................................................................... 123
6.1.2 Ambiente computacional .................................................................................................................... 123
6.1.3 Protocolo SESAMO ............................................................................................................................124
6.1.4 Protocolo BBP....................................................................................................................................127
6.1.5 Parâmetros da avaliação.................................................................................................................... 128
6.1.6 Procedimentos ....................................................................................................................................129
SESAMO – F.Stefan - xi -
6.2. R
ESULTADOS OBTIDOS
..............................................................................................................................129
6.2.1 Eficiência............................................................................................................................................ 129
6.2.2 Vazão..................................................................................................................................................130
6.3. D
ISCUSSÃO
................................................................................................................................................131
7. CONCLUSÃO ...............................................................................................................................................133
7.1. S
ÍNTESE DA PROPOSTA
..............................................................................................................................133
7.2. C
ONTRIBUIÇÕES
........................................................................................................................................133
7.2.1 Descentralização do controle de concorrência usando a SSE ........................................................... 133
7.2.2 Projeto de uma estratégia distribuída de controle de concorrência .................................................. 134
7.2.3 Flexibilização da propriedade de isolamento .................................................................................... 134
7.2.4 Simulação dos ganhos potenciais no grau de concorrência............................................................... 134
7.2.5 Adequabilidade ao ambiente de computação móvel...........................................................................135
7.3. T
RABALHOS FUTUROS
............................................................................................................................... 135
ANEXO I – PROJETO LÓGICO DO SIMULADOR ...................................................................................136
I.1. D
IAGRAMA DE
C
ASOS DE
U
SO
...................................................................................................................136
I.2. R
EGRAS DE
N
EGÓCIO
................................................................................................................................. 136
I.3. A
LGORITMOS DOS
C
ASOS DE
U
SO
.............................................................................................................. 137
BIBLIOGRAFIA E REFERÊNCIAS.............................................................................................................. 143
SESAMO – F.Stefan - xii -
LISTA DE DEFINIÇÕES
DEFINIÇÃO 1.
TRANSIÇÃO DE ESTADOS CONSISTENTES DE UM BD. ........................................26
DEFINIÇÃO 2.
ORDENAÇÃO PARCIAL, RESTRIÇÃO E PREFIXO..................................................28
DEFINIÇÃO 3. TRANSAÇÃO......................................................................................................................29
DEFINIÇÃO 4.
CONFLITO E PREDICADO. ............................................................................................31
DEFINIÇÃO 5.
HISTÓRICO........................................................................................................................32
DEFINIÇÃO 6.
HISTÓRICOS EQUIVALENTES. ....................................................................................33
DEFINIÇÃO 7.
HISTÓRICO SERIÁVEL (HSV).......................................................................................33
DEFINIÇÃO 8.
HISTÓRICOS EQUIVALENTES POR CONFLITO......................................................35
DEFINIÇÃO 9.
TRANSAÇÃO T
I
LÊ DA TRANSAÇÃO T
J
.....................................................................39
DEFINIÇÃO 10.
TRANSAÇÃO DISTRIBUÍDA. ........................................................................................60
DEFINIÇÃO 11.
CONFLITO INDIRETO....................................................................................................78
DEFINIÇÃO 12.
CONJUNTO-DEPENDÊNCIA.........................................................................................87
DEFINIÇÃO 13.
UNIDADE SEMÂNTICA (US). ........................................................................................87
DEFINIÇÃO 14.
MÓDULO SEMÂNTICO (MS). .......................................................................................87
DEFINIÇÃO 15.
PROJEÇÃO DE UM HISTÓRICO..................................................................................95
DEFINIÇÃO 16.
HISTÓRICO SEMANTICAMENTE SERIAL. ..............................................................95
DEFINIÇÃO 17.
HISTÓRICO SEMANTICAMENTE SERIÁVEL..........................................................96
DEFINIÇÃO 18.
GRAFO DE SERIAÇÃO SEMÂNTICA..........................................................................96
LISTA DE TABELAS
T
ABELA
1 – N
ÍVEIS DE ISOLAMENTO
ANSI SQL................................................................................................... 39
T
ABELA
2 – E
QUIVALÊNCIA ENTRE OS NÍVEIS DE ISOLAMENTO BASEADOS EM BLOQUEIOS E OS
ANSI SQL ......... 46
T
ABELA
3 - O
PERAÇÕES EM UMA TRANSAÇÃO
SESAMO......................................................................................98
T
ABELA
4 - S
UB
-
OPERAÇÕES DE UMA TRANSAÇÃO
SESAMO...............................................................................99
T
ABELA
5 – E
XECUÇÃO DO CENÁRIO USANDO O
SESAMO.................................................................................102
T
ABELA
6 - E
XECUÇÃO DO CENÁRIO USANDO O
BBF-
PRECISO
............................................................................ 103
T
ABELA
7 – C
ONTROLADORES DE CONCORRÊNCIA
:
MODELO DE TRANSAÇÃO E CRITÉRIO DE CORREÇÃO
...........114
T
ABELA
8 – C
ONTROLADORES DE CONCORRÊNCIA
:
INFRA
-
ESTRUTURA DE GERENCIAMENTO DE DADOS
............115
T
ABELA
9 – C
ONTROLADORES DE CONCORRÊNCIA
:
INFRA
-
ESTRUTURA DE GERENCIAMENTO DE TRANSAÇÕES
GLOBAIS
.......................................................................................................................................................118
T
ABELA
10 – C
ONTROLADORES DE CONCORRÊNCIA
:
RESUMO DA ANÁLISE
......................................................... 120
T
ABELA
11 – A
MBIENTE COMPUTACIONAL USADO NA SIMULAÇÃO DO
SESAMO...............................................124
T
ABELA
12 – P
ARÂMETROS USADOS NA SIMULAÇÃO DE DESEMPENHO DO
SESAMO ......................................... 128
SESAMO – F.Stefan - xiii -
LISTA DE FIGURAS
F
IGURA
1 – A
RQUITETURA DE UM
S
ISTEMA DE
B
ANCO DE
D
ADOS
........................................................................24
F
IGURA
2 - A
RQUITETURA DE UM
SBD
MÚLTIPLO
.................................................................................................73
F
IGURA
3 - A
RQUITETURAS DE INTEGRAÇÃO DE
SBD
S
.......................................................................................... 76
F
IGURA
5 – A
RQUITETURA DE UM
S
ISTEMA DE
C
OMPUTAÇÃO
M
ÓVEL
.................................................................79
F
IGURA
6 - SESAMO:
MODELO DA ESTRUTURA
.................................................................................................... 90
F
IGURA
7 - SESAMO:
MODELO DE OPERAÇÃO
(1) ................................................................................................ 92
F
IGURA
8 - SESAMO:
MODELO DE OPERAÇÃO
(2) ................................................................................................ 92
F
IGURA
9 - SESAMO:
MODELO DE OPERAÇÃO
(3) ................................................................................................ 93
F
IGURA
10 - SESAMO:
PROCESSO SINCRONIZADOR
...........................................................................................125
F
IGURA
11 - SESAMO:
PROCESSO EXECUTOR
....................................................................................................127
F
IGURA
12 - SESAMO:
AVALIAÇÃO DA EFICIÊNCIA
............................................................................................130
F
IGURA
13 – SESAMO:
AVALIAÇÃO DA VAZÃO
................................................................................................. 130
F
IGURA
14 - SESAMO: D
IAGRAMA DE
C
ASOS DE
U
SO
....................................................................................... 136
LISTA DE ACRÔNIMOS
AAD – agente de acesso aos dados.
AC – agente de compacto.
ACID – atomicidade, consistência, isolamento e durabilidade.
BBF – bloqueio bifásico.
BBP – protocolo baseado no BBF-preciso
BCG – bloqueio cíclico global.
BD – banco de dados.
BDD – BD distribuído.
BDM – BD múltiplo.
CC – controlador de concorrência.
CM – computador móvel.
DC – dispositivo computacional.
EBF – efetivação bifásica.
ECL – esquema conceitual local.
SESAMO – F.Stefan - xiv -
ECG – esquema conceitual global.
EEG – esquema externo global.
EEL – esquema externo local.
EIL – esquema interno local.
ESM – estação de suporte à mobilidade.
ETF – efetivação trifásica.
FOAS – fila de operações a sincronizar.
FOJS – fila de operações já sincronizadas.
FOSA – fila de operações com sincronização adiada.
GC – gerenciador de consultas.
GD – gerenciador de dados.
GE – grafo de espera.
GEG – GE global.
GS – gerenciador de subtransações.
GSS – grafo de seriação semântica.
GT – gerenciador de transações.
GTG – gerenciador de transações globais.
GTM – gerenciador de transações móveis.
HGPSS – histórico global parcial semanticamente seriável.
HGUSS – histórico global unificado semanticamente seriável.
HSE – histórico serial.
HSV – histórico seriável.
ISBDM – interface de SBDM.
JT – joey transaction.
KT – kangaroo transaction.
SESAMO – F.Stefan - xv -
LBDM – linguagem para BDM.
MS – módulo semântico.
MSE – modelo sumário de esquemas.
NTGA – número de transações globais ativas.
RCMD – rede de computação móvel de estrutura dinâmica.
RCME – rede de computação móvel de estrutura estática.
RF – requisito funcional.
RN – regra de negócio.
RSF – rede de comunicação sem fio.
SBD – sistema de BD.
SBDC – SBD-componente.
SBDM – SBD múltiplo.
SCM – sistema de computação móvel.
SESAMO – serialidade semântica aplicada à mobilidade.
SGBD – sistema gerenciador de BD.
SGBDM – SGBD múltiplo.
SSM – serialidade semântica.
ST – subtransação.
TG – transação global.
US – unidade semântica.
- xvi -
CAPÍTULO I
INTRODUÇÃO
- 17 -
1. Introdução
Neste capítulo, são apresentados conceitos básicos sobre Gerenciamento de Transações,
Controle de Concorrência, Sistema de Banco de Dados Múltiplo e Computação Móvel. Em
seguida, são apresentados a motivação, os objetivos, as premissas e a estrutura desta
dissertação.
1.1. Conceitos
Um Sistema de Banco de Dados (SBD) convencional é composto basicamente de um
Banco de Dados (BD) e um Sistema Gerenciador de Banco de Dados (SGBD), tendo este as
seguintes funções: gerenciar, armazenar, consultar e atualizar itens daquele BD, bem como
prover disponibilidade e confiabilidade de acesso ao BD pelos usuários e aplicações de
computador. A execução consistente e confiável de operações originadas de aplicações
concorrentes que acessam um BD, considerando a possibilidade de ocorrência de falhas
eventuais no processamento dos dados, ocorre por meio de transações. Uma transação é uma
abstração que representa uma seqüência de operações sobre itens de um BD, resultante da
execução de um programa que compõe uma aplicação de computador.
O Gerenciador de Transações (GT) é o componente do SGBD que tem como um de
suas principais funcionalidades o controle de concorrência, o qual é desempenhado pelo
mecanismo Controlador de Concorrência (CC). O CC objetiva controlar a execução
simultânea de operações pertencentes a transações concorrentes de forma tal que o BD
acessado esteja sempre mantido em um estado consistente. Um estado de um BD é o conjunto
dos valores de seus itens de dados, em um determinado instante. Um estado de um BD é
consistente quando está em conformidade com um conjunto de regras de integridade definidas
sobre esse BD.
A atividade do CC consiste em receber, entrelaçar e executar as operações de transações
concorrentes, produzindo um histórico de execução das transações, também conhecido, de
forma resumida, pelo termo Histórico. O entrelaçamento das operações feito pelo CC
tradicional segue um critério denominado Serialidade, por meio do qual se obtém um
Histórico Seriável (HSV), ou seja, um histórico equivalente a um Histórico Serial (HSE),
representando este uma execução serial do mesmo conjunto de transações que formou aquele
SESAMO – F.Stefan Introdução - 18 -
HSV. Em um HSE, as transações são executadas uma de cada vez, em seqüência. Diz-se que
um determinado histórico H é equivalente a outro H’ caso H produza, sobre um estado inicial
E1 de um BD, o mesmo estado final E2 que teria sido produzido por H’, caso H’ fosse
executado sobre E1.
Um Sistema de Banco de Dados Múltiplo (SBDM) é um sistema que visa integrar os
dados e funcionalidades de múltiplos SBDs autônomos, sendo estes denominados SBDs-
componentes (SBDCs), de forma tal que a autonomia e a consistência de cada SBDC sejam
preservadas. Um SBDM deve fornecer acesso aos dados e funcionalidades dos SBDCs com
transparência dos aspectos de distribuição e heterogeneidade dos dados, como também dos
aspectos de tecnologias de rede e plataforma computacional utilizados. Em um SBDM, o
acesso aos dados dos SBDCs ocorre por meio de transações globais (TGs).
A evolução constante das telecomunicações e das tecnologias de computadores portáteis
possibilitou o surgimento de Sistemas de Computação Móvel (SCMs). No ambiente
computacional de um SCM, alguns dos elementos que participam do processamento de dados
são computadores móveis (CMs), os quais podem comunicar-se com os demais computadores
por meio de Redes de comunicação Sem Fio (RSF). A necessidade de processamento de
dados de forma consistente, confiável e eficiente, através de CMs, como também a
necessidade de esses computadores acessarem SBDs pré-existentes têm motivado o
desenvolvimento de SBDs com suporte à mobilidade e, por extensão, de SBDMs com suporte
à computação móvel. Em um SBDM com suporte à computação móvel, cada nó da rede de
computadores pode hospedar um SBD, formando-se então uma coleção de SBDCs
autônomos, distribuídos, heterogêneos e móveis.
1.2. Motivação
Nesta seção, será apresentado um cenário de aplicação da proposta SESAMO, bem
como o enunciado do problema a ser resolvido.
1.2.1 Cenário de aplicação
A seguir, descreve-se um cenário real em que a proposta SESAMO seria aplicável.
Consideremos que há um hospital em que há dois SBDs autônomos sendo utilizados em um
SESAMO – F.Stefan Introdução - 19 -
SCM. Um dos SBDs gerencia dados sobre o histórico médico de pacientes do hospital e está
localizado em um computador A. O outro SBD gerencia dados sobre materiais e
medicamentos que são usados durante cirurgias. Tal SBD está localizado em um computador
B. Nesse ambiente, há também vários CMs que são usados por médicos. Cada um desses CMs
contém um SBD que gerencia dados sobre a agenda pessoal do respectivo médico usuário
desse CM.
No hospital em questão, deverá ser implantado um SBDM com suporte à mobilidade
que deverá integrar os três citados SBDs, passando estes a serem os SBDCs do SBDM
considerado. Uma nova aplicação, denominada AP1, deverá ser desenvolvida de forma a
fornecer a seguinte funcionalidade. Um médico, logo após fazer o atendimento de um
paciente que deverá ser submetido a uma cirurgia, registra dados em AP1, de forma que esta
aplicação realize as necessárias atualizações nos BDs locais dos SBDs A e B, bem como no
BD localizado no CM do médico. O médico poderá efetuar atualizações nos referidos
registros em vários pontos do hospital, tais como seu consultório, centros cirúrgicos e salas de
reunião, nas quais vários médicos poderão estar compartilhando dados presentes em seus
respectivos CMs, por meio de conexões sem fio.
O referido SBDM e a aplicação AP1 não deverão afetar a autonomia de funcionamento
dos referidos SBDCs e das aplicações que tenham sido desenvolvidas previamente para
acessá-los de forma isolada. Por exemplo, pode haver uma aplicação de controle de estoque,
denominada CE, usada pelo departamento de farmácia, o qual controla o estoque de
medicamentos e outros materiais usados pelo hospital. Os usuários poderão continuar usando
CE sem depender do funcionamento de AP1 e sem que devam ser realizadas modificações em
CE, por conta da existência de AP1.
1.2.2 Problema
Em um SBDM com suporte à mobilidade, o controle de concorrência deve ser
distribuído, preferencialmente. Muitas propostas de CCs distribuídos para SBDMs com
suporte à computação móvel adotam a Serialidade como critério de correção, o qual impõe
que a execução das TGs produza um HSV. Tal imposição normalmente requer a violação
parcial ou total da autonomia dos SBDCs, devido à necessidade de um controle externo da
SESAMO – F.Stefan Introdução - 20 -
ordem em que o CC de cada SBDC executa operações no seu BD local. Por outro lado, há
outras propostas de CC distribuído para SBDMs com suporte à mobilidade que flexibilizam
as regras da Serialidade, no sentido de evitar a violação da autonomia dos SBDCs, mas não
garantem a consistência dos dados dos SBDCs.
1.3. Objetivo
Esta dissertação propõe o SESAMO, que é um controlador de concorrência para
SBDMs com suporte à computação móvel, tendo como objetivos específicos:
Explorar as características do modelo de transação Serialidade Semântica [10], no
sentido de definir uma estratégia de controle de concorrência distribuído para
SBDMs com suporte à mobilidade, de forma que sejam preservadas a autonomia e a
consistência dos dados dos SBDCs;
Especificar um protocolo de controle de concorrência baseado na estratégia acima
definida e que implemente uma forma de flexibilização da propriedade de
isolamento de TGs, considerando as propriedades ACID [34], mediante a
exploração das características da Serialidade Semântica, visando aumentar o grau de
concorrência em relação ao critério de correção tradicional (Serialidade), o qual é
adotado no protocolo padrão de mercado BBF-preciso [27].
1.4. Premissas
O SESAMO assume que o ambiente computacional dispõe das seguintes
funcionalidades:
Há uma estrutura de SBDM que dá suporte à computação móvel e que fornece
acesso às estruturas de dados de todos os SBDCs. Um modelo de referência para
esse tipo de estrutura é a arquitetura AMDB [9];
A estrutura de SBDM considerada é tolerante a falhas com respeito ao
gerenciamento de TGs;
SESAMO – F.Stefan Introdução - 21 -
Cada computador onde o SESAMO estiver instalado tem uma interface que fornece
acesso transparente às funcionalidades do SBDM considerado;
Cada SBDC do SBDM considerado garante a consistência de seu BD pela
imposição de uma execução seriável de suas transações locais. É importante
ressaltar que o SESAMO não viola a autonomia dos SBDCs porque nenhuma
modificação é requerida em suas estruturas de dados ou em seus sistemas de
gerenciamento de banco de dados; e
As estruturas de dados de cada SBDC estão associadas a uma Unidade Semântica
(US) específica. Tal informação está contida na estrutura de dados do SESAMO e é
requerida apenas para os propósitos do SESAMO. Dessa forma, nem as aplicações
que utilizarão o SESAMO e nem os SBDCs acessados dependerão daquela
informação para quaisquer propósitos. Para fins de simplificação deste trabalho, é
assumido que o BD de cada SBDC corresponde a uma única US.
1.5. Estrutura
O restante desta dissertação está estruturado conforme descrito a seguir.
No Capítulo 2, aborda-se o modelo clássico de Gerenciamento de Transações em um
SBD. Inicialmente, é apresentada uma visão global da arquitetura de um SBD, destacando o
componente Gerenciador de Transações. Em seguida, são introduzidos alguns conceitos
básicos sobre transações e sobre a necessidade e o critério tradicional de correção adotado
para fazer o controle de transações concorrentes. Adiante, são apresentados os protocolos de
controle de concorrência tradicionais, com ênfase no Bloqueio Bifásico (BBF), cuja variação
BBF-preciso é o padrão de mercado. Ao final desse capítulo, descreve-se, de forma geral, o
componente do SGBD denominado Gerenciador de Recuperação e, de forma específica, o
Sistema ARIES, que é a implementação padrão da academia e da indústria de software.
No Capítulo 3, apresenta-se a atividade de gerenciamento de transações nos SBDs
distribuídos, múltiplos e móveis. Inicialmente, são apresentados conceitos gerais sobre os
SBDs distribuídos. Em seguida, são apresentados conceitos sobre o controle de concorrência e
o gerenciamento de recuperação no âmbito dos SBDs distribuídos. Ao final, são apresentados
SESAMO – F.Stefan Introdução - 22 -
alguns conceitos gerais, as arquiteturas e a atividade de controle de concorrência no âmbito
dos SBDs múltiplos (SBDMs) em geral e dos SBDMs com suporte à computação móvel.
No Capítulo 4, são apresentados os fundamentos teóricos da proposta desta dissertação,
ou seja, o CC SESAMO. Inicialmente, são introduzidos alguns conceitos básicos. Em
seguida, descreve-se o modelo de transação no qual o SESAMO está baseado, ou seja, a
Serialidade Semântica. Em seguida, são descritas as premissas nas quais o SESAMO está
baseado. A seguir, são apresentados os modelos de estrutura e operação do SESAMO.
Adiante, são feitas demonstrações de que o SESAMO preserva a consistência dos dados e
contribui para o ganho de desempenho de um SBDM gerenciado por ele. Em seguida, são
descritos todos os requisitos necessários para se elaborar uma transação que utilize o
SESAMO. Ao final do capítulo, descreve-se um estudo de caso em que se utiliza o SESAMO,
apresentando-se os resultados obtidos.
No Capítulo 5, são apresentadas algumas propostas acadêmicas que abordam CCs
distribuídos para SBDMs com suporte à computação móvel. Para cada uma das propostas
apresentadas, apresenta-se uma descrição resumida da proposta, seus objetivos, o modelo de
transação no qual ela se baseia, a infra-estrutura de gerenciamento de dados e transações, bem
como o processo de gerenciamento da execução de uma TG. Ao final desse capítulo,
apresenta-se uma análise comparativa dos mecanismos apresentados, em relação ao
SESAMO.
No Capítulo 6, serão descritos os recursos usados para construir uma aplicação capaz de
simular as operações dos algoritmos de controle de concorrência do SESAMO e de um
algoritmo baseado no protocolo BBF-preciso, no sentido de comparar seus desempenhos. Em
seguida, são apresentados os resultados obtidos e a avaliação correspondente.
O Capítulo 7 contém a conclusão desta dissertação. São apresentadas uma síntese do
trabalho, as contribuições obtidas e as perspectivas futuras de desenvolvimento.
Finalmente, no Apêndice I, descreve-se o projeto lógico de construção da aplicação
citada no Capítulo 6.
- 23 -
CAPÍTULO II
GERENCIAMENTO DE TRANSAÇÕES EM
UM SISTEMA DE BANCO DE DADOS
- 24 -
2. Gerenciamento de Transações em um Sistema de Banco de
Dados
Neste capítulo, aborda-se o modelo clássico de Gerenciamento de Transações em um
Sistema de Banco de Dados (SBD). Inicialmente, é apresentada uma visão global da
arquitetura de um SBD, destacando o componente Gerenciador de Transações. Em seguida,
são introduzidos alguns conceitos básicos sobre transações e sobre a necessidade e o critério
de correção tradicional adotado para fazer o controle de transações concorrentes. Adiante, são
apresentados os protocolos de controle de concorrência tradicionais, com ênfase no Bloqueio
Bifásico (BBF), cuja variação BBF-preciso é o padrão de mercado. Ao final desse capítulo,
descreve-se, de forma geral, o componente do SGBD denominado Gerenciador de
Recuperação e, de forma específica, o Sistema ARIES, que é a implementação padrão da
academia e da indústria de software.
2.1. Visão geral de um Sistema de Banco de Dados
Sistema de Banco de Dados (SBD) é um conjunto de módulos computacionais que
fornecem acesso a uma coleção de dados denominada Banco de Dados [4]. Um modelo
abstrato de uma arquitetura de SBD está representado na Figura 1.
Figura 1 – Arquitetura de um Sistema de Banco de Dados
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 25 -
Um SBD tem a função de criar e armazenar uma coleção de dados persistentes,
permitindo a modificação e consulta desses dados, por parte de aplicações-clientes
1
, de forma
eficiente, consistente e confiável, pelo uso de uma linguagem de manipulação de dados
[57,62]. A atual linguagem padrão de manipulação de dados é SQL:2003 [25].
Um SBD é formado basicamente por dois componentes: o Sistema Gerenciador de
Banco de Dados (SGBD), que é uma aplicação que gerencia a manipulação do banco de
dados; e o Banco de Dados (BD). Dentre os tipos de BDs em uso na academia, na indústria da
informática e no mundo dos negócios, o tipo predominante é o BD Relacional, ao qual esta
dissertação se restringirá.
O SGBD é formado pelos seguintes componentes:
Gerenciador de Consultas (GC). Componente encarregado de preparar e otimizar o
plano de execução de consultas sobre itens do BD, originadas de programas de
aplicações e/ou usuários;
Gerenciador de Transações (GT). Componente encarregado de gerenciar o
processamento dos programas que acessam, simultaneamente ou não, o BD,
registrar informações redundantes no BD e, por fim, recuperar o BD a um estado
anterior consistente, caso ocorram falhas operacionais no SGBD. O desempenho
dessas funções é realizado, conjuntamente, pelos componentes internos Controlador
de Concorrência (CC)
2
e Gerenciador de Recuperação (GR)
3
, os quais serão
descritos, em maiores detalhes, na Seção 2.2;
Gerenciador de Dados (GD). Componente que interage diretamente com o sistema
operacional do dispositivo computacional em que reside o BD, no sentido de
gerenciar o armazenamento, a indexação, o acesso e a atualização de blocos de
dados, os quais podem estar presentes na memória principal do computador ou nos
dispositivos de memória secundária.
1
Uma aplicação-cliente pode representar: uma interação direta de um usuário com o SBD, por meio de uma
interface gráfica ou textual; ou um programa que interage automaticamente com o SBD.
2
Tradução livre do termo original inglês scheduler. Alguns autores adotam o nome Escalonador. Deste ponto em
diante, todas as notas de tradução serão prefixadas com a sigla NT (notas de tradução). Além disso, todas as
traduções são livres, isto é, não estão rigorosamente de acordo com quaisquer padrões acadêmicos ou comerciais
estabelecidos. Todas as traduções referem-se a expressões ou termos originais da língua inglesa, exceto se
mencionado em contrário.
3
NT: recovery manager.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 26 -
O BD compõe-se dos arquivos de dados, dos arquivos de descrição dos dados
(formando o chamado Catálogo de dados), dos arquivos de índices dos dados, fragmentos de
código e, por fim, dos arquivos que contêm registros a serem usados no caso da necessidade
de recuperação do próprio BD, após a ocorrência de falhas no funcionamento deste.
O presente modelo abstrato de SBD está de acordo com os modelos apresentados pelos
autores de [31,57,62]. O modelo apresentado em [4] tem as seguintes diferenças, em relação
ao modelo apresentado na Figura 1:
Os componentes do SBD são: Gerenciador de Transações (GT), Controlador de
Concorrência (CC), Gerenciador de Dados (GD) e Banco de Dados (BD);
O GT corresponde ao Gerenciador de Consultas representado na Figura 1;
O CC corresponde a um dos componentes do GT representado na Figura 1; e
O GD corresponde, em relação aos componentes representados na Figura 1, ao GD
e a um dos componentes do GT.
Esta dissertação abordará com maiores detalhes apenas o SGBD e, mais
especificamente, o componente GT. Maiores informações sobre a organização do BD, do GC
e do GD poderão ser obtidas nas referências bibliográficas deste trabalho, principalmente em
[4,53,57,62].
2.2. Gerenciador de Transações
A função básica do Gerenciador de Transações (GT) de um SGBD é sincronizar
corretamente a execução simultânea de programas que contêm operações de acesso e
modificação de um BD, objetivando manter esse BD sempre em um estado consistente
4
.
Definição 1. Transição de estados consistentes de um BD.
A transição de estados consistentes de um BD é a passagem de um estado consistente
desse BD para outro estado também consistente, sendo que:
Um estado do BD é o conjunto de valores assumidos por seus itens de dados, em
um determinado instante.
4
Vide conceito de estado consistente na Definição 1.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 27 -
Um BD está num estado consistente quando os valores assumidos por seus itens de
dados estão em conformidade com todas as restrições lógicas de integridade
definidas sobre o mesmo. Tais restrições podem ser definidas e armazenadas no
próprio BD, tarefa geralmente realizada por uma equipe composta de um ou mais
usuários conhecidos por Administradores do BD. Muitas restrições podem também
estar contidas nas próprias aplicações.
O GT é formado pelos seguintes componentes [31]:
Controlador de Concorrência (CC). Este componente realiza as seguintes atividades:
planejamento
5
da execução das transações
6
e acesso consistente aos dados; e
Gerenciador de Recuperação (GR). Este componente realiza as seguintes atividades:
recuperação
7
do BD a um estado consistente após a ocorrência de falhas e registro
redundante
8
sobre dados e sobre operações de transações executadas. Este
componente não será descrito em maiores detalhes, por não ser o foco desta
dissertação. Na Seção 2.7, descreve-se, de forma resumida, o funcionamento deste
componente. Informações mais detalhadas poderão ser obtidas nas referências
[4,53,57,62].
2.3. Transações
Nesta seção, serão vistos conceitos básicos e as propriedades das transações.
2.3.1 Conceitos básicos
Uma tradicional definição informal para Transação [4] é a seguinte: uma transação é
uma abstração que representa a execução de um programa que acessa um BD compartilhado.
Uma definição informal mais completa para o termo transação seria a seguinte: transação é
uma abstração correspondente a uma unidade lógica de computação, resultante da execução
completa e isolada de uma aplicação ou programa, formada por uma ordenação parcial
9
de
5
NT: scheduling.
6
Vide conceito de transação na Seção 2.3.
7
NT: failure recovery ou crash recovery.
8
NT: logging.
9
Vide Definição 2.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 28 -
operações distintas e indivisíveis, executadas sobre itens de um BD compartilhado, e que
realiza a transição de estados consistentes
10
desse BD.
Uma transação é composta pelos seguintes elementos:
Uma operação de início da transação
11
. Esta operação sinaliza para o gerenciador de
transações o início de uma nova transação;
Uma ou mais operações de leitura e/ou escrita sobre itens do BD;
Uma operação de efetivação
12
ou de aborto
13
da transação. A operação de efetivação
sinaliza para o GT que a transação foi executada até o fim com sucesso, devendo o
GT tornar os efeitos da transação permanentes no BD. A operação de aborto sinaliza
para o GT que houve um término prematuro da transação e, portanto, os efeitos de
todas as suas operações devem ser anulados.
Uma operação de término da transação
14
. Esta operação sinaliza para o GT o
término da transação.
Uma transação pode estar em um dos seguintes estados:
Ativa. Significa que a transação foi iniciada, mas ainda não foi terminada.
Efetivada. Significa que a transação foi concluída com sucesso.
Abortada. Significa que a transação foi desfeita.
A seguir, serão formalizados alguns conceitos [4], dentre eles o conceito de transação.
Definição 2. Ordenação parcial, restrição e prefixo.
Uma ordenação parcial O é um par ordenado (D, <), onde:
D é chamado de domínio da ordenação parcial e representa um conjunto cujos
elementos estão sendo ordenados;
10
Vide Definição 1.
11
NT: begin of transaction.
12
NT: commit. Alguns autores utilizam a tradução “confirmação”. Optamos pelo termo efetivação para evitar
dubiedades.
13
NT: abort ou rollback.
14
NT: end of transaction.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 29 -
< é uma relação de ordenação binária irreflexiva
15
e transitiva
16
sobre os elementos
de D.
Se a < b, a e b
∈
D, então a antecede b e b sucede a em O.
Dados dois elementos distintos c,d ∈ O, se nenhum deles antecede o outro em O,
então ambos não podem ser comparados em O.
Uma ordenação parcial O’ = (D’, <’) é uma restrição de O no domínio D’, se:
D’ ⊆ D; e
Para todos os elementos a,b ∈ D’, a<’b se e somente se a<b.
O’ é um prefixo de O, simbolizado por O’ ≤ O, se:
O’ é uma restrição de O; e
Para cada a
∈
D’, todos os antecessores de a em O (isto é, todos os elementos b
∈
D, tais que b<a) estão também em D’ (isto é, b
∈
D’).
Definição 3. Transação.
Uma transação T
i
é uma ordenação parcial T
i
= (D
i
, <
i
), que atende as seguintes
condições:
1. T
i
⊆
{r
i
[x], w
i
[x]} U {a
i ,
c
i
}, onde: r
i
[x] representa uma operação de leitura de T
i
sobre um item de dado x; w
i
[x] representa uma operação de escrita de T
i
sobre x; a
i
representa uma operação de aborto de T
i
; c
i
representa uma operação de efetivação
de T
i
;
2. a
i
∈ Ti se e somente se c
i
∉ Ti; e c
i
∈ Ti se e somente se a
i
∉ Ti;
3. Se a operação q é c
i
ou a
i
(seja qual das duas estiver em T
i
), então para qualquer
outra operação p
∈
T
i
, tem-se que p <
i
q;
4. Se r
i
[x], w
i
[x] ∈ T
i
, então ou r
i
[x] <
i
w
i
[x] ou w
i
[x] <
i
r
i
[x].
A condição de número 1 acima define os tipos de operação que podem existir em uma
transação qualquer. A condição de número 2 reflete a propriedade de que uma transação
15
Uma relação binária < em D é irreflexiva se: para todo a
∈
D, não pode ocorrer a seguinte relação: a<a.
16
Uma relação binária é transitiva se, para todo a,b,c
∈
D e a<b e b<c, é válido que a<c.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 30 -
qualquer somente pode ter uma operação de aborto (a
i
) ou de efetivação (c
i
), mas não
ambas. Na condição de número 3, mostra-se que a operação de aborto ou efetivação
(seja qual das duas estiver na transação) deve suceder qualquer outra operação da
transação. A condição de número 4 reflete a necessidade de que a relação binária entre
as operações da transação, ou seja, <
i
, deva especificar a ordem de execução das
operações de leitura e escrita que se refiram a um mesmo item de dado.
2.3.2 Propriedades ACID
De acordo com a teoria clássica de gerenciamento de transações em BDs [34], o SGBD
realiza transições de estados consistentes
17
de um BD mediante a preservação das quatro
propriedades básicas das transações. Tais propriedades são conhecidas pelo acrônimo ACID
(Atomicidade, Consistência, Isolamento e Durabilidade) e estão descritas a seguir.
Atomicidade. Assegurada pelo componente GR do SGBD. É a garantia de que ou
todas ou nenhuma das operações da transação serão efetivamente executadas no
BD. É também denominada como o “Requisito todos-ou-nenhum”. Esta
propriedade caracteriza a transação como uma unidade lógica de computação.
Consistência. Assegurada, de forma conjunta, pelo código da transação, pela
verificação automática das restrições de integridade do BD, e pelo componente CC
do SGBD. Esta propriedade pressupõe que uma transação, quando executada
isoladamente (sem a presença de qualquer outra transação cuja execução seja
concorrente), é consistente, ou seja, é correta. Uma transação é considerada correta
quando realiza uma transição de estados consistentes do BD. A propriedade de
Consistência é também denominada como o “Requisito da Correção”. Esta
propriedade caracteriza a transação como uma unidade consistente de computação.
Isolamento. Assegurada pelo CC. É a propriedade que assegura que a transação,
durante sua execução, não sofrerá efeitos de outras que estejam sendo executadas de
forma concorrente. Dessa forma, os efeitos da transação seriam os mesmos caso ela
fosse executada isoladamente. Como conseqüência desta propriedade, os efeitos
intermediários, tais como atualizações sobre itens de um BD, produzidos por uma
transação, antes de seu término, não poderão ser acessíveis por outras transações.
17
Vide Definição 1.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 31 -
Durabilidade. Assegurada pelo GR. Consiste em garantir que os efeitos de uma
transação persistam após a mesma haver sido concluída. Havendo falhas no SGBD,
o referido componente deve ser capaz de refazer as operações de transações
concluídas, cujos efeitos ainda não tenham sido refletidos (gravados) no BD. Deve o
componente também desfazer os efeitos já produzidos por transações iniciadas, mas
não concluídas. Esta propriedade também é conhecida por “Requisito da
Persistência”. Esta propriedade caracteriza a transação como uma unidade confiável
(recuperável) de computação, ou ainda, uma unidade de recuperação pós-falhas.
2.4. Controlador de Concorrência
Nesta seção, serão abordados conceitos básicos sobre controle de concorrência e o
critério tradicional usado para avaliar a correção de um CC.
2.4.1 Conceitos básicos
Em um ambiente computacional multiusuário onde exista um SBD, é desejável que
múltiplas transações possam ser processadas de forma paralela, objetivando-se maximizar o
uso dos recursos computacionais. Conforme visto na Seção 2.2, é o componente CC do
SGBD que permite a execução simultânea (concorrente) de transações.
O CC sincroniza a execução de transações concorrentes mediante um processo de
entrelaçamento das operações dessas transações. O resultado desse processo é um
escalonamento da execução de operações sobre itens de BD. Esse escalonamento é
denominado histórico. Um Histórico é uma representação, em algum ponto no tempo, da
execução concorrente de um conjunto de transações. A seguir, descreve-se uma formalização
de alguns conceitos [4], dentre eles o conceito de histórico.
Definição 4. Conflito e predicado.
Considerem-se as seguintes convenções: (i) p simboliza uma operação de uma transação
sobre um item de dado (ou predicado, isto é, um conjunto de dados que satisfaz uma certa
condição lógica [3,27]) x de um BD, onde: p ∈ {r[x],w[x]}, r[x] representa uma operação de
leitura e w[x] representa uma operação de escrita; (ii) OP(T
i
) representa o conjunto de
operações que pertencem a uma certa transação T
i
.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 32 -
Duas operações p ∈ OP(T
i
) e q ∈ OP(T
j
), T
i
T
i
, estão em conflito se p,q ∈ {r[x],w[x]}
e ( p = w[x] ou q = w[x]).
De forma mais simples, pode-se dizer que duas operações estão em conflito quando se
referem ao mesmo item de dado ou ao mesmo predicado, originam-se de transações distintas
e pelo menos uma delas for uma operação de escrita.
Definição 5. Histórico.
Um histórico H é um prefixo de uma ordenação parcial (vide Definição 2) denominada
histórico completo H
C
= (D
C
,<
C
), feita sobre um conjunto de transações T = {T
1
, T
2
, ... T
n
} ,
onde:
1. H
C
= U
n
i=1
T
i
, sendo cada Ti = (D
i
,<
i
) uma transação (vide Definição 3) distinta;
2. <
C
⊇ U
n
i=1
<
i
;
3. Para quaisquer duas operações em conflito (vide Definição 4) p,q ∈ H
C
, uma das
seguintes assertivas deve ser verdadeira: p <
C
q ou q <
C
p.
A condição de número 1 acima indica que a execução representada por H
C
envolve
exatamente as operações submetidas pelo conjunto de transações T. A condição de número 2
indica que H respeita as ordenações de todas as operações especificadas em cada transação T
i
.
De fato, conforme explicado em [31], a seqüência relativa de execução das operações de cada
transação que forma um histórico é a mesma que seria resultante da execução isolada da
transação. Finalmente, a condição de número 3 indica que a ordenação de cada par de
operações conflitantes é determinada por <
C
. A partir de sua definição, pode-se concluir que
um histórico representa uma execução possivelmente incompleta de um conjunto de
transações.
Um histórico deve ter as seguintes propriedades:
Correção
18
. É a garantia de que o histórico é correto, ou seja, realiza transições de
estados consistentes do banco de dados
19
. Esta propriedade tem a finalidade de
preservar as propriedades de Consistência e Isolamento das transações. O critério
18
Na literatura pesquisada, os termos corretude e exatidão também têm sido empregados como sinônimo do
termo correção.
19
Vide Definição 1.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 33 -
tradicional de correção
20
de históricos é denominado Serialidade
21
, o qual será
abordado com mais detalhes na Subseção 2.4.2.
Confiabilidade. É a garantia de que o histórico mantém o BD em um estado que
poderá ser retornado a um estado consistente anterior, caso ocorram falhas na
operação do SGBD. Essa propriedade do histórico tem a finalidade de preservar as
propriedades de Atomicidade e Durabilidade das transações. É importante relembrar
que a efetiva recuperação do BD, conforme já visto na Seção 2.2 acima, é função do
componente GR do SGBD.
2.4.2 Serialidade: o padrão de correção de históricos
A execução serial de um conjunto T = {T
1
, T
2
, ... T
n
} de transações ocorre quando elas
são executadas, uma de cada vez, em seqüência. Assim sendo, na execução serial de T, cada
transação é executada completamente antes de ser iniciada a execução de uma outra
transação. Conforme visto anteriormente, histórico é a representação da execução de um
conjunto de transações concorrentes. Por extensão, a representação da execução serial de um
conjunto de transações concorrentes é denominada histórico serial (HSE).
Definição 6. Históricos equivalentes.
Um histórico H é equivalente por Estado Final (ou, simplesmente, equivalente) a outro
histórico H’ produzido pela execução de um conjunto T = {T
1
, T
2
, ... T
n
} de transações
concorrentes e que realiza a transição do estado E
1
para o estado E
2
de um BD, se H é
formado pelas mesmas operações de H’ e a execução de H realize a mesma transição de
estados do referido BD.
Definição 7. Histórico seriável (HSV).
Um histórico H, produzido pela execução de um conjunto T = {T
1
, T
2
, ... T
n
} de
transações concorrentes, é denominado histórico seriável
22
se é equivalente a um dos
possíveis HSEs (históricos seriais) que podem ser formados a partir de T.
A correção de um histórico baseia-se na premissa de que cada transação que o formou é
20
Critério de correção é o critério usado para avaliar se algo é ou não correto e, especificamente neste contexto,
indica se um histórico preserva ou não a consistência do BD.
21
NT: Serializability.
22
NT: serializable.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 34 -
correta
23
. Em um HSE produzido pela execução de um conjunto T = {T
1
, T
2
, ... T
n
} de
transações, cada transação T
i
inicia sua execução sobre um estado consistente do BD e ao
concluir sua execução mantém o BD em um outro estado consistente. Assim, ao final da
execução de todas as transações componentes do conjunto T, o BD estará em um estado
consistente. Assim, podem ser feitas as seguintes assertivas: (i) todo HSE é correto, ou seja,
realiza uma transição de estados consistentes do BD; e (ii) todo HSV, por ser equivalente a
um histórico serial, é também correto.
As assertivas acima fazem parte da Serialidade [4,27,31,54], que consiste no referencial
teórico tradicionalmente usado para avaliar se um CC produz históricos corretos. De acordo
com essa noção, um histórico é correto quando ele é seriável. Assim, o objetivo de um CC
baseado na serialidade é produzir históricos que sejam seriáveis.
A equivalência por Estado Final
24
é um critério que pode ser usado por um CC baseado
na Serialidade para verificar se um histórico é seriável. Se um histórico é equivalente por
estado final a um HSE, diz-se que ele é seriável por Estado Final. Além desse critério, há os
critérios de equivalência por Visão e de equivalência por Conflito, os quais são descritos a
seguir.
Pelo critério da equivalência por Visão, um histórico é seriável caso alguma das
possíveis execuções seriais do mesmo conjunto de transações atenda os seguintes
requisitos: i) para cada transação executada, os valores iniciais dos itens de dados
lidos sejam iguais aos do HSV; e ii) a última transação que atualize cada item de
dado seja também a última no HSV. Neste caso, diz-se que o histórico é seriável por
Visão.
Pelo critério da equivalência por Conflito, um histórico é seriável caso ele seja
equivalente por conflito
25
a alguma das possíveis execuções seriais do mesmo
conjunto de transações que o formou. Neste caso, diz-se que o histórico é seriável
por conflito.
23
Vide a propriedade Consistência, na Subseção 2.3.2, e a propriedade Correção, na Subseção 2.4.1.
24
Vide Definição 6.
25
Vide Definição 8.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 35 -
Definição 8. Históricos equivalentes por conflito.
Dois históricos H
1
e H
2
são considerados equivalentes por conflito, simbolizado por
H
1
H
2
, caso as seguintes condições sejam satisfeitas:
Eles são definidos sobre o mesmo conjunto T = {T
1
, T
2
, … , T
n
} de transações e têm
as mesmas operações;
Eles ordenam da mesma forma as operações em conflito de transações não-
abortadas. Dessa forma, para quaisquer duas operações conflitantes p e q,
pertencentes, respectivamente, às transações necessariamente não-abortadas Ti e Tj,
tem-se que: se p <
H1
q, então p <
H2
q.
É importante ressaltar que a serialidade não é o único critério de correção de históricos,
ou seja, o conjunto de todos os possíveis HSVs representa apenas um subconjunto dos
possíveis históricos corretos. Isso significa que a execução não seriável de transações pode
também preservar um BD em um estado consistente.
2.4.3 Serialidade de históricos por conflito
Dentre os critérios de identificação de históricos seriáveis apresentados na Subseção
2.4.2, a equivalência por conflito é o mais restritivo, ou seja, permite identificar o menor
número de históricos seriáveis, o que leva a um menor grau de concorrência, dentre os três
critérios. Já a equivalência por estado final é o mais abrangente, ou seja, possibilita um maior
grau de concorrência. Apesar disso, o critério da equivalência por conflito é adotado como o
critério padrão porque seu processo de identificação de HSVs, a partir de um conjunto de N
transações, ocorre, no pior caso, em tempo de ordem N
2
, sendo assim uma complexidade de
grau polinomial. Nos outros critérios, a identificação é mais complexa, pois é realizada, no
pior caso, em tempo de ordem N! (fatorial de N), sendo assim uma complexidade não-
polinomial completa [54,62].
A verificação da serialidade por conflito de um histórico pode ser feita mediante o uso
do grafo de seriação (também chamado de grafo de precedência ou grafo de dependência).
Este é um grafo de arestas direcionadas, onde cada vértice representa uma transação que
estiver em execução e cada aresta, a qual liga dois vértices, indica a existência de um
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 36 -
conflito
26
entre duas operações. O vértice de origem e o vértice de destino da aresta em
questão representam as referidas transações. A direção de cada aresta determina a ordem em
que as transações em conflito deveriam ser executadas em um HSE equivalente por conflito
27
.
No Grafo de Seriação, poderão estar representadas transações ativas e transações efetivadas
28
que ainda tenham alguma operação em conflito com alguma transação ativa. Os HSVs não
apresentam ciclos em seus grafos de seriação [4].
2.4.4 Níveis de isolamento e problemas relacionados
O CC visa permitir a execução simultânea de transações concorrentes, evitando, por
outro lado, a produção de estados inconsistentes no BD. No intuito de estabelecer um ponto
de equilíbrio entre um razoável grau de concorrência e um nível confiável de consistência, o
CC deve utilizar um dos chamados Níveis de Isolamento dos efeitos de outras transações.
Tais níveis de isolamento estão associados ao uso da linguagem de banco de dados ANSI
SQL [3].
Os níveis de isolamento são numerados de 1 a 4. O nível 1, por exemplo, conhecido por
Leitura sobre valor não-efetivado
29
, oferece o maior grau de concorrência e, por outro lado,
uma maior exposição das transações em execução a estados intermediários inconsistentes
produzidos por outras transações, o que pode levar as transações em execução a gerar estados
inconsistentes no BD. Tais inconsistências podem ser causadas pelas chamadas Anomalias ou
Fenômenos. Cada nível de isolamento impede a ocorrência de todos os tipos de Anomalias
que são evitadas pelo nível de isolamento de número imediatamente inferior, além de evitar
pelo menos um tipo de Anomalia adicional.
Já o nível de isolamento de número 4, conhecido por Seriável, oferece o menor grau de
concorrência, mas garante o isolamento total das transações concorrentes, ou seja, a
serialidade. Os níveis de isolamento intermediários, ou seja, número 2 (Leitura sobre valor
efetivado
30
) e 3 (de Leitura Repetível
31
), oferecem progressivos níveis de
isolamento/consistência e regressivos graus de concorrência. O SGBD Oracle 9i [52], um dos
26
Vide Definição 4.
27
Vide Definição 8.
28
Vide estados possíveis de uma transação, na Subseção 2.3.1.
29
NT: read uncommitted.
30
NT: read commited.
31
NT: repeatable read.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 37 -
produtos líderes de mercado, implementa como opção padrão o nível de isolamento 2, embora
também ofereça a opção do nível 4.
A seguir, são descritos os problemas com os quais um CC deve lidar, relacionando-os
com os níveis de isolamento mínimos que evitam os mesmos.
Atualização inconsistente
32
. Este problema surge em decorrência da atualização-
sobre-valor-não-efetivado
33
e ocorre da seguinte forma: uma certa transação (T
1
)
realiza uma operação de escrita sobre um item de dado cujo valor atual foi
produzido por uma operação de escrita originada de uma outra transação (T
2
) ainda
não-efetivada. O aborto de uma das duas transações levará o BD a ficar em um
estado inconsistente. O Nível de Isolamento mínimo que evita tal problema é o 1
(um).
Leitura inconsistente
34
. Este problema ocorre na seguinte situação: uma transação
(T
1
) produz um valor que é lido por outra transação (T
2
) e esta vem a ser efetivada.
A transação T
1
, no entanto, é abortada logo em seguida. T
2
terá lido um estado do
BD que não era consistente, pois este não foi efetivado. T
2
deve, portanto, ser
desfeita, o que não é possível, pois ela já foi efetivada. Essa necessidade de abortar
T
2
é causada pela chamada dependência Escrita→Leitura entre as duas transações.
O Nível de Isolamento mínimo que evita tal problema é o 2 (dois).
Abortos em cascata
35
. Este problema ocorre na seguinte situação: uma transação
(T
1
) atualiza um item de dado e este é lido, em seguida, por outras transações. Antes
do término dessas outras transações, T
1
acaba sendo abortada, o que torna
inconsistentes as leituras feitas pelas outras transações, o que requer o aborto destas.
Cada transação abortada poderá gerar aborto de outras que dependiam dela e assim
sucessivamente, caracterizando os chamados abortos em cascata. O Nível de
Isolamento mínimo que evita tal problema é o 2 (dois).
Leitura não-repetível
36
. Este problema surge na seguinte situação: uma certa
transação (T
1
) realiza duas operações de leitura sobre o mesmo item de dado. Entre
essas duas operações, uma outra transação (T
2
) efetua uma operação de escrita sobre
32
NT: dirty write.
33
NT: write uncommitted
34
NT: dirty read
35
NT: cascading aborts.
36
NT: non-repeatable read, un-repeatable read ou fuzzy read.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 38 -
o mesmo item de dado e, logo em seguida, é efetivada. A segunda operação de
leitura de T
1
obtém um valor diferente da primeira operação de leitura, sendo esta
então uma leitura cujo valor não se repete, ou seja, uma leitura não-repetível (para o
mesmo valor). A essa dependência entre as operações dá-se o nome de dependência
Leitura
→
Escrita. O Nível de Isolamento mínimo que evita tal problema é o de
número 3 (três).
Atualização perdida
37
. Este problema ocorre da seguinte forma: uma certa transação
(T
1
) realiza uma operação de leitura e escrita sobre o mesmo item de dado. Entre
essas duas operações, uma outra transação (T
2
) efetua uma operação de escrita sobre
o mesmo item de dado e logo em seguida é efetivada, antes da execução da
operação de escrita de T
1
. A operação de escrita de T
1
acaba sendo executada sem
considerar a atualização feita por T
2
, que se torna então uma atualização perdida. O
Nível de Isolamento mínimo que evita tal problema é o 3 (três).
Atualização fantasma
38
. Este problema surge na seguinte situação: uma certa
transação (T
1
) realiza duas operações de leitura sobre um predicado
39
. Entre essas
duas operações de leitura, uma outra transação (T
2
) efetua uma operação de escrita
sobre um outro item de dado, de forma tal que este passe a satisfazer o predicado. A
segunda operação de leitura de T
1
obtém um valor diferente da primeira operação de
leitura. A mudança que ocorreu no resultado da primeira leitura, antes do término da
transação correspondente, é chamada de atualização fantasma. O Nível de
Isolamento mínimo que evita tal problema é o 4 (quatro).
A seguir, na Tabela 1, apresenta-se um resumo dos níveis de isolamento, relacionando-
os aos problemas que eles evitam. Tal resumo baseia-se nos dados apresentados em [3].
37
NT: lost update.
38
NT: phantom.
39
Vide Definição 4.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 39 -
Tabela 1 – Níveis de isolamento ANSI SQL
Problemas (anomalias ou fenômenos) que o nível de isolamento evita
Atualização
inconsistente
Leitura
inconsistente
Abortos em
cascata
Leitura não-
repetível
Atualização
perdida
Atualização
fantasma
Nível de
Isolamento
Sem
isolamento
Não Não Não Não Não Não
1 - Leitura
sobre valor
não-efetivado
Sim Não Não Não Não Não
2 – Leitura
sobre valor
efetivado
Sim Sim Sim Não Não Não
3 – Leitura
repetível
Sim Sim Sim Sim Não Não
4 – Seriável Sim Sim Sim Sim Sim Sim
2.4.5 Confiabilidade de históricos
Diversos fatores podem gerar falhas na operação de um SGBD, tais como falha interna
de transações, do sistema computacional ou da rede de comunicação de dados. As falhas do
SGBD podem afetar as propriedades de atomicidade e durabilidade das transações, o que
pode gerar estados inconsistentes do BD.
O CC deve ter um certo grau de confiabilidade para evitar a ocorrência de estados
inconsistentes do BD, em conseqüência de falhas do SGBD. Em geral, quanto maior for o
grau de confiabilidade de um SGBD, maior será a disponibilidade de acesso ao BD
correspondente e menor a incidência de problemas pós-falhas. Por outro lado, o grau de
concorrência tende a ser menor.
O grau de confiabilidade de um CC é determinado pelo tipo de histórico que ele produz.
Os tipos de históricos confiáveis são os seguintes: Recuperável, Livre de abortos em cascata,
Precisos e Rigorosos [4,28,62]. O tipo recuperável contém os requisitos mínimos para que um
histórico seja considerado confiável. Os demais tipos, além de serem recuperáveis, têm
características adicionais que tornam os históricos ainda mais confiáveis.
Definição 9. Transação T
i
lê da transação T
j
.
Em um histórico H, diz-se que uma transação T
i
∈ H lê o item de dado x da transação
T
j
∈H se [4]:
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 40 -
w
j
[x] < r
i
[x], ou seja, uma operação de escrita de T
j
sobre x precede a operação de
leitura de T
i
sobre x;
a
j
r
i
[x], ou seja, não há em H uma operação de aborto de T
j
que preceda a
operação de leitura de T
i
sobre x; e
Dado w
k
[x] ∈ T
k
, T
k
∈H, tal que w
j
[x] < w
k
[x] < r
i
[x], então a
k
< r
i
[x]. Isto significa
que se uma terceira transação T
k
tiver executado uma operação de escrita entre w
j
[x]
e r
i
[x], então T
k
deverá ter sido abortada antes de r
i
[x], ou seja, o valor que T
i
leu foi
escrito por T
j
e não por T
k
.
A seguir, são descritas as características de cada um dos tipos de históricos confiáveis,
relacionando-os com os problemas de concorrência (Anomalias) que eles evitam e os níveis
de isolamento
40
correspondentes.
Recuperável. Formalmente [4], diz-se que um histórico H é recuperável se, para
cada transação T
i
que lê de uma transação T
j
(Definição 9), ij, e que tiver sido
efetivada (i.e., c
i
∈ H), então c
j
< c
i
(i.e., a efetivação de T
j
é anterior à efetivação de
T
i
). Informalmente, pode-se dizer que, neste tipo de histórico, cada transação T
i
somente é efetivada após a efetivação de todas as transações ativas que tenham
realizado a última operação de escrita sobre algum item de dado lido por T
i
.
Assim,
evita-se que sejam gerados estados inconsistentes do BD que seriam provocados
pela efetivação de uma transação que atualizou o BD com base em valores
produzidos por pelo menos uma transação que foi abortada. Um histórico
recuperável evita a ocorrência do problema “leitura inconsistente”. Se for
considerado que a existência de w
i
[x] (isto é, uma operação de escrita da transação
T
i
sobre o item de dado x) presume a existência prévia de r
i
[x] em T
i
, então é
correto afirmar que o histórico Recuperável também evita a ocorrência do problema
“atualização inconsistente”, garantindo, assim, o nível isolamento de número 1
(um).
Livre de abortos em cascata. Formalmente [4], diz-se que um histórico H é livre de
abortos em cascata se, para cada transação T
i
que lê de uma transação T
j
(Definição
9), sendo ij, então c
j
< r
i
[x] (isto é, a efetivação de T
j
é anterior à leitura de x por
T
i
). Informalmente, pode-se dizer que, neste tipo de histórico, uma transação
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 41 -
somente pode realizar operações de leitura sobre itens de dados cujos valores
tenham sido gravados por ela mesma ou por transações já efetivadas. Este tipo de
histórico evita os problemas “Leitura inconsistente” e “Abortos em cascata”. Se for
considerado que a existência de w
i
[x] (isto é, uma operação de escrita da transação
T
i
sobre o item de dado x) presume a existência prévia de r
i
[x] em T
i
, então é
correto afirmar que o histórico Livre de abortos em cascata também evita o
problema “atualização inconsistente”, garantindo, assim, o nível de isolamento de
número 2 (dois). Este tipo de histórico é necessariamente recuperável, mas nem
todo histórico recuperável é necessariamente livre de abortos em cascata.
Preciso. Formalmente [4], diz-se que um histórico H é preciso (também chamado
“estrito”) se, sempre que w
j
[x] < o
i
[x], sendo ij e o
i
[x] = {r
i
[x],w
i
[x]}, então a
j
(ou
c
j
) < o
i
[x]. Informalmente, pode-se dizer que, neste tipo de histórico, nenhuma nova
operação (de leitura ou escrita) poderá ser realizada sobre um item de dado x antes
que tenha sido efetivada (ou abortada) a transação que tenha realizado a última
operação de escrita sobre x. Este tipo de histórico evita os problemas “Leitura
inconsistente”, “Abortos em cascata”, “Leitura não-repetível”, “Atualização
inconsistente” e “Atualização perdida”, garantindo, assim, o nível de isolamento de
número 3 (três). Esse tipo de histórico é necessariamente livre de abortos em
cascata, mas nem todo histórico livre de abortos em cascata é necessariamente
preciso.
Rigoroso. Formalmente [13], diz-se que um histórico H é rigoroso se, sempre que
o
i
[x] < o
j
[x], sendo ij e há conflito (Definição 4) entre o
i
[x] e o
j
[x], então a
i
(ou c
i
)
< o
j
[x]. Informalmente, pode-se dizer que, neste tipo de histórico, nenhuma nova
operação (de leitura ou escrita) poderá ser realizada sobre um item de dado x caso
exista alguma transação ativa que tenha executado uma operação conflitante sobre
x. Neste tipo de histórico, a ordem de efetivação de duas transações que tenham
conflitos entre si é a mesma ordem em que elas seriam executadas em um histórico
serial equivalente por conflito (vide Definição 8). Este tipo de histórico evita todos
os problemas de concorrência citados na Subseção 2.4.4, garantindo, assim, o nível
de isolamento de número 4 (quatro), o que garante a produção de históricos
40
Vide Anomalias, na Seção 2.4.4.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 42 -
seriáveis por conflito. O histórico rigoroso é necessariamente preciso, mas nem todo
histórico preciso é necessariamente rigoroso.
2.5. Protocolos para Controle de Concorrência
Conforme visto anteriormente, o CC de um SGBD realiza o recebimento de operações
(originadas de transações concorrentes e que acessam itens BD) e faz o entrelaçamento dessas
operações com base em um certo critério de correção e um certo grau de confiabilidade,
resultando em uma seqüência de execução das operações que garanta a transição de estados
consistentes do BD e assegure que o BD poderá ser recuperado a um estado consistente, no
caso de ocorrência de falhas. O CC é implementado por meio de um programa denominado
protocolo de controle de concorrência.
Há dois tipos de protocolos de controle de concorrência: os Agressivos e os
Conservadores [4]. Ambos os tipos visam assegurar a produção de históricos seriáveis por
conflito. A serialidade por conflito é, portanto, o critério de correção padrão para todos os
referidos protocolos. Nas próximas subseções, são descritos os citados protocolos, em maiores
detalhes.
2.5.1 Protocolos agressivos
Seu funcionamento básico consiste em sincronizar
41
as operações das transações, no
momento em que elas são recebidas. A execução de cada transação é dividida nas três fases
abaixo descritas [53,57], durante as quais o protocolo mantém uma lista de todos os itens de
dados lidos e escritos pela transação, até que esta seja efetivada ou abortada.
Processamento. Nesta fase, todas as operações são executadas, sendo que os valores
produzidos pelas operações de escrita são armazenados em uma área temporária
privativa da transação;
Validação. Esta fase é iniciada no momento em que a transação submete a operação
de efetivação. A partir deste ponto, o protocolo CC verificará se a inserção de
alguma das operações da transação, no histórico em formação, poderá violar a
correção deste. Em caso afirmativo, a transação será invalidada, abortada e
41
Neste contexto, sincronizar significa inserir no histórico em formação.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 43 -
reiniciada, sendo apagada sua área temporária privativa de armazenamento. Em
caso contrário, a transação será validada e seu processamento prossegue na fase de
Gravação;
Gravação. Nesta fase, as alterações que a transação fez nos dados são copiadas da
área temporária privativa da transação para o BD.
Os protocolos Agressivos subdividem-se em protocolos Pessimistas e Otimistas. Os
protocolos Pessimistas executam as fases na seguinte seqüência: Validação-Processamento-
Gravação. As implementações mais conhecidas deste subtipo de protocolo são: Ordenação
por Marca de Tempo [65] e Teste do Grafo de Seriação [18]. Os protocolos Otimistas
executam as fases na seguinte seqüência: Processamento-Validação-Gravação. A
implementação mais conhecida deste tipo de protocolo é o Certificador [41].
O protocolo de Ordenação por Marca de Tempo sincroniza as operações em conflito
com base nas suas marcas-de-tempo
42
, sendo que a marca-de-tempo de uma operação é igual
à marca-de-tempo de sua transação de origem. A marca-de-tempo de uma transação é
recebida logo ao ser iniciada sua fase de validação e corresponde a um número (sempre
crescente) calculado em função da data e da hora em que foi iniciada a validação da
transação. Neste protocolo, a seqüência relativa de execução de quaisquer duas operações em
conflito deve ser igual à seqüência relativa de ordenação crescente de suas respectivas
marcas-de-tempo. O critério usado por este protocolo para validar uma transação é verificar se
a inclusão de suas operações produz um histórico equivalente por conflito a uma execução
serial das transações executadas até o momento, ordenadas por suas respectivas marcas-de-
tempo.
O protocolo conhecido por Teste do Grafo de Seriação baseia-se no uso do Grafo de
Seriação (vide Subseção 2.4.3), que identifica conflitos existentes entre operações de
transações concorrentes. A cada transação iniciada, será incluído um vértice correspondente
no grafo. A cada operação recebida, o protocolo verifica se há conflito entre ela e as
operações originadas das outras transações ativas que estiverem representadas no grafo.
Caso exista conflito entre as operações, o protocolo incluirá no grafo, para cada conflito
detectado, uma aresta ligando os vértices correspondentes às transações cujas operações
42
NT: time-stamps.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 44 -
estiverem em conflito. A origem da aresta será o vértice que representa a transação cuja
operação já tiver sido sincronizada. O destino da aresta será o vértice que representa a outra
transação conflitante.
Após a inserção de cada aresta, o protocolo verificará se essa inclusão levou ao
surgimento de algum ciclo no grafo. Em caso afirmativo, a operação que gerou o ciclo será
rejeitada e a transação correspondente será abortada. O vértice que representa a transação
abortada e as arestas que chegam e saem do vértice serão todos excluídos do grafo. Caso não
tenha surgido ciclo no grafo, a operação em questão será aceita. Após a aceitação de todas as
operações de cada transação representada no grafo, a transação será efetivada e as arestas que
saem do vértice correspondente serão eliminadas do grafo. Além disso, caso não haja arestas
chegando ao referido vértice, este também será eliminado do grafo.
No caso do protocolo Certificador, cada transação ativa é associada, logo após o
término de sua fase de processamento e antes do início de sua fase de validação, a um número
seqüencial inteiro, digamos tn(j), sendo tn(j)= tn(i)+1, onde tn(i) corresponde ao valor do
último número seqüencial inteiro associado a alguma transação. Na fase de validação, a
seguinte regra deve ser válida para o histórico formado até o momento pelo CC: deve existir
um HSE (histórico serial) equivalente no qual uma transação qualquer T
i
ocorra antes de outra
transação qualquer T
j
, sempre que tn(i) < tn(j).
2.5.2 Protocolos conservadores
Este tipo de protocolo utiliza operações de bloqueio
43
para evitar que duas operações em
conflito acessem simultaneamente um item de dado. Dessa forma, cada operação somente
poderá ser executada após obter um bloqueio de acesso ao item de dado ao qual ela se refere.
Os bloqueios podem ser classificados quanto ao modo, quanto à duração e quanto à
abrangência.
Quanto à duração, um bloqueio pode ser: de curta duração ou de longa duração. Um
bloqueio é de curta duração quando sua liberação ocorre logo após a execução da operação
que o requisitou. Um bloqueio é de longa duração quando sua liberação ocorre somente após
o término da transação que o requisitou.
43
Uma tradução alternativa para o termo original, que é lock, seria “trava”. No entanto, optou-se neste trabalho
pela tradução “bloqueio”, encontrada em [28].
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 45 -
Quanto ao modo, um bloqueio pode ser: compartilhado ou exclusivo. O bloqueio
compartilhado é usado para operações de leitura. Quando uma transação obtém um bloqueio
compartilhado sobre um item de dado, outras transações poderão obter bloqueios
compartilhados sobre esse mesmo item. O bloqueio exclusivo é usado para operações de
escrita. Quando uma transação obtém um bloqueio exclusivo sobre um item de dado, outras
transações somente conseguirão obter novos bloqueios sobre esse item de dado após a
liberação do bloqueio exclusivo em questão.
Quanto à abrangência, um bloqueio pode ser: simples ou de predicado. Um bloqueio é
do tipo simples quando for obtido sobre um item de dado específico. Um bloqueio de
predicado é aquele obtido sobre um conjunto de itens de dados que satisfazem uma
determinada condição lógica. O bloqueio de predicado é implementado por meio de bloqueios
em arquivos de índices de dados [57].
Haja vista que um protocolo do tipo Conservador bloqueia temporariamente os itens de
dados, algumas operações não poderão ser executadas no momento em que são recebidas pelo
CC. Por esse motivo, as operações que não puderem ser executadas imediatamente serão
adiadas para sincronização posterior, no sentido de garantir a serialidade por conflito do
histórico em formação.
A implementação mais conhecida de um protocolo do tipo Conservador é o Bloqueio
em duas fases [27] (ou Bloqueio Bifásico). Outros protocolos também citados na literatura são
o Bloqueio Altruísta [60] e o Bloqueio Cooperativo [6].
2.5.3 Níveis de isolamento baseados em bloqueios
Na Subseção 2.4.4, foram apresentados os níveis de isolamento ANSI SQL e os
problemas que eles evitam. É relevante ressaltar que tais definições foram padronizadas no
sentido de permitir tanto a implementação de CC do tipo Agressivo (que não se baseia em
bloqueios) como do tipo Conservador (baseado em bloqueios), sendo este último o padrão de
implementação de CC [3,31].
Na Tabela 2, a seguir, descreve-se a correspondência entre os níveis de isolamento
ANSI SQL e os níveis de isolamento que podem ser obtidos pelo uso do mecanismo de
bloqueio. O nível de isolamento ANSI SQL de número 3, por exemplo, evita todas as
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 46 -
anomalias, à exceção da “Atualização perdida” e “Atualização fantasma”. Para obter o
mesmo nível de isolamento, um protocolo baseado em bloqueios deve manter bloqueios do
tipo longo sobre itens de dados e bloqueios do tipo curto para predicados.
Tabela 2 – Equivalência entre os níveis de isolamento baseados em bloqueios e os ANSI SQL
Problemas (anomalias ou fenômenos) que o nível de isolamento
evita
Duração dos
bloqueios de leitura
necessária para obter
nível de isolamento
equivalente
Atualização
inconsistente
Leitura
inconsistente
Abortos
em
cascata
Leitura
não-
repetí-
vel
Atualiz.
perdida
Atualiz.
fantas-
ma
Sobre
itens de
dados
Sobre
predicados
Nível de
Isolamento
Sem
isolamento
Não Não Não Não Não Não - -
1 - Leitura
sobre valor
não-
efetivado
Sim Não Não Não Não Não - -
2 – Leitura
sobre valor
efetivado
Sim Sim Sim Não Não Não Curto Curto
3 – Leitura
repetível
Sim Sim Sim Sim Não Não Longo Curto
4 – Seriável
Sim Sim Sim Sim Sim Sim Longo Longo
2.5.4 Problemas no término de transações
Além dos problemas vistos na Subseção 2.4.4 acima que podem violar a garantia de
consistência do BD, os protocolos de controle de concorrência devem lidar também com os
seguintes problemas que podem retardar excessivamente ou mesmo impedir o término do
processamento de transações [19]:
Bloqueio cíclico
44
. É um problema que pode ocorrer apenas com protocolos do tipo
Conservador. Ocorre em um conjunto eventual de transações, em que cada
transação aguarda pela liberação de um ou mais bloqueios mantidos por outra
transação do mesmo conjunto, de maneira que se forma um ciclo de espera. Nesse
ciclo, nenhuma das transações consegue prosseguir seu processamento, pois não
44
NT: deadlock.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 47 -
consegue liberar os seus bloqueios. É um problema também chamado de espera
circular.
Bloqueio Permanente
45
. É um problema que pode ocorrer apenas com protocolos do
tipo Conservador. Ocorre quando uma transação aguarda a obtenção de um bloqueio
em um item de dado, indefinidamente, devido ao fato de existir um fluxo contínuo
de transações que obtêm bloqueios sobre aquele item de dado sempre antes que
aquela transação consiga obter.
Reinício cíclico
46
. Ocorre quando um grupo de duas ou mais transações sempre
causam o aborto das outras desse grupo.
Reinício infinito
47
. Ocorre quando uma transação que solicita um determinado
bloqueio é sempre abortada e reiniciada, devido à existência de um fluxo contínuo
de transações cujas solicitações de bloqueios são sempre concedidas antes que
aquela transação consiga obter o bloqueio necessário.
As técnicas tradicionalmente usadas para reduzir a ocorrência de tais problemas são os
chamados Esquemas de Prioridade, dentre os quais, destaca-se a Estratégia Wound-Wait
(WW) e Wait-Die (WD), cujo funcionamento é descrito a seguir, resumidamente. Na fase de
validação
48
de cada transação, para cada operação dela que tiver conflito com alguma
operação de qualquer outra transação ativa, as marcas-de-tempo dessas transações serão
comparadas, sendo que a transação com marca de tempo menor será priorizada, seja através
da preempção ou do aborto da transação com marca de tempo maior. Tal estratégia apresenta,
no entanto, a desvantagem de poder reduzir o grau de concorrência e o desempenho geral do
SGBD.
2.5.5 Protocolos com múltiplas versões de dados
De forma geral, os protocolos de controle de concorrência baseiam-se na premissa de
que o BD conserva, em memória estável, num determinado instante, apenas uma versão (um
valor) para cada item de dado armazenado. O levantamento bibliográfico contido em [4]
informa que os principais protocolos, ou seja, o Bloqueio Bifásico, a Ordenação por Marca de
45
NT: permanent blocking.
46
NT: cyclic restarting.
47
NT: starvation, livelock, permanent restarting, restarting forever.
48
Vide fase de validação na Subseção 2.5.1.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 48 -
Tempo e o Teste do Grafo de Seriação, podem ser modificados para usarem múltiplas versões
dos itens de dados, implementando assim o conceito de Controle de Concorrência com
Múltiplas Versões. Nesse contexto, o SGBD mantém múltiplas versões para cada item de
dado armazenado no BD, de forma que transações concorrentes possam ler e escrever,
transparentemente, versões distintas do mesmo item de dado. Isso é possível desde que cada
transação acesse um conjunto consistente de versões para todos os itens de dados lidos e
escritos por ela. Nesse tipo de protocolo, as operações de leitura sempre são permitidas,
enquanto as operações de escrita passam por uma validação antes de serem permitidas.
Quando uma operação de escrita é aceita, o SGBD cria uma nova versão do item de dado
referenciado. O objetivo do protocolo é reduzir a ocorrência de operações rejeitadas na fase
de validação, o que aumentará o grau de concorrência do SGBD.
2.5.6 Comentários finais
De forma geral, cada protocolo de controle de concorrência é mais adequado para um
tipo de ambiente de processamento, considerando as várias possibilidades intermediárias entre
as seguintes situações extremas: ambientes de atualização intensiva de dados; e ambientes
restritos a consultas.
Um protocolo do tipo Agressivo é recomendado para aplicações em que a maioria das
transações não entra em conflito com as demais, na tentativa de acesso aos dados. Como
pontos positivos, destacam-se: o alto grau de concorrência que pode ser obtido; e o fato de
esse tipo de protocolo evitar os bloqueios cíclicos. Como pontos negativos, destacam-se: a
sobrecarga que o CC tem com a manutenção das listas de dados lidos e gravados, por cada
transação em execução, e com a verificação de conflitos na fase de validação; e o desperdício
de processamento e a queda de desempenho do SGBD, causados pela possibilidade de grande
ocorrência de transações reiniciadas. Os protocolos do tipo Agressivo têm sido usados
principalmente em SBDs distribuídos [57].
Um protocolo do tipo Conservador é indicado para aplicações em que a maioria das
transações entra em conflito com outras na tentativa de acesso a itens de dados. A resolução
desses conflitos pode ocorrer mediante o aborto ou suspensão temporária da execução de
algumas transações envolvidas no conflito. O ponto positivo de um protocolo do tipo
Conservador é a simplicidade de resolução dos conflitos entre transações, em comparação
com os protocolos Agressivos. O ponto negativo é a sobrecarga que o CC geralmente tem
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 49 -
com a lista de todos os bloqueios que as transações ativas obtiveram sobre itens de dados. Os
protocolos do tipo Conservador são os mais indicados para SBDs centralizados [57].
2.6. Bloqueio Bifásico
O Bloqueio Bifásico (BBF)
49
é um protocolo do tipo Conservador que é aceito como a
solução padrão para o controle de concorrência em SGBDs convencionais. As transações
submetidas ao BBF devem ser construídas de acordo com suas regras
50
, tendo em vista o
correto funcionamento do protocolo.
O BBF divide a execução de cada transação em duas fases: fase de Aquisição e fase de
Liberação de bloqueios. Na fase de Aquisição de bloqueios (também chamada fase de
Crescimento), a transação pode obter sucessivos bloqueios em itens de dados distintos. Para a
k-ésima operação O
ik
(x), sendo O
ik
(x) = {r(x) ou w(x)}, que a transação T
i
submeter ao CC,
este verifica se o bloqueio requerido pode ser concedido. Se o item de dado x já estiver
bloqueado por uma operação conflitante O
jl
(x), então o novo bloqueio não será concedido,
ficando a operação O
ik
(x) numa fila de espera para a obtenção do bloqueio necessário. Essa
obtenção ocorrerá somente quando o bloqueio atual for liberado e não houver nenhuma outra
operação à frente na fila de espera. Se, por outro lado, não houver bloqueio conflitante, então
o CC registra o bloqueio numa tabela de bloqueios e envia a operação para ser processada
pelo GD do SGBD. Somente após a confirmação de execução da operação pelo GD é que o
bloqueio concedido a Oik(x) poderá ser liberado.
A fase de aquisição termina no momento em que o CC faz a primeira liberação em
qualquer um dos bloqueios concedidos à transação T
i
. A partir desse ponto, a transação entra
na fase de Liberação de bloqueios (também chamada de fase de Encolhimento). Nessa fase, a
transação não mais poderá obter bloqueios em nenhum item de dado, mas apenas liberar
aqueles já obtidos. Ao término da transação, todos os bloqueios que ela retinha são liberados.
2.6.1 Lidando com bloqueios cíclicos
O BBF não evita a ocorrência dos bloqueios cíclicos, problema abordado na Subseção
49
NT: 2PL ou two-phase locking.
50
As transações que estão em conformidade com essas regras são conhecidas pela expressão original inglesa
well-formed 2PL transactions.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 50 -
2.5.4. Como forma de reduzir a ocorrência desse problema, o referido protocolo dispõe de
mecanismos de prevenção e de detecção/resolução de bloqueios cíclicos.
A prevenção pode ser feita pelo uso da Estratégia WW/WD, conforme visto na
Subseção 2.5.4 ou mediante uma outra estratégia em que, para cada transação iniciada, todos
os bloqueios que ela poderá precisar deverão ser adquiridos antes do efetivo início de
processamento da transação. Esta última estratégia consiste numa variação do BBF
denominada BBF-conservador.
Uma das formas de fazer a detecção e resolução de bloqueios cíclicos ocorre mediante o
uso de um tipo de grafo direcionado denominado Grafo de Espera
51
(GE). Nesse grafo, cada
vértice é uma transação em execução e cada aresta indica que a transação representada pelo
vértice de origem aguarda pela liberação do bloqueio de um item de dado obtido pela
transação representada pelo vértice de destino. Caso ocorra um ciclo no GE, então serão
abortadas uma ou mais transações, no sentido de desfazer o bloqueio cíclico. A maioria dos
SGBDs implementa o GE [57].
Uma outra forma de detecção e resolução de bloqueios cíclicos é usando o recurso do
limite de tempo esgotado
52
[4]. O CC monitora o tempo que cada transação ativa (em
execução) aguarda para adquirir um bloqueio. Se a transação não conseguir adquirir o
bloqueio em um limite máximo de tempo padrão definido, então a transação será abortada.
Essa forma de detecção não é precisa, pois não é certo que a transação abortada estivesse de
fato envolvida em uma situação de bloqueio cíclico. Naturalmente, esse método de
detecção/resolução de bloqueios cíclicos pode reduzir o desempenho do SGBD
correspondente, pois muitas transações poderão ser abortadas sem necessidade.
2.6.2 Variações do BBF
O BBF apresenta as seguintes variações: o BBF-conservador e o BBF-preciso. O BBF-
conservador, conforme visto na Subseção 2.6.1, tem a vantagem de prevenir a ocorrência de
bloqueios cíclicos. A desvantagem deste tipo de protocolo é que o grau de concorrência
poderá ser bastante reduzido, pois muitos itens de dados poderão estar sendo bloqueados antes
51
NT: waits-for graph.
52
NT: time-out.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 51 -
do momento necessário, ou poderão até mesmo nem ser usados, no caso de o acesso a eles
depender de uma condição que não ocorra na execução da transação.
O protocolo BBF-preciso
53
forma históricos rigorosos
54
, liberando todos os bloqueios
adquiridos por cada transação somente após o recebimento da respectiva operação de
efetivação. Tal técnica produz um histórico equivalente por conflito a uma execução serial das
transações executadas até o momento, ordenadas pela seqüência na qual elas foram
efetivadas. A desvantagem desse protocolo é que ele não previne a ocorrência de bloqueios
cíclicos, havendo a necessidade de uso de técnicas de detecção/resolução.
O BBF-preciso é a implementação padrão nos SGBDs comerciais, tais como IBM DB2,
Informix, Microsoft SQL Server e Sybase [57]. Por esse motivo, o restante desta dissertação
se referirá apenas a esta variação do BBF.
2.6.3 Aumento da concorrência
Tendo em vista aumentar o grau de concorrência do SGBD, o BBF poderá utilizar,
durante a fase de aquisição de bloqueios, o recurso da conversão de bloqueios, de forma a
usar o bloqueio mais restritivo (o exclusivo) somente quando necessário. Há dois tipos de
conversão de bloqueios: progressão de bloqueio
55
, que é a conversão de um bloqueio
compartilhado em exclusivo; e regressão de bloqueio
56
, que é a conversão de um bloqueio
exclusivo em compartilhado, somente permitida caso a transação não tenha modificado o item
de dado. Apesar das vantagens, esse recurso poderá aumentar a incidência dos bloqueios
cíclicos [4].
Outra forma de aumentar o grau de concorrência é o uso do bloqueio do tipo
atualização
57
, que indica que uma transação T
i
irá inicialmente executar uma operação de
leitura sobre um item de dado x, R
i
(x), e, posteriormente, irá executar uma operação de
gravação sobre o mesmo item de dado, W
i
(x). Uma vantagem desse tipo de bloqueio é que ele
poderá ser concedido mesmo que um bloqueio de leitura, sobre o mesmo item de dado, tenha
sido concedido para uma operação, Rj(x), de outra transação Tj, situação que não seria
permitida caso o bloqueio requisitado por Tj fosse do tipo exclusivo. Outra vantagem desse
53
NT: strict-2PL.
54
Vide conceito de histórico rigoroso na Subseção 2.4.5.
55
NT: lock upgrade.
56
NT: lock downgrade.
57
NT: update.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 52 -
tipo de bloqueio é que ele evita os bloqueios cíclicos provocados pela progressão de
bloqueios.
Uma outra alternativa para o aumento da concorrência é o emprego de versões múltiplas
dos itens de dados (visto na Subseção 2.5.5) para aumentar a concorrência específica das
operações de leitura. Nessa alternativa, somente as operações de escrita requerem operações
de bloqueio para serem executadas. Essa modalidade de protocolo está implementada no
SGBD Oracle 8 [57].
2.6.4 Vazão de processamento de transações
O aumento do grau de concorrência e a redução dos bloqueios cíclicos contribuem para
o aumento da vazão no processamento de transações
58
, ou seja, o aumento da quantidade de
transações efetivadas por unidade de tempo. Outras formas de aumentar a referida vazão são:
Reduzir a sobrecarga sobre o CC mediante o uso de bloqueios de múltiplos itens de
dados. Isso pode ser feito pelo uso do bloqueio com granulosidade múltipla [17].
Esta é uma técnica usada pela maioria dos SGBDs comerciais [57], permitindo que
os bloqueios sejam obtidos sobre um agrupamento de itens de dados, ou seja, itens
de dados que contêm outros itens de dados. Um exemplo de agrupamento é a
página, a qual pode agrupar vários registros. Um arquivo, por sua vez, pode agrupar
várias páginas e um BD pode agrupar vários arquivos. Em sua fase de
encolhimento, o BBF libera os bloqueios pela ordem crescente de granulosidade, ou
seja, primeiro o registro e, em seguida, a página, o arquivo e o BD. É importante
salientar que quanto maior for a granulosidade no bloqueio, menor será o grau de
concorrência do SGBD.
Bloquear os itens de dados com a menor granulosidade possível. Esse recurso
apresenta a desvantagem de reduzir o desempenho do SGBD, pois quanto menor for
a granulosidade dos bloqueios, maior será a sobrecarga operacional sobre o CC.
Reduzir o tempo durante o qual as transações retêm bloqueios. Isso pode ser
realizado implementando-se o Nível de Isolamento de número 2
59
. No entanto, não
58
NT: throughput.
59
Vide níveis de isolamento, na Subseção 2.4.4.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 53 -
haverá garantia de serialidade do histórico e, conseqüentemente, não haverá garantia
de consistência do BD.
Reduzir a quantidade de gargalos
60
no BD, ou seja, itens de dados que causam
lentidão no funcionamento do SGBD devido ao fato de serem acessados e
modificados com intensa freqüência.
2.6.5 Comentários finais
Conforme mencionado em [2,62], na ausência de informações adicionais sobre a
estrutura das transações e/ou sobre a forma e o momento de acesso aos dados de um BD, o
BBF é tanto necessário como suficiente para assegurar a correção e a confiabilidade dos
históricos produzidos em um SGBD, ou seja, a serialidade dos históricos. Por outro lado, nem
todos os possíveis históricos seriáveis poderão ser produzidos pelo BBF, o que indica a
necessidade de se desenvolver protocolos que ofereçam um maior grau de concorrência.
2.7. Gerenciador de Recuperação
Nesta seção, será descrita uma visão geral da funcionalidade do componente GR
(Gerenciador de Recuperação) do SGBD. Em seguida, será descrito especificamente o GR
ARIES, implementação padrão usada nos SGBDs comerciais.
2.7.1 Visão geral
A operação normal de um SBD pode ser interrompida por diversos tipos de falhas, tais
como: erros internos nos programas que acessam o SBD; falhas internas de alguns dos
componentes internos do SGBD; e falhas na parte física (hardware) ou no sistema
operacional (software básico) correspondente aos dispositivos computacionais onde o SBD
estiver armazenado e operando.
O GR (Gerenciador de Recuperação) [4,57,62] é o componente do SGBD que recupera
o BD a um estado consistente, após a interrupção da operação normal do SBD, objetivando
preservar as propriedades de Atomicidade e Durabilidade das transações executadas.
Considerando a ocorrência de uma falha na operação de um SGBD, a Atomicidade é
60
NT: hot spots.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 54 -
assegurada pela anulação das ações das transações que estavam ativas, no momento em que
ocorreu a interrupção na operação do SGBD. A Durabilidade é assegurada pela preservação
das ações das transações efetivadas.
O GR pode ser implementado de acordo com um dos seguintes tipos de protocolo: os
baseados em espelhamento-de-páginas
61
e os baseados em histórico-de-ocorrências
62
.
Somente o segundo tipo de protocolo é adequado a sistemas onde há a execução concorrente
de transações. Um exemplo de implementação do primeiro tipo de protocolo é o Sistema R
[32]. Um exemplo para o segundo tipo de protocolo é o ARIES [49], que é a implementação
comercial padrão para o GR.
Um GR baseado em histórico-de-ocorrências pode ser classificado de acordo com o
modo com que ele trata as operações de escrita (atualização) sobre itens do BD. No modo
tomar-memória
63
, o GR poderá liberar páginas da memória principal que contêm dados
gravados por transações ainda não efetivadas, fazendo com que tais dados sejam escritos em
memória estável, ou seja, no BD. No modo forçar-escrita
64
, o GR poderá forçar que, a cada
transação efetivada, os dados que ela modificou sejam imediatamente copiados da memória
principal para a memória estável. O ARIES usa a abordagem tomar-memória e não-forçar-
escrita.
2.7.2 Sistema ARIES
O sistema ARIES é considerado o mecanismo de recuperação de BD que está no
estado-da-arte, pois fornece um alto grau de paralelismo, reduz a sobrecarga na operação de
registro no histórico-de-ocorrências e minimiza o tempo de recuperação. A seguir, será visto,
resumidamente, o seu funcionamento.
Durante a operação normal do SGBD, o ARIES realiza os seguintes procedimentos:
Registra, em um arquivo-de-ocorrências
65
(sendo este localizado em uma área de
memória persistente), informações sobre todas as operações de escrita executadas
sobre itens do BD. Esse registro deve ser realizado antes que as operações de escrita
sejam efetivamente gravadas no BD. Essa característica (ou propriedade) é chamada
61
NT: shadow paging.
62
NT: log-based schemes.
63
NT: stealing-frames.
64
NT: forcing-pages.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 55 -
de registro-antecipado-de-ocorrências
66
. O registro de informações do ARIES leva
em consideração os bloqueios de múltipla granulosidade
67
.
Registra periodicamente, no BD, informações coletadas em um dado momento
sobre as transações ativas, seus estados e os endereços dos mais recentes registros-
de-ocorrências
68
gerados em nome delas. Além disso, são também registradas
informações sobre os dados presentes na memória e ainda não gravados
definitivamente no BD. Esse registro representa um ponto-de-verificação
69
e sua
finalidade é reduzir o tempo gasto na busca e execução das informações necessárias
para efeito de recuperação do BD.
Ao ocorrer alguma falha que interrompa a operação normal do SGBD, o ARIES, após o
reinício da operação do SGBD, realiza os procedimentos descritos a seguir, os quais estão
divididos em três fases:
Análise. Nesta fase, são identificados, pela consulta ao mais recente registro de
ponto-de-verificação, quais eram, no momento em que o SGBD falhou, as
transações ativas e quais eram os itens de dados cujos valores haviam sido
modificados, mas ainda não haviam sido gravados no BD. Esta fase determina o
ponto de partida, no arquivo-de-ocorrências, a partir do qual a segunda fase deverá
ser executada. Além disso, são também determinadas quais transações não haviam
sido efetivadas no momento da falha do SGBD. Tais transações são denominadas
transações-vítimas
70
;
Executar-novamente
71
. Nesta fase, serão executadas novamente, a partir do primeiro
registro imediatamente seguinte ao último registro de ponto-de-verificação, todas as
operações de escrita representadas pelos registros do arquivo-de-ocorrências cujos
efeitos não tenham sido refletidos no BD. O objetivo dessa fase é reconstituir o BD
ao estado em que ele se encontrava no momento da falha do SGBD; e
65
NT: log file.
66
NT: write-ahead log (WAL).
67
Vide conceito na Subseção 2.6.4.
68
NT: log record.
69
NT: checkpoint.
70
NT: loosers.
71
NT: redo.
SESAMO – F.Stefan Gerenciamento de Transações em um SBD - 56 -
Desfazer-transações
72
. Nesta fase, serão desfeitas, em ordem cronológica inversa,
todas as operações de escrita, relativas às transações-vítimas, que estejam
representadas nos registros do arquivo-de-ocorrências.
2.8. Resumo do capítulo
Neste capítulo, foram vistos conceitos gerais sobre o gerenciamento clássico de
transações em um SGBD e, mais especificamente, sobre o componente CC (controlador de
concorrência), o qual objetiva preservar o isolamento das transações executadas
simultaneamente com vistas a garantir a consistência do BD. O CC controla a ordem em que
são executadas as operações de transações concorrentes, formando assim um histórico de
execução das operações, ou, simplesmente, um histórico. De acordo com o critério clássico de
controle de concorrência, o CC deve produzir um histórico seriável, ou seja, um histórico que
produz um estado do BD idêntico ao que seria produzido por alguma das possíveis execuções
seriais do conjunto de transações que formou aquele histórico. A implementação de um CC é
feita pelo uso de um protocolo de controle de concorrência. O protocolo padrão de mercado é
denominado BBF-preciso, o qual assegura a formação de um histórico seriável. Como será
visto no Capítulo 4, as regras do BBF-preciso são usadas como base de referência e
comparação com o protocolo de controle de concorrência proposto nesta dissertação, ou seja,
o SESAMO.
O BBF-preciso foi concebido para um SBD centralizado, ou seja, um SBD cujo BD está
centralizado em um único computador. No próximo capítulo, serão vistos conceitos sobre o
gerenciamento de transações e o controle de concorrência em SBDs distribuídos, múltiplos e
com suporte à mobilidade. Além disso, será vista a relação do BBF-preciso com o BBF-
distribuído, protocolo concebido para SBDs distribuídos.
72
NT: undo.
- 57 -
CAPÍTULO III
GERENCIAMENTO DE TRANSAÇÕES EM
SBDs DISTRIBUÍDOS, MÚLTIPLOS E
MÓVEIS
- 58 -
3. Gerenciamento de Transações em SBDs distribuídos, múltiplos
e móveis
Neste capítulo, apresenta-se a atividade de gerenciamento de transações nos SBDs
distribuídos, múltiplos e móveis. Inicialmente, são apresentados conceitos gerais sobre os
SBDs distribuídos. Em seguida, são apresentados o controle de concorrência e o
gerenciamento de recuperação em SBDs distribuídos. Ao final, são apresentados alguns
conceitos gerais, as arquiteturas e a atividade de controle de concorrência dos SBDs múltiplos
(SBDMs) em geral e SBDMs com suporte à computação móvel.
3.1. Conceitos gerais em SBDs distribuídos
Os SBDs convencionais foram concebidos para funcionar de forma centralizada, ou
seja, em um único sistema computacional. O surgimento da necessidade dos usuários em
compartilhar e integrar os recursos de distintos e independentes SBDs centralizados pré-
existentes, como também a necessidade de serem desenvolvidas aplicações que distribuíssem
o processamento e/ou o armazenamento de dados através de sistemas computacionais
distintos e até mesmo geograficamente distribuídos, motivou a concepção e o
desenvolvimento dos SBDs distribuídos.
3.1.1 Visão geral de um SBD distribuído
Um sistema computacional distribuído é aquele formado por dispositivos de
computação autônomos que geralmente têm certo grau de homogeneidade
73
em suas
plataformas operacionais, estão interligados por uma rede de comunicação e que cooperam
para o processamento de suas tarefas. Um SBD distribuído [53,57] é um sistema
computacional distribuído que gerencia um BD distribuído (BDD). Um BDD é uma coleção
de BD logicamente inter-relacionados, em que cada BD está fisicamente localizado em um
nó
74
distinto de uma rede de computação. As seguintes características e funcionalidades
deverão existir em um SBD distribuído:
73
Neste contexto, a homogeneidade refere-se à compatibilidade entre as tecnologias com as quais cada produto
foi desenvolvido.
74
Sistema computacional que faz parte de uma rede de computadores.
SESAMO – F.Stefan GT em SBDs DMMs - 59 -
Cada nó da rede representa um SBD que possui uma cópia do SGBD distribuído e
que gerencia o BD local, de forma autônoma. O SBD de cada nó é chamado de
SBD-componente (SBDC);
O SBD distribuído deve esconder dos usuários a complexidade de acesso, em um
ambiente distribuído, aos recursos de gerenciamento de bancos de dados,
fornecendo acesso transparente aos mesmos;
O SBD distribuído deve fornecer aos seus usuários a execução transparente das
funções de armazenamento e acesso aos dados, em termos de distribuição física,
replicação
75
e fragmentação
76
;
O SBD distribuído deve fornecer aos seus usuários a execução transparente das
funções de gerenciamento de transações, ou seja, controle de concorrência e
recuperação; e
O SBD distribuído deve garantir a independência das aplicações em relação às
alterações físicas e lógicas que venham a ser feitas nos dados e, da mesma forma,
dos dados em relação às aplicações.
Algumas implementações de SBDs distribuídos são: SDD-1 [5], R* [50], Oracle 9i [51]
e IBM DB2 [37].
3.1.2 Transação distribuída
As aplicações-clientes de um SBD centralizado interagem com este por meio de
transações locais, que consistem em transações que se originam de e são processadas pelo
mesmo sistema computacional. Em um SBD distribuído, a interação das aplicações-clientes
ocorre por meio das chamadas transações distribuídas.
Uma transação distribuída (Definição 10) caracteriza-se por ter operações que deverão
ser processadas por um ou mais SBDs remotos
77
, podendo haver ou não a participação do
SBD local no processamento. Cada SBD que participa de uma transação distribuída é
75
Técnica que consiste em manter réplicas dos itens de dados, visando aumentar a disponibilidade de acesso aos
mesmos.
76
Técnica que consiste em dividir os itens de dados em fragmentos, armazenando estes em locais físicos
distintos de tal forma que cada um destes fragmentos esteja o mais próximo possível dos prováveis usuários,
com o propósito de diminuir o tempo de acesso aos dados.
77
O termo remoto, neste contexto, significa estar situado em um nó da rede distinto daquele em que a transação
distribuída foi iniciada.
SESAMO – F.Stefan GT em SBDs DMMs - 60 -
chamado de nó-participante. O agrupamento de todas as operações da transação distribuída
que serão processadas por um mesmo SBD tem o nome de subtransação (ST). Cada um dos
nós participantes de uma transação distribuída recebe e executa, por meio de seu respectivo
CC local, as operações das STs, além de processar normalmente as operações de suas
transações locais.
Em [33], os autores argumentam que, no modelo que representa uma transação
distribuída, há um processo, denominado mestre, o qual é executado no computador em que a
transação é submetida. Há também um conjunto de outros processos, denominados
seguidores, os quais executam operações, em nome da transação, nos diversos computadores
que são acessados pela transação.
Definição 10. Transação distribuída.
Uma transação distribuída T
i
é uma transação (Definição 3) com as seguintes
características [53]:
1) T
i
= {Σ
i
, <
i
}, Σ
i
= OS
i
U {N
i
}, OS
i
é o conjunto de todas as operações O
ij
(x) em
T
i
, O
ij
(x) é uma operação da transação T
i
que se refere ao item x de um BD, O
ij
(x)
∈
{r(x),w(x)}, N
i
é a condição de término para T
i
e N
i
∈
{a,c};
2) ∀ O
ij
(x), O
ij
(y) ∈ OS
i
, tem-se que (x,y ∈ BD
j
) ou (x ∈ BD
j
e y ∈ BD
k
), sendo
que BD
j
e BD
k
representam BDs distintos;
3) Para cada duas operações O
ij
e O
ik
∈ OS
i
, se O
ij
∈ {r(x),w(x)} e O
ik
= w(x), ∀ x,
então: O
ij
<
i
O
ik
ou O
ik
<
i
O
ij
; e
4) ∀ O
ij
∈ OS
i
, O
ij
<i N
i
.
3.1.3 Arquiteturas de SBDs distribuídos
Do ponto de vista do grau de distribuição das funções do SGBD, os SBDs distribuídos
podem ser classificados de acordo com uma das seguintes arquiteturas: Cliente-Servidor
78
,
Colaborativo
79
e Mediador
80
[57].
78
NT: Client-Server.
79
NT: Collaborating Server ou Peer-to-Peer. Outros nomes para esta arquitetura são: sistemas cooperativos ou
completamente distribuídos.
80
NT: Middleware.
SESAMO – F.Stefan GT em SBDs DMMs - 61 -
Nos sistemas com arquitetura do tipo Cliente-servidor, dois tipos de sistemas
computacionais interagem para o gerenciamento de transações distribuídas: os clientes e os
servidores. Um sistema computacional cliente, por meio de suas aplicações, requisita, a um
SBD situado em um outro sistema computacional (o servidor de BD), a criação e o
processamento de uma transação distribuída. O SBD ficará encarregado de criar e executar a
transação e as STs necessárias, coletando os resultados do processamento e os enviando ao
cliente.
Nos sistemas com arquitetura do tipo Colaborativo, uma coleção de SBDs autônomos
colabora mutuamente, de forma que qualquer um deles pode gerar uma transação distribuída,
dividi-la em STs, e enviar cada uma dessas STs a um dos SBDs da coleção, cujo SGBD local
coordenará a execução das respectivas operações da ST (subtransação). Exemplos: SDD-1 [5]
e R* [50].
Nos sistemas com arquitetura do tipo Mediador, existe uma aplicação intermediária (o
chamado mediador), implementada sobre um determinado SBD, de forma que este último
possa gerenciar as seguintes tarefas: recebimento das transações distribuídas; divisão das
transações distribuídas em STs; envio das STs aos respectivos SBDs participantes da
transação; e o envio dos resultados do processamento aos nós da rede que requisitaram as
transações distribuídas. Nesta arquitetura, o gerenciador local de transações de cada SBD-
participante coordena a execução das STs que ele recebe. Por outro lado, somente o SBD
sobre o qual estiver implementado o mediador terá condições de lidar com transações
distribuídas.
Em alguns tipos de SBDs cliente-servidor, as funções de interoperabilidade ficam ao
encargo de sistemas mediadores, resultando em uma arquitetura de três camadas. Tal
arquitetura tem sido usada de forma crescente nas aplicações comerciais, principalmente no
âmbito da Internet. Nessa arquitetura, cada camada representa sistemas computacionais
especializados, em vez de sistemas computacionais de propósito geral [53]. As camadas são:
Servidores de clientes: esta camada processa as interfaces dos usuários com as
aplicações e com os BDs.
Servidores de aplicação: esta camada processa as aplicações.
Servidores de BD: esta camada executa os serviços de gerenciamento de BDs.
SESAMO – F.Stefan GT em SBDs DMMs - 62 -
3.1.4 Requisitos do gerenciamento de transações distribuídas
Nos SBDs distribuídos, os nós participantes de cada transação distribuída devem se
comunicar para que sejam asseguradas as propriedades ACID (vistas na Subseção 2.3.2) da
referida transação e das STs dela decorrentes. Em função das características da computação
distribuída, é necessário que o SBD distribuído gerencie os efeitos das possíveis falhas que
podem ocorrer com a rede de comunicação ou com o sistema computacional de cada nó-
participante. Assim, além dos problemas usuais de concorrência em um SBD centralizado
(vistos na Subseção 2.4.4), os seguintes problemas deverão ser levados em conta pelo GT de
cada nó participante de uma transação distribuída [29]:
Violação parcial da autonomia dos SBDs locais. Este problema pode ocorrer como
conseqüência, por exemplo, da necessidade de preservar a atomicidade de uma
transação distribuída, impedindo que cada ST dela decorrente seja efetivada de
forma autônoma pelo respectivo SBD local.
Desperdício de processamento. Este problema pode ser causado, por exemplo, pela
necessidade de abortar uma transação distribuída de longa duração para efeito de
preservar a sua atomicidade, em decorrência do aborto de uma de suas STs.
Devido aos supracitados problemas, os mecanismos convencionais de gerenciamento de
transações, normalmente usados em SBDs centralizados, são inadequados para serem usados
em SBDs distribuídos, fator este que motivou o desenvolvimento de soluções mais adequadas
para o gerenciamento de transações em SBDs distribuídos. Nas próximas seções, serão
abordados aspectos de controle de concorrência e gerenciamento de recuperação, específicos
para o ambiente dos SBDs distribuídos.
3.2. Controle de concorrência em SBDs distribuídos
O controle de concorrência é um dos problemas mais extensivamente estudados na área
dos SBDs distribuídos [53]. Em um SBD distribuído, o controle de concorrência é realizado
pelo CC-distribuído, o qual representa o conjunto dos CCs dos SBDCs.
A função principal do CC-distribuído é assegurar que seja preservada a consistência dos
BDs por ele acessados, em um ambiente distribuído e multiusuário, por meio da produção de
históricos globais seriáveis e recuperáveis, formados pela execução de transações distribuídas.
SESAMO – F.Stefan GT em SBDs DMMs - 63 -
Além disso, o CC-distribuído deve também maximizar a vazão
81
no processamento de
transações e reduzir o tempo de resposta no processamento.
3.2.1 Protocolos de Controle de Concorrência em SBDs distribuídos
A abordagem utilizada em [53] classifica os protocolos de concorrência para SBDs
distribuídos de forma análoga àquela feita para os SBDs centralizados (vista na Seção 2.5),
reagrupando aqueles protocolos em duas categorias básicas: os Otimistas e os Pessimistas. Os
Otimistas dividem a execução de cada transação nas seguintes fases: leitura-computação-
validação-gravação. Os Pessimistas dividem a execução de cada transação nas mesmas quatro
fases, embora numa seqüência diferente, ou seja, validação-leitura-computação-gravação.
Na referida abordagem, tanto os protocolos Otimistas como os Pessimistas podem ser
implementados por meio de mecanismos que usam bloqueios ou que usam a ordenação por
marcas de tempo, os quais, segundo os autores, são os mecanismos primitivos de controle de
concorrência. Além disso, os protocolos Pessimistas podem também ser implementados por
meio de mecanismos híbridos, combinando características dos dois outros mecanismos.
Ainda de acordo com a referida abordagem, os protocolos Otimistas não têm sido
implementados de fato e, além disso, as pesquisas para sua utilização têm sido mais voltadas
para SBDs centralizados e não para SBDs distribuídos. Assim, os protocolos Pessimistas têm
sido o foco de atenção das pesquisas sobre mecanismos de controle de concorrência para
SBDs distribuídos e, por esse motivo, o presente capítulo desta dissertação adotará o mesmo
foco.
Os protocolos Pessimistas que usam bloqueios podem ser subdivididos em três tipos: o
centralizado; o baseado em cópia primária
82
; e o distribuído. Uma das implementações desse
último tipo é o protocolo chamado BBF-distribuído, o qual se constitui em um dos protocolos
mais usados nos SGBDs distribuídos comerciais. Maiores detalhes sobre o BBF-distribuído
serão vistos na subseção seguinte.
Os protocolos Pessimistas baseados em ordenação por marcas de tempo podem ser
subdivididos nos seguintes tipos: o básico; o multiversão; e o conservador. O tipo básico tem
a vantagem de nunca causar bloqueios cíclicos, mas tem a desvantagem de poder apresentar
81
NT: throughput.
82
NT: primary-copy.
SESAMO – F.Stefan GT em SBDs DMMs - 64 -
um alto nível de reinícios cíclicos e infinitos, o que pode causar um impacto negativo no
desempenho do SBD. O tipo conservador tem a vantagem de evitar a rejeição de operações
recebidas, mas pode causar bloqueios cíclicos. Esse tipo tem ainda a capacidade de reduzir a
ocorrência de reinícios cíclicos e infinitos, embora não os elimine completamente. O tipo
multiversão tem por objetivo eliminar o problema dos reinícios cíclicos e infinitos. Uma de
suas implementações foi feita no SDD-1 [5]. Tal implementação se baseia no estabelecimento
prévio, durante a fase de projeto do SBD distribuído, das possíveis classes de transações e dos
possíveis conflitos que podem existir entre essas classes, de forma a reduzir a carga de
trabalho do CC, na fase de operação do SBD distribuído.
No contexto dos SBDs distribuídos, os protocolos Pessimistas baseados em ordenação
por marcas de tempo funcionam de forma semelhante à que ocorre nos SBDs centralizados,
conforme visto na Subseção 2.5.1. Uma das diferenças básicas é que a marca de tempo de
uma transação distribuída é formada por um par de identificadores, que são: o identificador do
nó onde a transação foi gerada, ou seja, o nó-coordenador; e o valor do contador de transações
do nó-coordenador, que representa um número seqüencial progressivo.
3.2.2 BBF-distribuído
Em [53,62], é apresentado o protocolo BBF-distribuído, ou seja, bloqueio bifásico
distribuído. Nesse protocolo, a transação distribuída é gerenciada pelo GT do nó onde a
mesma foi originada, sendo este chamado de nó-coordenador. Em cada nó participante de
uma transação distribuída, deve existir um CC local que deve seguir o protocolo BBF, como
também deve existir o correspondente GD local (conceito descrito na Seção 2.1). Caso os nós-
participantes implementem o BBF-preciso (visto na Subseção 2.6.2), então os CCs locais
correspondentes terão autonomia e informação suficientes para decidirem quando processar as
operações das STs, sem dependerem de comunicação com os CCs do nó-coordenador ou
qualquer outro nó-participante.
O BBF-distribuído processa uma transação distribuída em quatro etapas. A primeira
etapa consiste no recebimento de operações da transação pelo nó-coordenador, o qual solicita
os correspondentes bloqueios (nos itens de dados) aos CCs locais dos nós-participantes onde
os itens de dados estiverem armazenados. O nó-coordenador continua normalmente
processando as próximas operações, sem ter que esperar por mensagens de concessão dos
bloqueios solicitados. Na segunda etapa, os CCs locais obtêm os bloqueios necessários e
SESAMO – F.Stefan GT em SBDs DMMs - 65 -
repassam as operações aos respectivos GDs locais, os quais executam as operações. Na
terceira etapa, esses GDs enviam confirmações de execução das operações ao nó-
coordenador. Após o nó-coordenador receber a confirmação de execução de todas as
operações que ele solicitou, bem como a operação de efetivação da transação distribuída, o
processo entra em sua quarta etapa. Nessa etapa, o nó-coordenador envia a operação de
efetivação para todos os CCs locais, os quais, após executarem as operações de efetivação em
seus respectivos nós, liberam os itens de dados que até então estavam bloqueados em favor da
transação distribuída em questão.
Além da possível ocorrência de bloqueios cíclicos locais em cada um dos nós-
participantes, há também a possibilidade de ocorrência de bloqueios cíclicos em um grupo de
transações distribuídas concorrentes, sendo assim chamado de bloqueio cíclico distribuído ou
bloqueio cíclico global (BCG). De forma análoga ao que ocorre com o BBF tradicional
83
(Seção 2.6), o BBF-distribuído dispõe de mecanismos de prevenção, detecção e resolução de
BCGs.
O mecanismo de prevenção usa as mesmas técnicas usadas pelo BBF centralizado,
segundo as quais as transações mais antigas têm prioridade sobre as mais novas. O
mecanismo de detecção e resolução é implementado pela construção periódica do chamado
grafo de espera global (GEG), sendo este semelhante ao grafo de espera (visto na Subseção
2.6.1), em que se faz a verificação da existência de ciclos correspondentes aos BCGs. A
detecção pode ser feita de duas formas, a centralizada e a distribuída. Na forma centralizada, o
nó-coordenador recebe periodicamente dos outros nós os dados para a atualização do GEG.
Havendo a ocorrência de ciclo no GEG, o protocolo então aborta as transações mais recentes
que estiverem envolvidas no ciclo. Na forma distribuída, o GEG migra através dos nós-
participantes, onde ocorre a sua atualização. Durante a atualização do GEG, em um nó-
participante, caso surjam ciclos no GEG, o BBF-distribuído aborta as transações distribuídas
mais recentes, originadas localmente e que estiverem envolvidas nos ciclos detectados.
Por fim, vale salientar que o BBF-distribuído gerencia a concessão e a liberação de
bloqueios em itens de dados acessados pelas transações de forma implícita, ou seja, de forma
que as transações não precisem especificar em que momento os bloqueios sobre os itens de
dados deverão ser adquiridos ou liberados. Algumas implementações do BBF-distribuído são:
System R* [50] e NonStop SQL [63].
83
Para diferenciar melhor os conceitos, o BBF tradicional será referido daqui por diante por BBF centralizado.
SESAMO – F.Stefan GT em SBDs DMMs - 66 -
3.3. Recuperação de SBDs distribuídos
Semelhante ao que foi visto no estudo dos SBDs centralizados (Seção 2.7), o
gerenciamento de recuperação em SBDs distribuídos deve assegurar a preservação das
propriedades de atomicidade e durabilidade das transações distribuídas.
A durabilidade de cada transação distribuída fica assegurada por conta dos respectivos
protocolos de recuperação dos SBDCs que participam da transação. Haja vista que cada
SBDC é geralmente um SBD centralizado e considerando que já foi apresentado o protocolo
de recuperação padrão (Subseção 2.7.2), esta dissertação não abordará protocolos de
recuperação específicos para o caso dos SBDs distribuídos.
A atomicidade de cada transação distribuída fica assegurada pelo uso de um protocolo
de efetivação atômica, o qual visa garantir que todas as STs originadas de uma mesma
transação distribuída apresentem o mesmo estado
84
. A seguir, serão vistos os protocolos de
efetivação atômica mais conhecidos, ou seja, a Efetivação Bifásica, tido como o padrão dos
sistemas comerciais [46], e a Efetivação Trifásica.
3.3.1 Efetivação Bifásica
Em [1,4,20,31,33,53,57,62], é apresentado o protocolo de efetivação atômica
denominado Efetivação Bifásica
85
(EBF). É um protocolo realizado pela troca de mensagens
entre os nós participantes de cada transação distribuída, ou seja, o nó-coordenador e os demais
nós-participantes, também chamados de nós-subordinados (no contexto de uma dada
transação distribuída). É a implementação padrão em SGBDs comerciais. Algumas de suas
implementações são: LU 6.2, OSI TP e RDA. A seguir, será visto de forma resumida, o
funcionamento do EBF para uma dada transação distribuída T
i
qualquer. Neste contexto, não
será considerada a possibilidade de ocorrência de falhas de comunicação ou de falhas nos nós
participantes da transação distribuída.
Fase de Votação. Esta fase é iniciada no momento em que o nó-coordenador recebe de
T
i
a operação de efetivação, o que ocorre somente após todos os nós-subordinados de T
i
terem
informado ao nó-coordenador que suas respectivas STs já foram executadas, mas não
efetivadas.
84
Vide estados possíveis de uma transação na Subseção 2.3.1.
SESAMO – F.Stefan GT em SBDs DMMs - 67 -
O nó-coordenador envia a cada um dos nós-subordinados uma solicitação de voto sobre
o que fazer com T
i
, ou seja, abortá-la ou efetivá-la. Essa solicitação é chamada de mensagem
de preparação para efetivação
86
. Antes do envio efetivo da referida mensagem, o nó-
coordenador inclui um registro no seu histórico local de ocorrências, de forma semelhante ao
que ocorre com os SBDs centralizados (Subseção 2.7.2), contendo os seguintes dados: o tipo
da ocorrência, que no caso é “início-ebf”; a identificação de T
i
; e a identificação dos nós-
subordinados de T
i
.
Ao receber do nó-coordenador a mensagem de preparação para efetivação, cada nó-
subordinado enviará seu voto, de acordo com a situação de execução da ST local. Se a ST não
tiver sido abortada pelo gerenciador local de transações, situação que pode ocorrer de forma
independente e unilateral, o nó-subordinado enviará o voto de efetivação. Caso contrário, o
nó-subordinado enviará o voto de aborto. Em ambos os casos, o gerenciador local de
transações do nó-subordinado insere um registro no histórico local de ocorrências, antes do
envio de seu voto. O referido registro conterá os seguintes dados: a decisão tomada (efetivar
ou abortar); a identificação de T
i
; e a identificação do nó-coordenador. Se a decisão tiver sido
“efetivar”, então a identificação dos outros nós-subordinados também será acrescentada ao
referido registro. Essa identificação é extraída da mensagem de preparação para efetivação,
anteriormente recebida do coordenador.
Fase de Decisão. Esta fase é iniciada no momento em que o coordenador de Ti tiver
recebido os votos de todos os nós-subordinados. Nesta fase, o nó-coordenador decidirá se Ti
deverá ser efetivada ou abortada, de acordo com os seguintes critérios:
Se os votos de todos os nós-subordinados forem pela efetivação, então a decisão
dependerá do voto do coordenador. Se esse voto for pela efetivação, então a decisão
será a de efetivar Ti. Caso contrário, a decisão será a de abortar Ti.
Se algum dos votos dos nós-subordinados for pelo aborto de Ti, então a decisão será
a de abortar Ti.
Quando a decisão (abortar ou efetivar Ti) tiver sido tomada, o nó-coordenador insere,
no histórico local de operações, um registro que contém os seguintes dados: a decisão tomada;
a identificação de T
i
; a identificação do nó-coordenador; e a identificação dos nós-
85
NT: Two-Phase Commit (2PC).
86
NT: Prepare-to-commit.
SESAMO – F.Stefan GT em SBDs DMMs - 68 -
subordinados (apenas se a decisão tiver sido pela efetivação). Em seguida, o nó-coordenador
envia uma mensagem a todos os nós-subordinados, informando sobre a decisão tomada.
Ao receber a decisão do coordenador, cada subordinado executa os seguintes
procedimentos:
Registrar, no histórico local de operações, a informação sobre a decisão final do nó-
coordenador;
Enviar ao nó-coordenador uma mensagem de reconhecimento
87
de que recebeu a
informação sobre a decisão final; e
Caso a ST local não tenha sido abortada, então executar a ação de término
correspondente à decisão global, ou seja, efetivar ou abortar a ST. Caso o BBF seja
o mecanismo local de controle de concorrência, então ocorrerá, nesse momento, a
liberação dos itens de dados que haviam sido bloqueados por T
i
.
O nó-coordenador, após receber a mensagem de reconhecimento de todos os nós-
subordinados, registra, em seu histórico local de operações, a informação de término da
transação distribuída, encerrando assim o processamento do EBF.
3.3.2 Topologias de comunicação no EBF
No protocolo EBF padrão, a comunicação entre os nós participantes das transações
distribuídas ocorre sempre entre o coordenador e os nós-subordinados. Os nós-subordinados
não se comunicam entre si. Essa topologia de comunicação caracteriza o EBF Centralizado.
No intuito de reduzir a quantidade de mensagens trocadas entre os nós e/ou o tempo gasto no
processamento do protocolo EBF Centralizado, duas topologias alternativas foram propostas:
o EBF Distribuído e o EBF Linear. Nessas duas topologias, o EBF dispõe de um protocolo
adicional denominado Protocolo de Término, que será visto na Subseção 3.3.3.
No tipo Linear, os nós-participantes comunicam-se em linha, sendo que o primeiro nó
(o coordenador) se comunica apenas com o segundo nó e este tem comunicação com o
primeiro e o terceiro nós. O último nó, ou seja, o mais à direita, comunica-se apenas com o
penúltimo. O protocolo é iniciado pelo coordenador, que envia seu voto, que é uma decisão
parcial, para o segundo nó. Este repassa para o terceiro nó a decisão parcial de efetivação caso
87
NT: Acowledgement.
SESAMO – F.Stefan GT em SBDs DMMs - 69 -
o seu voto e a decisão parcial recebida do nó anterior forem de efetivação. Caso contrário, ele
repassará a decisão parcial de aborto. O terceiro e os subseqüentes nós agirão da mesma
forma que o segundo nó, até que a decisão parcial chegue ao último nó. Esse nó, usando a
mesma metodologia que os anteriores, chegará à decisão final da transação, a qual será
repassada para os nós anteriores, até chegar ao nó-coordenador, seguindo o caminho inverso
que a fase de votação percorreu. O tipo linear tem a vantagem de reduzir a quantidade de
mensagens necessárias para se chegar ao término do protocolo. Por outro lado, esse tipo
apresenta baixo índice de processamento paralelo e, conseqüentemente, menor desempenho
computacional global.
No tipo Distribuído, cada nó tem comunicação com todos os outros, dispensando a
segunda fase do EBF centralizado, ou seja, a espera, por parte de cada nó-subordinado, sobre
a decisão global do coordenador. Nesse tipo, o coordenador envia o seu voto, juntamente com
a solicitação de voto. Cada participante, ao receber o voto do coordenador, toma a sua decisão
e a envia a todos os outros nós. A vantagem desse tipo é a possibilidade de redução do tempo
necessário para que cada nó participante tome conhecimento sobre a decisão global da
transação distribuída. Por outro lado, o volume de mensagens na rede pode aumentar muito, o
que poderá reduzir o desempenho global do SBD distribuído.
3.3.3 Problemas do EBF
Em cada uma das fases do EBF, o nó-coordenador e os nós-subordinados entram em
certos estados de espera por mensagens. Diversos fatores poderiam estender demasiadamente,
ou mesmo indefinidamente, o tempo de espera, tais como falhas na rede de comunicação ou
falhas nos nós da rede. O EBF faz uso de mecanismos de temporização como forma de
garantir que os nós possam sair do estado de espera. Se o tempo estipulado for atingido sem
que a mensagem esperada tenha chegado, situação que pode ser designada como
esgotamento-do-tempo-limite
88
, então ações específicas serão tomadas, de acordo com o tipo
do nó e a fase do EBF na qual ele se encontra.
Se o nó for o coordenador, então este presumirá que algum dos subordinados abortou a
transação, o que o levará a decidir pelo aborto global da transação. Se o nó for do tipo
subordinado e ele ainda não tiver enviado o seu voto para o coordenador, então esse nó
abortará a ST local. A variação do EBF que usa esse processo é o chamado EBF com aborto
SESAMO – F.Stefan GT em SBDs DMMs - 70 -
presumido, que é um dos protocolos padrões de mercado e faz parte dos padrões de
processamento de transações distribuídas ISO-OSI e X/OPEN [33]. Tal protocolo baseia-se na
seguinte regra: em caso de dúvida, deve-se assumir que a transação foi abortada. Tal variação
objetiva reduzir a carga do gerenciamento de transações, em relação às transações abortadas.
Há uma variação desse protocolo que se baseia na seguinte regra: em caso de dúvida, deve-se
assumir que a transação foi efetivada. O nome desse protocolo é EBF com efetivação
presumida, o qual objetiva reduzir a carga do gerenciamento de transações, em relação às
transações efetivadas.
Se o nó for do tipo subordinado e ele já tiver enviado o voto de efetivação ao nó-
coordenador, então esse nó-subordinado terá entrado em um estado especial de espera por
mensagens, conhecido por período de incerteza. Esse período é assim denominado devido ao
desconhecimento, por parte do nó-subordinado, sobre a decisão final que o nó-coordenador
tomou quanto ao término da transação distribuída. Nesse caso, o nó-subordinado não poderá
abortar a ST, pois a decisão estará a cargo do coordenador. Será necessário executar o
chamado Protocolo de Término, pelo qual o nó-subordinado tentará saber a que decisão final
o coordenador chegou enviando consultas a outros nós-subordinados. Apenas o EBF
Distribuído e o EBF Linear usam esse protocolo.
Caso as falhas no nó-coordenador sejam duradouras (no caso do EBF centralizado) ou
caso ocorram falhas duradouras que impossibilitem o processamento do protocolo de término,
então certos recursos dos nós que ainda estiverem no período de incerteza poderão ficar
bloqueados indefinidamente até que o nó-coordenador se recupere (no caso do EBF
centralizado) ou até que o protocolo de término seja concluído. Esse problema é conhecido
por bloqueio-de-nós-subordinados e representa uma importante desvantagem do EBF, o que
motivou a concepção de protocolos de efetivação atômica que suprimissem tal problema. Um
desses protocolos é o chamado Efetivação Trifásica, o qual será visto na Subseção 3.3.4.
3.3.4 Efetivação Trifásica
A Efetivação Trifásica
89
(ETF) [1,4,33,57,62] é uma extensão do protocolo EBF que
visa suprimir o problema caracterizado pelo bloqueio dos nós-subordinados (Subseção 3.3.3).
A diretriz básica desse protocolo é que nenhum nó-subordinado poderá executar a sua
88
NT: time-out.
89
NT: Three-Phase Commit (3PC).
SESAMO – F.Stefan GT em SBDs DMMs - 71 -
efetivação local antes de certificar-se de que nenhum outro nó-participante esteja em período
de incerteza.
A primeira fase do protocolo ETF é idêntica ao que ocorre no EBF. A segunda fase é
iniciada após o coordenador ter recebido o voto de todos os subordinados. A partir desse
ponto, o protocolo poderá seguir um de dois caminhos alternativos, a depender da decisão
global do coordenador. Se a decisão global for de abortar, então os procedimentos seguem da
mesma forma que no EBF. Se a decisão for de efetivar a transação, então o coordenador
enviará aos subordinados uma mensagem de pré-efetivação da transação
90
. Em seguida, cada
nó-subordinado, ao receber a mensagem de pré-efetivação, envia ao coordenador uma
mensagem de notificação, informando que já recebeu a informação sobre a decisão global,
saindo assim de seu período de incerteza. Essa fase é encerrada no momento em que o
coordenador recebe as mensagens de notificação advindas de todos os nós-subordinados.
Inicia-se então a terceira fase do protocolo ETF. Nessa fase, o nó-coordenador envia a
mensagem de efetivação global aos subordinados e estes a recebem, executam a efetivação
local e encerram o processamento da transação.
No protocolo ETF, não ocorre o problema de bloqueio nos nós-subordinados, pois, caso
o coordenador falhe, então será iniciado o protocolo de término, no qual os participantes
elegerão um novo coordenador. Este último, pela consulta aos outros nós, terá sempre
condições de obter a decisão tomada pelo coordenador anterior, antes de sua falha. O ETF, no
entanto, não é usado na prática, pois apresenta as seguintes desvantagens:
Impõe ao SGBD uma maior complexidade e sobrecarga de processamento.
Sua implementação depende da observância de premissas pouco realistas, quais
sejam: que não ocorra fragmentação da rede (vide nota de rodapé Erro! Indicador
não definido.); e que não ocorram falhas em mais que uma quantidade fixa e pré-
determinada de nós-participantes.
3.4. Conceitos gerais em SBDs múltiplos
Nesta seção, são apresentados conceitos sobre modelos de arquitetura, transações
globais, esquemas de dados e a taxonomia de SBDs múltiplos (SBDMs).
90
NT: pre-commit.
SESAMO – F.Stefan GT em SBDs DMMs - 72 -
3.4.1 Visão geral
Em um SBD distribuído convencional, também chamado de SBD distribuído
homogêneo, os SBDCs são homogêneos em termos de: plataforma operacional, rede de
comunicação, modelo de dados, linguagem de manipulação de BD e protocolos de
gerenciamento de transações. Além disso, os SBDCs são geralmente concebidos desde o seu
projeto para operarem de forma integrada, compartilhando, por exemplo, todos os dados.
Em termos genéricos, um SBD múltiplo
91
[46], ao qual nos referiremos daqui por diante
pelo acrônimo SBDM, é um sistema que fornece, de forma transparente aos seus usuários,
uma visão integrada e um acesso distribuído a múltiplos SBDs (distribuídos ou não)
autônomos (em termos de controle sobre seus respectivos SGBDs e BDs) e, possivelmente,
heterogêneos entre si. Um SBDM também é chamado de SBD heterogêneo [57,61]. Outra
designação conhecida para SBDM é SBD federado fracamente acoplado (vide Subseção
3.4.4).
Em um SBDM, cada SBDC deve funcionar de forma autônoma e cooperar na execução
de tarefas globais, controlando o compartilhamento total ou parcial de seus dados. Em cada
SBDC de um SBDM, deve haver razoável grau de independência nos seguintes aspectos: GD
(gerenciador de dados); sistema de comunicação utilizado; e protocolos de concorrência,
efetivação e recuperação, os quais podem ser distintos em cada SBDC. Em um SBDM, os
usuários devem poder acessar os dados de uma forma transparente, não tendo que lidar com a
complexidade associada à localização, representação e distribuição dos dados presentes nos
SBDCs.
O SGBD de um SBDM, o qual designaremos pelo acrônimo SGBDM, pode se
comunicar com os SGBDs componentes por uma das seguintes formas: Solicitação de
Serviços
92
[12]; interfaces que os SGBDs componentes podem dispor para receber operações
individuais advindas do GT do SGBDM, o qual designaremos, daqui por diante, pelo
acrônimo GTG (Gerenciador de Transações Globais).
91
NT: multi-dbs, distributed multi-dbs ou multi-ddbs. O conceito de SBD múltiplo tem interpretações variadas,
de acordo com os autores pesquisados. Nesta dissertação, foi adotada uma interpretação que está de acordo com
[57,61], devido à sua maior generalidade.
92
NT: service request.
SESAMO – F.Stefan GT em SBDs DMMs - 73 -
Figura 2 - Arquitetura de um SBD múltiplo
3.4.2 Transações globais
A arquitetura básica de um SBDM está representada na Figura 2. Nessa figura, vê-se
que as aplicações de usuário se comunicam com o SGBDM, o qual cria transações,
designadas doravante como transações globais (TG) ou transações multi-BD. Cada TG dá
origem ao número de STs correspondente à quantidade de SGBDs componentes acessados
por ela. Cada ST (subtransação) é enviada a um SGBD-componente distinto, onde será
processada. Dessa forma, uma TG deverá ter no máximo uma ST sendo executada em cada
SGBD-componente. Cada SGBD-componente processa a ST e envia os resultados de volta ao
SGBDM. O SGBDM não deve ter qualquer controle sobre o gerenciamento das STs em cada
SGBD-componente. Cada SGBD-componente pode ser um SGBD centralizado, um SGBD
distribuído ou um outro SGBDM.
3.4.3 Esquemas de dados em um SBD múltiplo
Na perspectiva de organização dos dados, um SBDM pode apresentar três tipos de
esquema de dados
93
[53]: esquema interno, o qual contém o catálogo de dados de um SBDC e
é acessado apenas pelo SGBD correspondente; esquema conceitual, pelo qual as operações
93
NT: schema.
SESAMO – F.Stefan GT em SBDs DMMs - 74 -
externas sobre os dados dos SBDCs são mapeadas para o formato de seus respectivos
esquemas internos; e esquema externo, pelo qual as operações externas sobre os dados dos
SBDCs são mapeadas para o formato dos seus respectivos esquemas conceituais. Geralmente,
tem-se um único esquema interno e um único esquema conceitual para cada BD, enquanto
pode-se ter vários esquemas externos para um mesmo BD. Além disso, o esquema conceitual
representa a totalidade da estrutura dos dados do BD, enquanto que o esquema externo pode
representar apenas um subconjunto daquela estrutura. Na perspectiva de distribuição dos
dados, um esquema de dados pode ser local ou global. Um esquema local refere-se a apenas
um único BD. Um esquema global refere-se a múltiplos BDs.
Considerando as duas perspectivas apresentadas, pode haver as seguintes variações de
esquemas de dados: EIL (esquema interno local), ECL (esquema conceitual local), EEL
(esquema externo local), ECG (esquema conceitual global) e EEG (esquema externo global).
Um ECG é formado a partir da integração dos ECLs dos SBDCs. Em algumas arquiteturas de
SBDM, a construção do ECG não é feita diretamente a partir da integração dos ECLs, mas
sim pela integração dos EELs, os quais representam, cada um deles, um subconjunto do EIL
de um SBDC. Essa alternativa é usada para o caso de não ser necessário ou desejável o
compartilhamento total do EIL de cada SBDC.
3.4.4 Taxonomia de SBDs múltiplos
Segundo a classificação adotada em [61], os SBDMs podem ser agrupados em dois
tipos: os SBDs não-federados e os SBDs federados. Os SBDs não-federados não serão
abordados com maiores detalhes, por estarem fora do foco desta dissertação. Um exemplo de
sua implementação é o UNIBASE [15]. Os SBDs federados são aqueles que têm acesso
simultâneo a múltiplos SGBDs, executando operações nestes por meio de TGs. Os SBDs
federados podem ser subdivididos em duas categorias, conforme o grau de acoplamento
existente entre os esquemas de dados dos SBDCs. As categorias são: os SBDs federados
fracamente acoplados e os SBDs federados fortemente acoplados. Os SBDs federados
fracamente acoplados são também conhecidos simplesmente pela designação mais genérica,
ou seja, os SBDMs [48], conotação que será usada nesta dissertação daqui por diante. Os
SBDs federados fortemente acoplados são também conhecidos simplesmente por SBDs
federados, designação esta que será usada no restante desta dissertação. Maiores detalhes
SESAMO – F.Stefan GT em SBDs DMMs - 75 -
sobre os SBDs federados e SBDMs estão descritos nas Subseções 3.4.5 e 3.4.6,
respectivamente.
Há uma outra taxonomia [53] que classifica as formas de integração de SBDs
autônomos (os quais designaremos como SBDCs de uma arquitetura de integração, ou,
simplesmente, SBDCs), de acordo com a variação de três dimensões. A primeira dimensão
representa a autonomia (controle) que cada SBDC tem em relação às suas funcionalidades. A
segunda dimensão representa a heterogeneidade entre os SBDCs quanto aos seus esquemas
locais de dados, à linguagem de manipulação de dados, e aos protocolos de gerenciamento de
transações. A terceira dimensão representa o grau de distribuição dos dados dos SBDCs. A
Figura 3 (obtida de [53]) representa as diversas arquiteturas de integração de SBDCs. A
seguir, estão indicadas algumas dessas arquiteturas, as quais correspondem a determinados
pontos ou planos da citada figura.
O ponto N corresponde aos SBDs centralizados tradicionais (vide Seção 2.1);
Os pontos A e G correspondem aos SBDs distribuídos tradicionais, ou seja, os
SBDs distribuídos homogêneos (Subseção 3.1.1);
Os sistemas situados no plano definido pelos pontos B, E, R e O correspondem aos
SBDs Federados (Subseção 3.4.5);
Os sistemas situados no plano definido pelos pontos C, D, Q e P correspondem aos
SBDMs (Subseção 3.4.6);
Os sistemas situados no plano definido pelos pontos A, C, D e F correspondem aos
Sistemas Colaborativos (Subseção 3.1.3);
Os sistemas situados no plano definido pelos pontos G, I, J e M correspondem aos
SBDs Cliente-Servidor (Subseção 3.1.3).
O ponto J corresponde ao SBD múltiplo heterogêneo cuja arquitetura de
distribuição é do tipo cliente-servidor. Nesse tipo de SBD, as funções de
interoperabilidade ficam ao encargo de sistemas mediadores, resultando em uma
arquitetura de três camadas. Exemplo: a World Wide Web da Internet.
SESAMO – F.Stefan GT em SBDs DMMs - 76 -
Figura 3 - Arquiteturas de integração de SBDs.
3.4.5 SBDs federados
Os SBDs federados são sistemas que usam o ECG (vide classificação de esquemas na
Subseção 3.4.3). O acesso aos dados ocorre da seguinte forma. Os usuários e/ou programas
acessam os EEGs, pelos quais as operações são mapeadas para o ECG. Por meio do ECG, as
operações sobre os dados são mapeadas para os ECLs (ou EELs) de cada SBDC, o qual
executa as operações sobre os dados, mapeando-as para os respectivos EILs.
De acordo com o esquema de integração dos ECLs, os SBDs federados podem ser
subdivididos em duas categorias, ou seja, os SBDs federados simples
94
, os quais integram os
ECLs por meio de um único ECG; e os SBDs federados múltiplos
95
, os quais integram os
ECLs por meio de vários esquemas de integração. Algumas implementações do tipo simples
são o DDTS [24] e o SIRIUS-DELTA [48]. Uma das implementações do tipo múltiplo é o
Mermaid [64].
De acordo com a linguagem de integração, um SBD federado pode ser classificado
como unilingual ou multilingual [53]. Uma implementação do SBD federado unilingual é o
94
Também conhecidos por Federações simples.
95
Também conhecidos por Federações múltiplas.
SESAMO – F.Stefan GT em SBDs DMMs - 77 -
MULTIBASE [43]. Algumas implementações do SBD federado multilingual são o SIRIUS-
DELTA [48] e o HD-DBMS [16].
Outro exemplo de implementação de SBD federado é o AURORA [69].
3.4.6 SBDMs
Os SBDs múltiplos (SBDMs) são sistemas que integram os recursos de SBDs
autônomos componentes sem a utilização de um ECG (vide classificação de esquemas na
Subseção 3.4.3). Em vez disso, a integração é realizada pelo uso de uma linguagem para
manipulação integrada dos dados presentes nos SBDCs. Essa linguagem pode ser chamada de
Linguagem para Bancos de Dados Múltiplos (LBDM).
O acesso aos dados ocorre da seguinte forma. Os usuários e/ou programas acessam os
EELs, por meio da LBDM, a qual faz um mapeamento desses esquemas para os ECLs de cada
SBDC, o qual executa as operações sobre os dados, mapeando-as para os respectivos EILs.
Alguns exemplos de SBDMs são o MRDSM [47], o CALIDA [38], o OMNIBASE
[59], o ADDS [14] e o INTERBASE [26].
3.5. Controle de concorrência em SBDMs
Nesta seção, serão discutidos os requisitos e problemas associados ao controle de
concorrência em SBDMs.
3.5.1 Requisitos
Os protocolos convencionais de controle de concorrência para SBDs distribuídos
(Subseção 3.2.1) utilizam o critério da Serialidade como garantia de preservação das
propriedades de isolamento e consistência das transações executadas. O requisito básico para
garantir a serialidade é o controle sobre a seqüência em que todas as operações são
executadas, o que requer a troca de informação entre o Gerenciador de Transações Globais
(GTG) e os GTs dos SBDCs. Como conseqüência desse requisito, a implementação dos
referidos protocolos de controle de concorrência em um SBDM requer que as seguintes
condições sejam satisfeitas:
SESAMO – F.Stefan GT em SBDs DMMs - 78 -
O GTG deverá: coordenar a execução distribuída de TGs; gerenciar os bloqueios
cíclicos globais que possam ocorrer entre TGs; garantir a serialidade do histórico de
execução de TGs concorrentes; e conhecer a ordem de seriação das STs nos
históricos locais dos SBDCs;
O GT de cada SBDC deverá: garantir a serialidade do histórico de execução local; e
manter a ordem relativa de execução das STs, determinada pelo GTG. Essa última
condição impõe que as TGs do histórico global deverão ter a mesma seqüência
relativa de seriação em todos os históricos locais dos SBDs participantes das
transações, o que garantirá que o histórico produzido pelo GTG seja globalmente
seriável.
3.5.2 Problemas
Nos SBDs distribuídos convencionais (homogêneos), o GTG pode comunicar-se
diretamente com os CCs de todos os SGBDs componentes que participam das TGs. Já nos
SBDMs, a referida comunicação não é sempre possível [53], devido à inexistência, em alguns
dos SGBDs-componentes, de recursos de comunicação em ambientes distribuídos, de forma
que um certo SGBD-componente somente tem recursos para se comunicar com um aplicativo
que estiver sendo processado no sistema computacional local. Além disso, a autonomia
requerida por cada SGBD-componente dificulta ou mesmo inviabiliza a tarefa de fazer um
controle global sobre todas as operações executadas nos SGBDs-componentes, o que pode
resultar em conflitos indiretos entre TGs e transações locais, conceito a seguir definido,
extraído de [46].
Definição 11. Conflito indireto.
Existe um conflito indireto entre duas transações T
i
e T
j
se e somente se há uma
seqüência de transações T
1
, T
2
, ... T
n
, de forma que T
i
esteja em conflito direto
96
com T
1
, T
1
esteja em conflito direto com T
2
, e assim por diante, resultando no fato de que T
n
esteja em
conflito direto com T
j
.
Considerando os problemas citados e o fato de as soluções existentes para os SBDs
distribuídos homogêneos presumirem que os SGBDs-componentes empreguem o mesmo
mecanismo de controle de concorrência, conclui-se que tais soluções não são adequadas para
96
Conflito direto é sinônimo de conflito, conceito descrito na Definição 4 na página 31.
SESAMO – F.Stefan GT em SBDs DMMs - 79 -
SBDMs [12], o que requer o desenvolvimento de novas soluções. Algumas propostas podem
ser encontradas em [30,56].
3.6. Conceitos gerais em SBDs móveis
Nesta seção, são apresentados conceitos sobre sistemas de computação móvel e sobre
SBDs móveis.
3.6.1 Sistema de computação móvel
Na Figura 4, está representado um modelo abstrato de arquitetura de um sistema de
computação móvel (SCM). Um SCM pode ser considerado como um tipo dinâmico de
sistema de computação distribuída (vide Subseção 3.1.1), em que as conexões entre os nós da
rede de computadores mudam dinamicamente [23]. Um outro conceito para SCM é um
sistema em que alguns de seus componentes computacionais podem mudar dinamicamente de
localização física [58]. As duas configurações físicas mais conhecidas para um SCM são:
Rede de Computação Móvel de estrutura Estática (RCME)
97
e Rede de Computação Móvel de
estrutura Dinâmica (RCMD)
98
.
SGBD
SGBD
Estação de
suporte à
mobilidade
Célula
BD
BD
BD
SGBD
Computador móvel
Estação de
suporte à
mobilidade
Estação de
suporte à
mobilidade
Computador fixo
SGBD
SGBD
Estação de
suporte à
mobilidade
Célula
BD
BD
BD
SGBD
Computador móvel
Estação de
suporte à
mobilidade
Estação de
suporte à
mobilidade
Computador fixo
Figura 4 – Arquitetura de um Sistema de Computação Móvel
97
NT: Nomadic computing network. A tradução correta para o termo nomadic seria nômade. Optamos pela
designação “de estrutura estática” para efeito de contraste com a rede ad-hoc, que tem estrutura dinâmica.
98
NT: Mobile ad-hoc network (MANET). O termo ad-hoc pode ter vários significados, tais como “para este
propósito”, “específica”, “improvisada”. Optamos pela designação “rede de estrutura dinâmica” com o fim de
contrastar com as redes que têm estrutura estática.
SESAMO – F.Stefan GT em SBDs DMMs - 80 -
Uma RCME consiste basicamente de uma estrutura fixa de rede e um conjunto de
Computadores Móveis (CMs)
99
que se ligam à rede fixa por intermédio de uma Estação de
Suporte à Mobilidade (ESM)
100
. A ESM consiste em um dispositivo da rede fixa que tem
capacidade para comunicação sem fio. Cada ESM cobre uma área geográfica denominada
Célula
101
, dentro da qual os CMs poderão se conectar com a ESM, podendo então ter acesso a
outros CMs ou nós da rede fixa. Devido ao aspecto funcional de mobilidade, os CMs
freqüentemente fazem migrações
102
de uma célula para outra.
Uma RCMD consiste exclusivamente de CMs que se conectam entre si quando as
condições físicas (tal como a distância entre os CMs) permitem. A estrutura da RCMD é
formada de maneira oportunista e muda rapidamente em resposta ao movimento dos CMs.
Uma RCMD é dinamicamente configurável e seus nós (os CMs) podem fornecer serviços a
outros computadores, tais como acesso a banco de dados [58].
Os CMs podem ter recursos computacionais limitados, em relação a computadores
fixos, e geralmente se comunicam com outros dispositivos computacionais através de uma
Rede de comunicação Sem Fio (RSF)
103
[58], a qual ocorre, basicamente, via ondas de rádio
ou via raios infra-vermelhos. As RSFs geralmente apresentam instabilidade e/ou lentidão em
seu funcionamento. Ocasionalmente, os CMs podem involuntariamente perder a conexão com
a RSF, em conseqüência de falhas em seus componentes internos ou de falhas na RSF. Os
CMs podem também perder a conexão com a RSF, de forma voluntária, como conseqüência
da intenção de seus usuários em economizar carga de bateria do CM ou custos de utilização
da RSF.
3.6.2 SBD móvel
Um SBD móvel pode ser considerado como um tipo mais genérico de SBD distribuído,
pois pode ter todas as características deste último, acrescentando-se as características
inerentes a um ambiente com suporte à computação móvel. De forma análoga, um SBDM
móvel (ou SBDM com suporte à mobilidade) é a generalização de um SBDM, ou seja, é um
99
NT: Mobile Hosts, Mobile Units, ou Mobile Computers.
100
NT: Mobile Support Station ou Base Station.
101
NT: cell.
102
NT: hand-offs.
103
NT: wireless network.
SESAMO – F.Stefan GT em SBDs DMMs - 81 -
SBDM que pode funcionar também em um ambiente de computação móvel [21,35,36,46].
Deste ponto em diante, salvo observação em contrário, será usado o termo SBD móvel para
designar o caso mais genérico possível, ou seja, englobando o tipo SBD distribuído múltiplo
móvel (SBDM móvel, i.e., SBDM com suporte à mobilidade).
Um dos modelos de referência para SBDs móveis compõe-se de três camadas de
processamento, quais sejam: sistemas, agentes de acesso aos dados e transações móveis [23].
Os sistemas oferecem, ao ambiente de mobilidade, serviços de informação que ficam
registrados na rede. Os dados presentes nos sistemas são acessados por intermédio dos
agentes
104
de acesso aos dados, que ficam localizados nas ESMs. As transações móveis são as
transações criadas pelo SBD móvel.
Quando um CM requisita a execução de uma transação, o agente de acesso aos dados,
situado na ESM à qual o CM está conectado, encaminha a solicitação para o sistema
específico que estiver oferecendo o serviço requerido. O agente de acesso aos dados executa
as funções de controle de concorrência e efetivação atômica das transações que forem
executadas na respectiva ESM, bem como o gerenciamento da recuperação do SBD móvel.
3.7. Requisitos do Gerenciamento de Transações em SBDs móveis
Conforme discutido anteriormente, o SBD móvel é um caso genérico de um SBDM.
Dessa forma, o gerenciamento de TGs em um SBD móvel deve atender os requisitos de
autonomia local de cada SBDC e a serialidade global dos históricos produzidos pelo GTG.
Adicionalmente, devem ser observados os requisitos específicos do ambiente de computação
móvel.
Conforme visto na Subseção 3.6.2, o ambiente de computação de um SBD móvel
apresenta as seguintes características: freqüente desconexão dos CMs com a rede de
computadores; mobilidade dos CMs entre células distintas; baixa taxa de transmissão de
dados e/ou instabilidade da rede de comunicação sem fio; e limitações tecnológicas dos CMs.
Tais limitações impõem a necessidade de pesquisa e desenvolvimento, dentre outros aspectos
104
Agente [20,44,46] é um programa de computador que age de forma contínua e autônoma, reagindo às
mudanças no ambiente de execução. O agente do tipo móvel é capaz de transportar e executar operações (no
lugar de dados) em sistemas computacionais remotos, entregando, de forma confiável, os resultados das
operações ao sistema computacional que o criou.
SESAMO – F.Stefan GT em SBDs DMMs - 82 -
da área de estudo Computação, de soluções apropriadas para o gerenciamento de transações
em SBDs móveis.
Em [68], os autores afirmam que o gerenciamento de transações em um SBD móvel
deve incluir as seguintes funcionalidades, visando, dentre outros objetivos, prosseguir com
suas atividades durante os momentos de desconexão, instabilidade ou baixa velocidade na
rede de comunicação:
Usar técnicas eficientes de armazenamento de dados;
Usar técnicas de replicação e consistência dos dados nos CMs;
Prover, aos CMs, mecanismos locais de Gerenciamento de Transações;
Fornecer uma interface de comunicação dos CMs com os servidores de banco de
dados estacionários;
Usar um método de reconciliação das transações processadas nos momentos de
desconexão com os SBDs que controlam as fontes originais dos dados; e
Dispor de sistemas de registro de ocorrências, registro de pontos de verificação de
consistência, e recuperação dos BDs, de forma a reduzir os efeitos causados pelas
falhas no gerenciamento das transações.
Em [46], os autores ressaltam que um mecanismo de controle de concorrência em um
SBD móvel deve ter as seguintes funcionalidades:
Otimizar a vazão de processamento
105
, considerando as limitações impostas pela
tecnologia dos componentes de um ambiente computacional móvel;
Reduzir a sobrecarga global de comunicação no SBD móvel; e
Preservar ao máximo a autonomia dos SBDCs.
Em [21], os autores afirmam que o GTG de um SBDM móvel pode delegar a
responsabilidade de garantia das propriedades de Consistência e Durabilidade das TGs aos
SBDCs. O GTG precisará assegurar apenas as propriedades de Atomicidade e Isolamento das
TGs, além de fazer o tratamento dos problemas relacionados à migração e desconexão dos
sistemas computacionais envolvidos no processamento das TGs.
105
Vide nota de rodapé 58.
SESAMO – F.Stefan GT em SBDs DMMs - 83 -
Algumas pesquisas e propostas sobre aspectos de controle de concorrência, efetivação
atômica e recuperação, no contexto do gerenciamento de transações em SBDs móveis, podem
ser encontradas em [8,21,23,36,40,42,46,55,68]. Em [66], é apresentado um levantamento
bibliográfico de várias propostas de suporte ao gerenciamento de transações para o ambiente
de computação móvel.
Há outros aspectos que também influenciam no gerenciamento de transações em SBDs
móveis, tais como a arquitetura de acesso e integração de BDs no ambiente de mobilidade,
replicação de dados e disponibilidade de dados em momentos de desconexão. Esses aspectos
foram estudados em [9,22,35,44,45,55].
3.8. Resumo do capítulo
Neste capítulo, foram descritos conceitos gerais acerca do gerenciamento de transações
em SBDs distribuídos, com ênfase nos protocolos padrões de controle de concorrência de
transações distribuídas (i.e., o BBF-distribuído) e de efetivação atômica de transações
distribuídas (i.e., o EBF). Ademais, foram apresentados conceitos sobre modelos de
arquitetura, TGs, esquemas de dados e a taxonomia de SBDs múltiplos (SBDMs).
Neste capítulo, também foram discutidos os requisitos e problemas associados ao
controle de concorrência em SBDMs. A partir da referida discussão, foram obtidas as
seguintes conclusões: (i) Um SBDM deve preservar a autonomia dos SGBDs-componentes,
bem como a garantia de consistência dos BDs dos SBDCs; (ii) O uso da Serialidade como
critério de controle de concorrência em SBDMs garante a consistência dos BDs por meio da
formação de um histórico global seriável, mas viola a autonomia dos SGBDs-componentes; e
(iii) Um SBDM com suporte à mobilidade é uma generalização de um SBDM, devendo,
portanto, preservar a autonomia e a garantia de consistência dos dados dos SBDCs. Além
disso, em um SBDM com suporte à mobilidade, é desejável que exista, dentre outras
características, o gerenciamento local de TGs e uma vazão otimizada de TGs.
Como será visto no Capítulo 4, o protocolo de controle de concorrência proposto nesta
dissertação objetiva justamente atingir as características descritas no último item do parágrafo
anterior (item iii), configurando-se numa vantajosa proposta em relação a outras propostas
correlatas, conforme pode ser visto no Capítulo 5.
- 84 -
CAPÍTULO IV
SESAMO – Fundamentos
- 85 -
4. SESAMO – Fundamentos
Neste capítulo, são apresentados os fundamentos teóricos da proposta desta dissertação,
ou seja, o CC SESAMO. Inicialmente, é introduzido o problema que motivou a concepção do
SESAMO. Em seguida, descrevem-se o modelo de transação e as premissas nas quais o
SESAMO está baseado. A seguir, são apresentados os modelos de estrutura e operação do
SESAMO. Adiante, são feitas demonstrações de que o SESAMO garante a consistência dos
dados e contribui para o ganho de desempenho de um SBDM gerenciado por ele. Em seguida,
são descritos os requisitos necessários para se elaborar uma transação que utilize o SESAMO,
bem como um estudo de caso, apresentando-se os resultados obtidos.
4.1. Introdução
A Serialidade é o critério tradicional de correção dos CC de SBDs centralizados e
distribuídos. A adoção da Serialidade para controle de concorrência de TGs em um SBDM,
ou seja, a Serialidade global, requer a formação de um único histórico global seriável. A
formação de um histórico global seriável implica que as STs de quaisquer duas TGs T
1
e T
2
deverão apresentar a mesma ordem relativa de execução em todos os históricos seriais
equivalentes aos históricos produzidos em cada SBDC onde alguma operação de T
1
conflitou
com alguma operação de T
2
[12,21,30,46]. Os CC que adotam a serialidade global garantem a
execução correta de TGs, mas apresentam os seguintes problemas:
Alguma forma de violação da autonomia dos SBDCs do SBDM, devido à
necessidade de sincronizar a ordem de seriação
106
das STs com a ordem de seriação
das respectivas TGs, evitando assim possíveis inconsistências nos dados que seriam
causadas pela violação global das propriedades ACID das TGs; e
Se a autonomia dos SBDCs não puder ser violada, então a obtenção da ordem de
seriação das STs, nos referidos SBDs, se torna complexa, comprometendo a
garantia de consistência dos BDs dos SBDCs.
106
Neste contexto, o uso da expressão “ordem de seriação” de um grupo de transações (ou subtransações) não
indica que as transações (ou subtransações) foram executadas serialmente. Na verdade, a expressão usada indica
que as transações foram executadas de forma equivalente por conflito a uma execução serial delas.
SESAMO – F.Stefan SESAMO: Fundamentos - 86 -
Nesta dissertação, propõe-se um CC, denominado SESAMO, o qual objetiva solucionar
os problemas supracitados. O SESAMO [7], acrônimo para Serialidade Semântica Aplicada à
Mobilidade, foi concebido para funcionar sobre uma infra-estrutura de acesso transparente a
um SBDM que integra uma comunidade de SBDs autônomos e oferece suporte à computação
móvel. Um modelo de referência para esse tipo de estrutura é a arquitetura AMDB (vide
Seção 5.5). O SESAMO torna-se uma solução adequada para SBDMs, em geral, e para
SBDMs com suporte à computação móvel, pois atende a alguns dos requisitos vistos na
Subseção 3.5.1 e Seção 3.7, quais sejam: (i) favorece um alto grau de concorrência e preserva
integralmente a autonomia dos SBDCs, características que resultam da implementação da
Serialidade Semântica (vide Seção 4.2), que é o modelo de transação adotado pelo SESAMO;
(ii) fornece mecanismos locais de gerenciamento de TGs em cada nó da rede; (iii) otimiza a
vazão de processamento; e (iv) possibilita a redução da carga de comunicação no SBDM.
4.2. Serialidade Semântica
O modelo de transação tradicional, isto é, a Serialidade (Subseção 2.4.2), impõe a
preservação das propriedades ACID para todas as transações executadas. Alguns modelos
alternativos foram desenvolvidos com a finalidade de superar os problemas impostos pela
Serialidade, no ambiente específico de SBDMs, principalmente pela flexibilização das
propriedades de Atomicidade e Isolamento das TGs [1,29,39]. Dentre eles, foi desenvolvido a
Serialidade Semântica
107
[10], o qual explora a semântica dos dados, objetivando preservar a
autonomia dos SBDCs existentes e garantir um alto grau de paralelismo na execução de TGs
concorrentes.
A Serialidade Semântica (deste ponto em diante referida apenas por SSM) permite a um
CC fragmentar uma TG, que representa uma unidade consistente de computação, em unidades
consistentes de computação menores e independentes entre si, denominadas módulos
semânticos (MSs), conceito formalizado na Definição 14. A redução da quantidade de
operações de cada unidade consistente de computação, ou seja, de TG para MS, possibilita
um maior grau de entrelaçamento das operações de TGs distintas, originalmente submetidas
ao CC, o que favorece ao aumento do grau de concorrência.
Há modelos de transação que visam aumentar o grau de paralelismo por meio da
exploração da semântica das transações e suas operações [1,29]. Nesses modelos, as regras
SESAMO – F.Stefan SESAMO: Fundamentos - 87 -
para entrelaçamento de operações são definidas em tempo de projeto da aplicação, o que torna
mais complexa a programação. Na SSM, a identificação dos pontos de entrelaçamento ocorre
automaticamente em tempo de execução, com base na semântica dos dados presentes nas
Unidades Semânticas (US) , conceito formalizado na Definição 13. As USs são definidas em
tempo de projeto. Informalmente, uma US pode ser descrita como um agrupamento lógico de
dados (normalmente, mas não obrigatoriamente, correspondente a um BD autônomo e não
fragmentado), sendo que a atualização de algum item desse conjunto não deve depender da
leitura de itens de dados associados a outras USs. A seguir, descrevem-se formalmente alguns
conceitos necessários.
Definição 12. Conjunto-dependência.
Diz-se que um item de dado y ∈ conjunto-dependência(x) quando o resultado de alguma
operação de uma transação T
i
que atualiza o item x é uma função do valor do item y, lido na
mesma transação T
i
, considerando que: x,y ∈ BDM; BDM é um BD múltiplo; e o conjunto-
dependência(x) representa o conjunto de todos os itens de dados z, tal que z ∈ conjunto-
dependência(x).
Definição 13. Unidade semântica (US).
Considerando que BDM é um BD múltiplo, então US
a
(0 < a
≤
n) é uma unidade
semântica de BDM se e somente se: BDM =
∪
n
a=1
US
a
;
∀
1
≤
i, j
≤
n, i
≠
j : US
i
∩
US
j
=
∅
; e
(
∀
x
∈
US
i
, y
∈
US
j
, i
≠
j) => ( x
∉
conjunto-dependência(y) )
Λ
(y
∉
conjunto-
dependência(x) ).
Definição 14. Módulo semântico (MS).
Considerando que T
i
é uma transação que acessa o BD múltiplo BDM =
∪
n
a=1
US
a
, em
que cada US
a
(0 < a
≤
n) é uma unidade semântica de BDM. Para cada OP
USa
(T
i
)
≠
∅
, com
OP
USa
(T
i
) representando o conjunto de operações de T
i
que são executadas em itens de US
a
,
define-se um módulo semântico de T
i
, simbolizado por MS
USa
(T
i
), como sendo a seqüência de
operações de T
i
executadas em itens de US
a
, satisfazendo a seguinte condição: ∀p,q ∈
OP
USa
(T
i
), tem-se que p<
MSUSa(Ti)
q ⇔ p <
Ti
q, ou seja, a operação p precede a operação q em
MS
USa
(T
i
) se e somente se p precede q em T
i
.
107
NT: semantic serializability.
SESAMO – F.Stefan SESAMO: Fundamentos - 88 -
Na SSM, a execução de uma transação é correta se o histórico de execução de
transações concorrentes for semanticamente serial ou equivalente
108
a ele, sendo chamado,
nesse último caso, de histórico semanticamente seriável. Um histórico semanticamente serial
representa uma execução serial de MSs, os quais representam, individualmente, o conjunto de
todas as operações, originadas de uma mesma transação, que leram ou gravaram dados
presentes em uma mesma US. A título de exemplo, caso uma TG tenha executado operações
em N USs, um histórico global de execução que seja semanticamente serial conterá a
execução de N MSs originados da referida transação.
A título de comparação, um CC do tipo Conservador que use o critério da SSM
oferecerá maior grau de concorrência do que um CC baseado no BBF-preciso, pois uma
mesma transação poderá obter bloqueios mesmo após já ter liberado alguns outros bloqueios,
desde que os bloqueios liberados se refiram a USs distintas daquela onde está armazenado o
novo item de dado a ser bloqueado.
A SSM foi concebida inicialmente para o ambiente de aplicações avançadas (por
exemplo, aplicações CAD/CAM e workflow) em BD [11]. Posteriormente, em [10], os autores
a adaptaram para o ambiente de SBDMs e, em [8], os autores demonstraram que a SSM
garante a consistência dos dados em ambientes de SBDMs que oferecem suporte à
mobilidade.
4.3. Premissas
O funcionamento do SESAMO pressupõe as seguintes condições:
Deve existir uma interface de acesso transparente a uma estrutura de SBDM que
tenha suporte à computação móvel e que forneça acesso aos EELs (vide
classificação de esquemas de dados na Subseção 3.4.3) de todos os BDs-
componentes. Um exemplo de estrutura desse tipo está apresentado em [9]. Além
disso, o SBDM considerado deve ser tolerante a falhas, garantindo assim a
atomicidade e durabilidade das TGs.
Cada SGBD-componente, ou seja, cada SGBD que gerencia um dos BDs-
componentes do SBDM considerado, deve garantir a serialidade das transações
108
Vide definição deste termo na Subseção 2.4.2.
SESAMO – F.Stefan SESAMO: Fundamentos - 89 -
locais (garantindo o isolamento) e ser tolerante a falhas (garantindo a atomicidade e
durabilidade).
O conjunto dos EELs dos BDs-componentes deve estar logicamente segmentado em
grupos, sendo que cada grupo corresponde a uma US (Definição 13). Essa
informação precisa estar disponível somente para os componentes de CC do
SESAMO. Os programas e os SGBDs-componentes não precisam ter acesso a essa
informação.
A efetivação antecipada de STs geradas por uma TG submetida ao SESAMO
ocorrerá mediante o uso da operação (opcional) de encerramento de operações sobre
um determinado BD. Tal operação será vista em maiores detalhes na Seção 4.5.
4.4. Modelo de estrutura
Na Figura 5, está representado o modelo abstrato da estrutura do SESAMO. Há três
componentes básicos, os quais estão situados em cada dispositivo computacional (DC) onde
reside um SBD autônomo que integra o SBDM ao qual o SESAMO tem acesso. Na Figura 5,
estão representados três DCs, quais sejam, A, B e C. Os componentes são os seguintes:
ISBDM, GTG e SBDC. A seguir, serão descritas as funcionalidades de cada componente.
4.4.1 ISBDM
Consiste na Interface de acesso à estrutura de SBDM com suporte à computação móvel.
Este componente deve executar as seguintes funcionalidades, para cada operação submetida
por uma TG originada no DC local, sendo este referido como DC-originador:
Receber a operação e inseri-la numa estrutura denominada FOAS (vide Subseção
4.4.2);
Coletar a operação a partir de uma estrutura denominada FOJS (vide conceito na
Subseção 4.4.2) e submetê-la ao componente SBDC (vide conceito na Subseção
4.4.3) onde está localizado o BD-alvo (vide conceito na Subseção 4.4.3) da
operação; e
Coletar do SBDC os resultados da execução da operação, repassando-os ao DC
originador e registrando o sucesso (ou insucesso) da operação na FOJS.
SESAMO – F.Stefan SESAMO: Fundamentos - 90 -
Figura 5 - SESAMO: modelo da estrutura
4.4.2 GTG
Consiste no gerenciador de TGs. O GTG executa as seguintes ações, para cada operação
submetida pelo ISBDM:
Coletar a operação a partir da estrutura FOAS (fila de operações a serem
sincronizadas pelo GTG) e identificar, a partir dos EELs de todos os BDs que fazem
parte do SBDM (vide premissas, na Seção 4.3), a US e o BD aos quais a operação
se refere, sendo estes denominamos, respectivamente, de US-alvo e BD-alvo. A
operação será associada a um MS (de acordo com a US-alvo) e a uma ST (de acordo
com o BD-alvo);
Obter um bloqueio de acesso ao item de dado referenciado pela operação. Tal
bloqueio é de uso exclusivo do GTG, i.e., os CCs dos SBDCs não têm acesso a essa
informação. Caso o bloqueio seja obtido, a operação é inserida na estrutura FOJS
(fila de operações já sincronizadas pelo GTG) e excluída da FOAS. Caso o bloqueio
não seja obtido, a operação é excluída da FOAS e inserida em uma estrutura
denominada FOSA (fila de operações com sincronização adiada). Periodicamente, o
GTG tentará executar esse processo de bloqueio para cada uma das operações que
SESAMO – F.Stefan SESAMO: Fundamentos - 91 -
estiverem na FOSA. Quando conseguir, a operação será excluída da FOSA e
inserida na FOJS; e
Adicionalmente, o GTG irá determinar o término das STs, MSs e das TGs, de
acordo com as informações presentes na FOJS.
4.4.3 SBDC
Corresponde ao SBD local que faz parte do SBDM ao qual o SESAMO tem acesso.
Para fins de simplificação, iremos considerar que, para cada GTG, o BD local de cada SBDC
corresponde a uma única US.
4.5. Modelo de operação
Nesta seção, está descrito, de forma simplificada, o modelo abstrato de operação do
SESAMO, consistindo em três passos. Na Figura 6, estão representadas as TGs T
1
e T
2
, as
quais foram originadas no DC (dispositivo computacional) A e são ambas formadas pelo
seguinte conjunto de operações: { w(a
i
), E(A),w(b
j
), C }. A operação w(a
i
), por exemplo,
indica uma operação de leitura sobre o item de dado a
i
, o qual está localizado no BD que
reside no DC A. A operação E(A) representa uma forma abreviada da operação “encerrarBD”
e indica que a transação em questão não mais irá submeter operações sobre o BD informado
como parâmetro, no caso o BD que reside no DC A. A operação C representa a efetivação da
transação. No passo 1 do modelo abstrato de operação do SESAMO (Figura 6), o componente
ISBDM recebe as operações das duas TGs e as submete ao GTG.
SESAMO – F.Stefan SESAMO: Fundamentos - 92 -
! "
#$"% & %#' &(
& &&) !
! "
#$"% & %#' &(
& &&) !
Figura 6 - SESAMO: modelo de operação (1)
! "
#$"&&(
%#$)*()+
& ,! )
&)!%&#$!
&%- &) !
%#$
.
.
! "
#$"&&(
%#$)*()+
& ,! )
&)!%&#$!
&%- &) !
%#$
.
.
Figura 7 - SESAMO: modelo de operação (2)
No segundo passo do modelo de operação (Figura 7), o GTG associa cada operação a
um MS (de acordo com a US-alvo) e ST (de acordo com o BD-alvo), sincroniza e submete a
operação ao ISBDM. No presente exemplo, a transação T
1
, por exemplo, gerou dois MSs,
SESAMO – F.Stefan SESAMO: Fundamentos - 93 -
M
1A
e M
1B
, sendo que cada um destes agrupa as operações destinadas a uma US-alvo. Cada
MS, por sua vez, gerou uma ST, sendo que cada uma delas agrupa as operações destinadas a
um BD-alvo.
No terceiro passo do modelo de operação (Figura 8), o ISBDM submete cada operação
ao SBDC, coleta os resultados e os informa ao GTG que originou a operação. É importante
ressaltar que as operações de cada ST gerada por um GTG são gerenciadas por um SBDC da
mesma forma que este gerencia as operações de suas transações locais. Por extensão, um
SBDC gerencia uma ST da mesma forma que o faz com uma transação local.
"
! "
#$"&) ! (
%#$+ !&
% &)+!(& &/%
%0(%( %#$
!#$
#
%
1%"
.
1%"
.
"
! "
#$"&) ! (
%#$+ !&
% &)+!(& &/%
%0(%( %#$
!#$
#
%
1%"
.
1%"
.
Figura 8 - SESAMO: modelo de operação (3)
4.6. Garantia de consistência dos dados e desempenho
Nesta seção, descreve-se de que forma o critério de controle de concorrência da SSM
garante a consistência dos dados em um SBDM cujo CC gerencia TGs de forma centralizada.
Em seguida, descreve-se de que forma a proposta SESAMO, cujo CC gerencia TGs de forma
descentralizada, garante a consistência dos dados.
SESAMO – F.Stefan SESAMO: Fundamentos - 94 -
4.6.1 Consistência via SSM centralizada
Em um SBDM, os dados estão armazenados em SBDCs autônomos, os quais, por
definição, preservam a consistência de seus respectivos BDs locais, considerando que a forma
de acesso a cada um deles ocorre somente por meio da execução correta de transações (vide
Subseção 2.4.1).
Em [10], Brayner et al. provaram que:
Considerando-se as seguintes premissas:
Há uma coleção de SBDCs, i.e., SBDs autônomos integrados em um SBDM, sendo
que cada SBDC gerencia um BD local e este corresponde a uma única US. O
conjunto de todos esses BDs locais forma um BD múltiplo denominado BDM.
O SBDM acessa e atualiza o BDM, de forma consistente e confiável, por meio de
TGs.
O SBDM considerado tem um GTG (gerenciador de transações globais)
centralizado em um único computador da rede e implementa a SSM como critério
de controle de concorrência.
Cada TG compõe-se de operações referentes a itens de dados armazenados em uma
ou mais das USs.
O conjunto das operações de uma TG que se destinam a uma mesma US representa
um MS. A execução isolada de cada MS (Definição 14) consiste em uma unidade
consistente de computação, o que preserva a consistência dos dados.
Cada SGBD integrante do SBDM garante a preservação das propriedades ACID das
transações por ele recebidas, garantindo assim a preservação da consistência de seu
BD local.
Então, pode-se afirmar que:
SESAMO – F.Stefan SESAMO: Fundamentos - 95 -
A execução serial de MSs, isto é, um histórico semanticamente serial (Definição
15), preserva a consistência dos dados.
Um histórico semanticamente seriável (Definição 17) é equivalente (Definição 6) a
um histórico semanticamente serial, e, portanto, também preserva a consistência dos
dados.
O GTG considerado produz, a partir da execução de um conjunto de TGs T, uma
execução seriável dos MSs identificados em T, ou seja, um histórico
semanticamente seriável. Dessa forma, o GTG considerado garante a preservação da
consistência do BD múltiplo BDM.
A correção de um histórico semanticamente seriável pode ser conferida, de forma
eficiente, por meio da verificação da ausência de ciclo em um grafo direcionado chamado de
Grafo de Seriação Semântica (Definição 18), o qual modela o histórico semanticamente
seriável. A seguir, são formalizados alguns conceitos, tendo em vista um melhor
entendimento.
Definição 15. Projeção de um histórico.
Considerando-se que S seja um histórico sobre um conjunto T = M ∪ L de transações,
no qual M e L são conjuntos de dados disjuntos. Uma projeção P de S no conjunto M é um
histórico para o qual as seguintes condições devem ser válidas:
i) P contenha apenas operações de transações que pertençam à M,
ii) Quaisquer operações p e q, tais que p,q ∈ OP(P) => p,q OP(SP), e
iii) Quaisquer operações p e q, tais que p,q ∈ OP(P), p <
P
q => p <
S
q.
Definição 16. Histórico semanticamente serial.
Considerando-se que S
G
= U
m
k=1
S
K
seja um histórico global sobre um conjunto T = M
∪ L de TGs e transações locais, respectivamente, e P seja a projeção de S
G
em M. O histórico
global S
G
é semanticamente serial (S
e
Serial) se:
i) Cada histórico local S
K
é seriável; e
SESAMO – F.Stefan SESAMO: Fundamentos - 96 -
ii) Para cada M
i
em P, M
i
é estruturada em módulos e não há entrelaçamento
dentro de um módulo de M
i
, para todos os módulos de M
i
(ou seja,
entrelaçamentos são permitidos apenas entre dois módulos de uma
transação).
Obs: a segunda condição acima força que, em um histórico S
e
Serial, a projeção de
S
G
em M seja uma execução serial de módulos pertencentes a várias TGs. O
resultado disso é que a granulosidade de entrelaçamento para TGs em um histórico
S
e
Serial é em nível de módulo.
Definição 17. Histórico semanticamente seriável.
Um histórico global S
G
= U
m
k=1
S
K
, sobre um conjunto T = M ∪ L de transações móveis
e locais, é semanticamente seriável (S
e
Seriável) se e somente se:
i) Cada histórico local S
K
é seriável; e
ii) A projeção P de S
G
em M é equivalente à projeção P
SS
, sendo esta a
projeção de um histórico S
e
Serial S
ss
sobre T.
Obs1: a classe de todos os históricos semanticamente seriáveis é representada pela
notação S
e
SR
Obs2: esta definição assegura que um histórico global S
G
sobre T é S
e
Seriável se e
somente se ele for equivalente a um histórico S
e
Serial sobre T.
Definição 18. Grafo de Seriação Semântica.
Considerando-se que S seja um histórico sobre T = {T
1
, T
2
, ... T
n
}. O Grafo de Seriação
Semântica de S é um grafo direcionado GSS(S) = (N,E), no qual N = T. O símbolo E
representa o conjunto de arestas rotuladas T
i
USa
> T
j
, sendo T
i,
T
j
∈ N, indicando que há duas
operações p ∈ OP(T
i
), q ∈ OP(T
j
), p <
S
q, as quais se referem a um item de dado da US US
a
,
as quais estão em conflito (Definição 4). A notação OP(T
i
) representa o conjunto de
operações que pertencem a uma certa transação T
i
.
Teorema 1. Um histórico S é semanticamente seriável se e somente se GSS(S), isto é, o
grafo de seriação semântica que modela o histórico S, não contém nenhum ciclo formado por
arestas com o mesmo rótulo, sendo este referente a uma certa US. A prova do citado teorema
pode ser encontrada em [11].
SESAMO – F.Stefan SESAMO: Fundamentos - 97 -
4.6.2 Consistência via SESAMO
No SESAMO, a obtenção de um histórico semanticamente seriável, de forma isolada,
em cada um dos GTGs que operam simultaneamente, é garantida pela preservação das
propriedades ACID de cada MS executado. Essa garantia é atingida pelo uso das regras do
BBF-preciso (vide Subseção 2.6.2), sendo que, em vez de usar as transações como unidades
de consistência, o SESAMO usa os MSs. Dessa forma, todos os bloqueios obtidos pelas
operações pertencentes a um determinado MS são liberados somente após a efetivação
109
do
referido MS. A seguir, mostramos que o SESAMO preserva a consistência de um banco de
dados múltiplo, provando que sua operação forma um histórico semanticamente seriável.
No SESAMO, a atividade de gerenciamento de TGs móveis pode ser distribuída por
vários computadores, de forma que haverá vários controladores de concorrência de TGs
móveis, ou seja, vários GTGs. Cada um dos GTGs estará produzindo um histórico global
parcial semanticamente seriável (HGPSS). As atividades simultâneas de diversos GTGs
podem ser modeladas como um histórico global unificado semanticamente seriável (HGUSS),
resultante da união dos HGPSSs produzidos pelos respectivos GTGs. De acordo com o
Teorema 1, um HGUSS somente poderá ser considerado um histórico semanticamente
seriável caso o seu correspondente grafo de seriação semântica, ou seja, GSS
e
(HGUSS), seja
acíclico.
Dado um certo grafo acíclico, GSS
e
(HGPSS)
A
, produzido por um certo GTG
A,
a única
forma de se adicionar um ciclo a ele é pela adição de uma aresta rotulada T
i
USn
>T
j
, tal que:
T
i
,T
j
∈ T(GTG
A
), sendo T(GTG
A
) o conjunto de TGs sincronizadas por GTG
A;
e
Já exista um caminho direcionado em GSS
e
(HGPSS)
A
iniciando no vértice do grafo
que representa T
j
, de tal forma que o vértice que representa T
i
possa ser alcançado.
Considerando que T(GTG
X
) ∩ T(GTG
Y
) = ∅, para quaisquer GTG
X
, GTG
Y
∈ SBDM
K
,
sendo SBDM
K
um SBDM que usa o SESAMO, não é possível que a união de dois ou mais
grafos acíclicos GSS
e
(HGPSS) produza um grafo cíclico GSS
e
(HGUSS). Portanto, podemos
concluir que o SESAMO produz um grafo GSS
e
(HGUSS) acíclico, ou seja, HGUSS é um
histórico semanticamente seriável e, conseqüentemente, garante a consistência do BD
múltiplo que ele gerencia.
SESAMO – F.Stefan SESAMO: Fundamentos - 98 -
4.6.3 Melhoria do desempenho
A distribuição do gerenciamento de TGs, que é a principal característica do SESAMO,
pode melhorar o desempenho global de um SBDM em relação a soluções que requerem a
centralização do gerenciamento de TGs em um único sistema computacional. A seguir,
formulamos alguns argumentos que levam a essa conclusão.
Em uma solução centralizada, se ocorrer falha no computador onde está operando o
gerenciador de TGs, todas as TGs em andamento serão afetadas de alguma forma. No
SESAMO, se um computador da rede falhar, então serão afetadas somente as TGs dele
originadas, bem como as STs recebidas pelo SGBD local que esteja possivelmente instalado
no referido computador. Assim sendo, as TGs restantes e as demais STs prosseguirão suas
execuções normalmente.
Em uma solução centralizada, cada operação de TG a ser processada deve ser enviada
do computador de origem (cliente) até o gerenciador de TGs. Este, por sua vez, remete a
operação para o SGBD que controla o BD ao qual a operação se refere (BD-alvo). O resultado
de cada operação deve ser enviado do referido SGBD de volta para o gerenciador.
Finalmente, o resultado é enviado do gerenciador para o computador que requisitou a
transação. No SESAMO, cada operação é enviada diretamente do computador de origem até o
SGBD que controla o BD-alvo. O resultado de cada operação é enviado do referido SGBD
para o computador de origem. Percebe-se que o SESAMO requer menor carga de
comunicação para fazer o processamento das operações de TGs.
4.7. Requisitos de uma transação SESAMO
Abstraindo-se de sua lógica, cada TG a ser submetida ao SESAMO deverá se constituir
de uma seqüência de operações, estruturadas conforme indicado na Tabela 3.
Tabela 3 - Operações em uma transação SESAMO
Atributo da operação Valores alternativos possíveis para o atributo
da operação
Tipo Operações sobre TGs:
-Iniciar TG;
-EncerrarBD;
109
A efetivação de um módulo semântico corresponde ao commit da subtransação correspondente, no BD
remoto acessado.
SESAMO – F.Stefan SESAMO: Fundamentos - 99 -
-Efetivar TG;
-Abortar TG.
Operações sobre dados:
-Leitura (corresponde ao “select” no SQL);
-Atualização (update do SQL);
-Inclusão (insert);
-Exclusão (delete).
Comando SQL Somente usado se o tipo de operação for
sobre dados. O conteúdo do comando é
variável.
Cada operação da transação é recebida pelo Gerenciador de Consultas (vide Seção 2.1)
do SBDM gerenciado pelo SESAMO. Para cada operação, o GC poderá gerar várias sub-
operações, de forma que cada uma delas estará associada a um único item de dados, ou seja, a
uma única tupla de uma tabela localizada em algum dos bancos de dados que formam o
SBDM gerenciado pelo SESAMO.
Cada sub-operação será enviada ao GTG, o qual a processará e enviará seu resultado de
volta ao GC. Cada sub-operação terá a estrutura descrita na Tabela 4.
Tabela 4 - Sub-operações de uma transação SESAMO
Atributo da sub-operação Valores alternativos possíveis para o atributo
da sub-operação
Tipo
Operações sobre dados:
-Leitura (corresponde ao comando "select" no
SQL);
-Atualização (update do SQL);
-Inclusão (insert);
-Exclusão (delete).
Sub-comando SQL Somente usado se o tipo de operação for
sobre dados. O conteúdo do comando é
variável.
BD-alvo Esta informação é extraída do comando SQL
da operação original.
Classe de itens de dados Esta informação é extraída do comando SQL
da operação original.
Chave primária do item de dado Esta informação é extraída do comando SQL
da operação original.
A geração das sub-operações a partir de uma operação da transação é uma atividade do
Gerenciador de Consultas (GC) e, portanto, não faz parte da abrangência desta dissertação.
SESAMO – F.Stefan SESAMO: Fundamentos - 100 -
Ademais, é relevante relembrar, conforme já mencionado anteriormente, que uma
transação é uma ordenação parcial de operações. Assim sendo, algumas operações da mesma
transação poderão ser processadas em paralelo, sem seguir uma ordem relativa entre elas. O
encargo de manter a seqüência com que cada operação é encaminhada ao GTG do SESAMO
é também do GC, não estando também esse assunto coberto por esta dissertação.
4.8. Estudo de Caso: sistema múltiplo de vendas
Nesta seção, é apresentado um estudo de caso no qual se mostra a vantagem de se usar o
CC proposto pelo SESAMO, em relação a um CC baseado nas regras do BBF-preciso.
4.8.1 Descrição do cenário
Em uma determinada feira de negócios, um microempresário e seu sócio carregam
consigo dois computadores portáteis. Em um deles, está armazenado o SBD C, o qual
armazena um BD autônomo que controla pedidos de venda de artigos de pesca. No outro
computador portátil, está o SBD D, o qual mantém um controle de pedidos de venda de
artigos de couro. Em cada um dos computadores portáteis, está instalado um sistema de
compras que integra os referidos BDs, de forma que um usuário desse sistema possa
cadastrar, por exemplo, um pedido de compra que contém artigos dos dois BDs. Considerem-
se também as seguintes premissas:
Cada um dos BDs representa uma US.
Há dois tipos de transações: o tipo X e o tipo Y. A transação do tipo X é formada
pela seguinte seqüência de operações: {IniciarTG; gravarPed(C); encerrarBD(C);
gravarPed(D); efetivarTG}. A transação do tipo Y é formada pela seguinte
seqüência de operações: {IniciarTG; gravarPed(D); encerrarBD(D); gravarPed(C);
efetivarTG}.
A operação gravarPed representa um macrocomando SQL e, para efeito de
simplificação, será considerada como uma operação atômica, isto é, ela não será
fragmentada pelo CC. A notação gravarPed(D) indica que deverá ser gravado um
pedido de venda relativo a uma determinada mercadoria registrada no BD D. De
forma a mostrar uma situação bem genérica, iremos considerar que todas as
operações do tipo gravarPed conflitam entre si.
SESAMO – F.Stefan SESAMO: Fundamentos - 101 -
Há duas TGs do tipo X (A
1
e A
2
) e iniciadas a partir do computador móvel CM
A
. Há
duas TGs do tipo Y (B
1
e B
2
) e iniciadas a partir do computador móvel CM
B
. Iremos
considerar a execução das quatro TGs mencionadas em dois cenários. Um deles
modela o funcionamento do SESAMO, conforme descrito na Tabela 5. O outro
cenário, disposto na Tabela 6, modela o funcionamento de um CC que implementa
o protocolo BBF-preciso, o qual impõe a formação de um histórico global seriável.
SESAMO – F.Stefan SESAMO: Fundamentos - 102 -
Tabela 5 – Execução do cenário usando o SESAMO
TG = A1 GTG = A
Operação BD
TG
Operação BD
iniciarTG
A1 iniciarTG
gravarPed C
A1 gravarPed C
encerrarBD
C
A2 iniciarTG
gravarPed D
A2 gravarPed C
efetivarTG
A1 encerrarBD
C
A2 encerrarBD
C
TG = A2
A1 gravarPed D
Operação BD
A2 gravarPed D
iniciarTG
A1 efetivarTG
gravarPed C
A2 efetivarTG
encerrarBD
C
gravarPed D
efetivarTG
TG = B1 GTG = B
Operação BD
TG
Operação BD
iniciarTG
B1 iniciarTG
gravarPed D
B1 gravarPed D
encerrarBD
D
B2 iniciarTG
GravarPed C
B2 gravarPed D
efetivarTG
B1 encerrarBD
D
B2 encerrarBD
D
TG = B2
B1 gravarPed C
Operação BD
B2 gravarPed C
iniciarTG
B1 efetivarTG
gravarPed D
B2 efetivarTG
encerrarBD
D
gravarPed C
efetivarTG
GTG = A GTG = B
TG
Operação BD
TG
Operação BD
A1
iniciarTG
B1 iniciarTG
A1
gravarPed C
B1 gravarPed D
A2
iniciarTG
B2 iniciarTG
A2
gravarPed C
B2 gravarPed D
A1
encerrarBD C
B1 encerrarBD
D
A2
encerrarBD C
B2 encerrarBD
D
A1
gravarPed D
B1 gravarPed C
A2
gravarPed D
B2 gravarPed C
A1
efetivarTG
B1 efetivarTG
A2
efetivarTG
B2 efetivarTG
SBD = C SBD = D
Operação TG
Operação TG
1
iniciarSG A1
2
iniciarSG B1
gravarPed A1
3
gravarPed B1
iniciarSG A2
4
iniciarSG B2
gravarPed A2
5
gravarPed B2
efetivar A1
6
efetivar B1
efetivar A2
7
efetivar B2
iniciarSG B1
8
iniciarSG A1
gravarPed B1
9
gravarPed A1
iniciarSG B2
10
iniciarSG A2
gravarPed B2
11
gravarPed A2
efetivar B1
12
efetivar A1
efetivar B2
13
efetivar A2
Neste cenário, podem ser feitas as seguintes observações:
1-No SBD C, A1 é seriada antes de B2. Já no SBD D, B2 é seriada antes de A1.
2-A efetivação de A1 no SBD C ocorre de forma independente e bem antes da
efetivação de A1 no SBD D. Dessa forma, quaisquer bloqueios que A1 tenha sobre itens de
dados no SBD C serão liberados bem antes de haver a efetivação global de A1.
SESAMO – F.Stefan SESAMO: Fundamentos - 103 -
Tabela 6 - Execução do cenário usando o BBF-preciso
TG = A1 GTG = A
Operação BD
TG
Operação BD
iniciarTG
A1 iniciarTG
gravarPed C
A1 gravarPed C
encerrarBD
C
A2 iniciarTG
gravarPed D
A2 gravarPed C
efetivarTG
A1 encerrarBD
C
A2 encerrarBD
C
TG = A2
A1 gravarPed D
Operação BD
A2 gravarPed D
iniciarTG
A1 efetivarTG
gravarPed C
A2 efetivarTG
encerrarBD
C
gravarPed D
efetivarTG
TG = B1 GTG = B
Operação BD
TG
Operação BD
iniciarTG
B1 iniciarTG
gravarPed D
B1 gravarPed D
encerrarBD
D
B2 iniciarTG
gravarPed C
B2 gravarPed D
efetivarTG
B1 encerrarBD
D
B2 encerrarBD
D
TG = B2
B1 gravarPed C
Operação BD
B2 gravarPed C
iniciarTG
B1 efetivarTG
gravarPed D
B2 efetivarTG
encerrarBD
D
gravarPed C
efetivarTG
GTG = A GTG = B
TG
Operação BD
TG
Operação BD
A1
iniciarTG
B1 iniciarTG
A1
gravarPed C
B1 gravarPed D
A2
iniciarTG
B2 iniciarTG
A2
gravarPed C
B2 gravarPed D
A1
encerrarBD C
B1 encerrarBD
D
A2
encerrarBD C
B2 encerrarBD
D
A1
GravarPed D
B1 gravarPed C
A2
GravarPed D
B2 gravarPed C
A1
EfetivarTG
B1 efetivarTG
A2
EfetivarTG
B2 efetivarTG
SBD = C SBD = D
Operação TG
Operação TG
1
iniciarSG A1
2
iniciarSG B1
gravarPed A1
3
gravarPed B1
iniciarSG A2
4
iniciarSG B2
gravarPed A2
5
gravarPed B2
6
7
iniciarSG B1
8
iniciarSG A1
gravarPed B1
9
gravarPed A1
iniciarSG B2
10
iniciarSG A2
gravarPed B2
11
gravarPed A2
efetivar A1
12
efetivar A1
efetivar A2
13
efetivar A2
efetivar B1
14
efetivar B1
efetivar B2
15
efetivar B2
Neste cenário, podem ser feitas as seguintes observações:
1-As transações A1 e B2 são seriadas da mesma forma em SBD C e SBD D.
2-A efetivação de uma TG em qualquer SBD somente pode ocorrer ao final da
transação. Além disso, a ordem relativa de efetivação das TGs em cada SBD deve ser igual.
Os bloqueios retidos somente são liberados ao final de cada transação.
SESAMO – F.Stefan SESAMO: Fundamentos - 104 -
4.8.2 Discussão
No cenário em que o SESAMO é executado, há as seguintes vantagens em relação ao
outro cenário:
A efetivação de uma ST SG
ij
em um SBD
j
, de forma independente da efetivação
global da TG de origem TG
i
, faz com que sejam liberados todos os bloqueios retidos
por SG
ij
sobre itens de dados de SBD
j
. Isso, obviamente, permitirá que outras STs
ou transações locais possam ter acesso aos referidos itens de dados, aumentando o
grau de paralelismo e, conseqüentemente, a vazão de processamento de SBD
j
. A
título de exemplo, observe-se a efetivação da TG A
1
no SBD C. Usando o SESAMO
(Tabela 5), A
1
foi efetivada no instante 6 (vide numeração seqüencial destacada em
negrito). Já usando o BBF-preciso (Tabela 6), A
1
somente foi efetivada no instante
12, que corresponde ao momento em que A
1
também pôde
ser efetivada no SBD D.
A ordem relativa de efetivação de quaisquer duas TGs pode ser diferente em cada
SBD em que elas tenham operações em conflito, o que impede que uma delas seja
abortada por ter violado a ordem global de seriação. A redução de abortos promove
indiretamente um aumento na vazão de processamento de um SBD. A título de
exemplo, considere as TGs A
1
e B
2
. No SESAMO, A
1
foi efetivada (instante 6) antes
de B
2
(instante 13) no SBD C. Já no SBD D, a ordem de efetivação foi invertida,
pois B
2
foi efetivada (instante 7) antes de A
1
(instante 12). No BBF-preciso, A
1
foi
efetivada (instante 12) antes de B
2
(instante 15) tanto no SBD C quanto no SBD D.
4.9. Resumo do capítulo
Neste capítulo, foram apresentados os modelos de estrutura e operação do SESAMO.
Ademais, foi demonstrado de que forma o SESAMO garante a consistência dos dados e
preserva a autonomia dos SBDCs integrantes de um SBDM com suporte à mobilidade.
Conforme visto, tais funcionalidades do SESAMO são requisitos essenciais para qualquer
solução de CC para SBDMs e, por este motivo, são usadas como base de comparação do
SESAMO com trabalhos correlatos, conforme pode ser visto no Capítulo 5.
- 105 -
CAPÍTULO V
Trabalhos Correlatos
- 106 -
5. Trabalhos Correlatos
Neste capítulo, são apresentadas algumas propostas acadêmicas que abordam CCs de
TGs em SBDMs com suporte à computação móvel. Para cada uma das propostas discutidas,
apresenta-se uma descrição resumida da proposta, seus objetivos, o modelo de transação na
qual ela se baseia, a infra-estrutura de gerenciamento de dados e transações, bem como o
processo de gerenciamento da execução de uma TG. Ao final deste capítulo, apresenta-se uma
análise comparativa dos mecanismos apresentados, em relação ao SESAMO.
5.1. Kangaroo
O Kangaroo [23] é uma proposta de gerenciamento de transações baseada em um
modelo de transação que usa transações dos tipos multinivelada-aberta
110
[57] e
desdobrável
111
. Seu objetivo principal é integrar o gerenciamento de transações com o
gerenciamento da mobilidade dos computadores móveis (CMs). A arquitetura do modelo tem
três componentes básicos: os SBDMs componentes, situados em nós fixos da rede; os
Agentes de acesso aos dados (AAD), situados nas ESMs; e as transações móveis, que são
disparadas a partir dos CMs.
O processamento de uma transação ocorre da forma seguinte. Um CM (chamado CM-
originador) solicita a execução de uma transação à ESM que cobre sua célula. O AAD local
da ESM cria uma TG chamada KT (kangaroo transaction) e uma ST chamada JT (joey
transaction). A JT é a unidade consistente de computação em uma ESM. A partir da JT, o
AAD cria e executa, em série, uma ST para cada SBD local ou múltiplo no qual a KT original
tiver dados para processar. Caso ocorra migração do CM originador para outra célula, então
ocorre o desdobramento da JT que estava em execução em duas JTs. A JT original continua
executando as STs que já haviam iniciado. A outra JT será criada pela ESM que estiver
cobrindo a célula para onde migrou o CM originador. Essa nova JT se encarregará de executar
o restante do código, ainda não executado, da KT original.
110
NT: open-nested transaction.
111
NT: split transaction.
SESAMO – F.Stefan Trabalhos Correlatos - 107 -
5.2. Pro-motion
O Pro-motion [67,68] é uma proposta de gerenciamento de transações móveis que se
baseia nos modelos de transações multinivelada-aberta e multinivelada-desdobrável
112
[2]. O
Pro-motion objetiva dar suporte ao processamento de transações durante os momentos em que
os CMs perdem a conexão com a rede, oferecendo mecanismos locais de replicação de dados
e gerenciamento de transações. A unidade básica de dados, para fins de replicação e
consistência, é o chamado compacto
113
, o qual armazena itens de dados e seus métodos de
acesso, bem como informações e restrições necessárias para o gerenciamento de transações.
Os componentes básicos da infra-estrutura são: o Agente-de-Compactos , o qual fica situado
em cada um dos CMs e é responsável pelas tarefas de controle do estado da conexão,
gerenciamento local de transações, gerenciamento local de dados replicados, e pela
localização das fontes primárias dos dados; o Gerenciador-de-Compactos, o qual fica situado
em cada SBD fixo que é acessado pelas TGs; e o Gerenciador-de-Mobilidade, que fica
situado em cada uma das ESMs e é responsável pela interligação dos outros componentes.
De forma resumida, a execução de uma transação consiste na solicitação, replicação,
armazenamento, acesso e atualização, tudo isso feito na memória de um CM, de um ou mais
compactos que foram criados e enviados pelos Gerenciadores-de-Compactos de cada SBD
acessado pela transação. O processo de replicação ocorre por meio de um acordo que o
Gerenciador-de-Compactos faz com o Agente-de-Compactos, de forma que os direitos de
atualização de cada compacto solicitado ficam delegados temporariamente ao Agente-de-
Compactos, o qual deverá obedecer a todas as restrições que o Gerenciador-de-Compactos
tiver registrado em cada compacto. O direito de atualização do compacto retorna ao
Gerenciador-de-Compactos logo que a fase de sincronização de dados entre CM e SBD é
iniciada ou quando o tempo de uso definido pelo Gerenciador-de-Compactos expira.
Logo que o CM se conecta à rede, o Agente-de-Compactos local dispara o processo de
sincronização, o qual consiste na validação e propagação das atualizações, feitas no CM, para
os SBDs fixos. Durante a sincronização de um CM, o Gerenciador-de-Compactos local do
SBD cria e gerencia a execução de uma transação de sincronização, contendo todas as
transações já efetivadas no CM, mas ainda não validadas e propagadas.
112
NT: nested-split transaction.
113
NT: Compact.
SESAMO – F.Stefan Trabalhos Correlatos - 108 -
O critério de correção do Pro-Motion é baseado no uso de níveis progressivos de
garantia de isolamento de uma transação em relação às demais. Cada compacto pode ter um
modo de operação e um critério de correção para cada um de seus métodos. Cada aplicação
pode especificar o seu próprio nível mínimo de isolamento ou assumir valores padrões
especificados pelo próprio Gerenciador-de-Compactos. A execução de uma transação será
considerada correta caso as seguintes condições forem obedecidas: i) os níveis de isolamento
definidos nos métodos de todos os compactos que foram acessados não forem menores que os
níveis definidos na transação; e ii) o menor nível de isolamento, dentre os métodos de leitura
de todos os compactos acessados, não seja menor que o maior nível dentre os métodos de
gravação de todos os compactos acessados.
5.3. PSTM
PSTM é uma proposta de gerenciamento de transações baseado no modelo de transação
multinivelada aberta, que usa como critério de correção a serialidade dos históricos globais e
a atomicidade global semântica
114
. O modelo de referência da proposta é composto pelos
seguintes componentes: a transação global (TG); as subtransações (STs); o gerenciador de
STs
115
(GS), situado em cada sistema computacional no qual reside um SBD-participante da
transação; e o gerenciador de transações globais
116
(GTG), situado em cada estação de suporte
à mobilidade (ESM). O GS supervisiona a execução local das STs, em cada SBD participante.
O processamento de uma TG ocorre em duas fases, a seguir especificadas.
Fase 1. Esta fase se caracteriza pela execução independente das STs. Uma TG G
i
é
requisitada ao GTG por um CM, denominado aqui CM-originador. O GTG inicia a execução
de G
i
, gerando STs do tipo S
ik
. Cada ST S
ik
pode ser designada como vital ou não-vital. G
i
somente será efetivada caso todas as suas STs vitais tiverem sido efetivadas. O GTG envia
cada ST do tipo S
ik
, juntamente com sua respectiva transação de compensação [12,39], para o
gerenciador de STs GS
j
, o qual faz parte do SBD SBD
j
, sistema em que S
ik
deverá executar
seu processamento. GS
j
recebe as operações de S
ik
e as submete a SBD
j
. Cada GS
j
mantém um
grafo-de-seriação-local GSL
j
, o qual mantém informações sobre a ordem de seriação das STs
vitais no SBD local. A ordem de seriação das STs vitais é determinada pela ordem com que
114
Neste modelo, uma TG consiste em um conjunto de subtransações compensáveis. Uma transação (ou
subtransação) compensável é aquela que, mesmo após sua efetivação, poderá ser desfeita pela execução de uma
transação (ou subtransação) de compensação [39].
115
Na versão original, esse componente é chamado de site-transaction manager (STM).
SESAMO – F.Stefan Trabalhos Correlatos - 109 -
elas obtiveram ingressos [30] para acesso ao SBD local. A informação sobre o gerenciamento
de uma TG migra juntamente com o CM-originador.
Cada ST S
ik
poderá ser efetivada ou abortada pelo GS que a gerencia, de forma
antecipada e independente do resultado da TG ou de outras STs. A perda de conexão com a
rede do CM-originador de G
i
fará com que esta TG seja suspensa pelo GTG até que a conexão
seja restabelecida. Transações globais suspensas serão abortadas pelo GTG apenas se
estiverem impedindo, em algum momento, a execução de alguma TG ativa. Após o término
de todas as STs vitais, termina a primeira fase e inicia-se a segunda.
Fase 2. Esta fase é caracterizada pela verificação da atomicidade e isolamento globais,
seguida da efetivação da TG G
i
. Inicialmente, é feita a verificação da atomicidade global. Se
alguma ST vital tiver sido abortada, então G
i
será abortada e cada uma das STs será abortada
(caso esteja ativa) ou compensada (caso já tenha sido efetivada). Se, por outro lado, todas as
STs tiverem sido efetivadas, então o processamento prosseguirá com a verificação da
propriedade de isolamento global. Informações são coletadas a partir dos grafos-de-seriação-
local de todos os GSs participantes da TG G
i
, para fins de construção do grafo-de-seriação-
global-parcial. Se o isolamento tiver sido violado, então o GTG aborta G
i
e propaga a
informação para todos os GSs participantes de G
i
. Se o isolamento não tiver sido violado,
então G
i
é marcada como correta, em termos de isolamento, e as informações do grafo-de-
seriação-global-parcial serão propagadas para os grafos-de-seriação-local de todos os GSs
participantes de G
i
.
5.4. V-Lock
Esta proposta [46] consiste em um mecanismo de gerenciamento de transações que usa
como critério de correção a serialidade dos históricos de TGs executadas em determinados
nós da rede, os quais exercem, simultaneamente, o papel de coordenadores de TGs. A
atomicidade dos históricos é assegurada pelo protocolo EBF.
O gerenciador de TGs compõe-se de dois mecanismos. Um deles é o V-lock, o qual é
responsável pelo controle de concorrência. O outro é o P-caching, que é responsável pela
atividade de replicação de dados na memória dos CMs. O modelo de referência do
gerenciamento de transações é formado pelos seguintes elementos: (i) O Modelo Sumário de
116
NT: global-transaction coordinator (GTC).
SESAMO – F.Stefan Trabalhos Correlatos - 110 -
Esquemas
117
(MSE), que é uma infra-estrutura de integração e acesso a SBDs distribuídos,
múltiplos e hierárquicos; (ii) Nós fixos MSE. Cada nó fixo MSE contém um catálogo de
informações, estruturadas em forma de árvore, sobre os esquemas dos BDs integrados; e (iii)
CMs originadores de TGs.
O P-caching consiste em um mecanismo que dispara, de acordo com o perfil do usuário,
consultas automáticas e armazenamento dos resultados na memória de acesso rápido
118
do
CM, visando garantir a disponibilidade de dados nos momentos de desconexão ou pouca
disponibilidade da rede. O objetivo do V-lock é seriar as operações conflitantes de TGs, como
também detectar e remover bloqueios cíclicos globais. A seguir, é descrito um exemplo de
processamento de uma TG.
Uma TG G
i
é requisitada por um computador móvel CM
j
a um nó fixo MSE F
k
. O V-
lock consulta, no esquema global parcial de F
k
, a localização de todos os dados a serem
processados por G
i
. Se F
k
não contiver todas as informações de localização necessárias, então
o V-lock continua a busca pelas informações em outro nó MSE da rede (F
l
), seguindo a
indicação existente no esquema global parcial de F
k
. O processo de busca se repete até que o
V-lock encontre um nó MSE F
w
que contenha todas as informações sobre a localização dos
dados a serem processados por G
i
. F
w
fica então sendo o coordenador da TG, ao qual nos
referiremos simplesmente por Coordenador. O Coordenador então se encarrega de controlar a
execução correta de G
i
segundo o critério da serialidade permanente do histórico de execução
de TGs, isto é, o histórico global.
O V-lock assegura a serialidade do histórico global pelo uso de uma tabela-de-
bloqueio-global. O V-lock também previne e remove os BCGs que surgirem durante o
processamento, usando um GEG. O V-lock bloqueia e registra na tabela-de-bloqueio-global,
de acordo com as regras do protocolo tradicional BBF, os itens de dados envolvidos em G
i
.
As STs são criadas e enviadas, juntamente com as informações da tabela-de-bloqueio-global e
GEG, para os nós MSE onde estiverem os SBDs que contêm os dados a serem processados
pelas STs. A qualquer momento, cada um desses SBDs (SBDs participantes) poderá abortar,
de forma independente, sua respectiva ST. Já a efetivação deverá seguir as regras do
protocolo de efetivação EBF.
117
NT: summary schemas model.
118
NT: cache.
SESAMO – F.Stefan Trabalhos Correlatos - 111 -
5.5. GTM
O GTM é o mecanismo de gerenciamento de TGs proposto para a estrutura de SBDM
denominada AMDB (Accessing Mobile Databases) [8]. A AMDB consiste em uma
arquitetura de acesso a uma comunidade de bancos de dados móveis
119
, ou seja, um ambiente
físico dinamicamente configurável e composto por uma coleção de SBDs autônomos e
heterogêneos, situados em CMs e interligados através de uma RCMD (vide Subseção 3.6.1).
Sobre a referida infra-estrutura de rede da AMDB, funciona uma camada de aplicação
que fornece a interface necessária entre as aplicações de usuários e os SBDCs. Essa interface
é implementada com base na tecnologia de agentes itinerantes (ou resumidamente agentes)
[23,44,46]. A seguir, descreve-se o processamento típico de uma TG nesse ambiente.
Um usuário ou programa faz uma solicitação S, a partir de um computador móvel
CM
i
, para a criação de uma nova TG móvel. A solicitação S é recebida na AMDB
por meio de um agente fixo local AgT
i
, que é do tipo Tradutor
120
, o qual é
responsável pela interface entre os CMs e a arquitetura AMDB;
O AgT
i
encaminha a solicitação S, por intermédio do agente móvel AgE
i
, que é do
tipo Executor
121
, ao agente-tradutor AgT
j
, situado no CM CM
j
, o qual foi designado
previamente para ser o gerenciador de TGs da rede;
O AgT
j
, por intermédio de seu componente Gerenciador de Transações Móveis
122
(GTM), cria efetivamente a transação G e despacha cada operação Op
Gk
de G para
um agente móvel do tipo executor AgE
j
; e
AgE
j
transporta o código de cada operação Op
Gk
até o CM onde estiver o banco de
dados BD
w
ao qual Op
Gk
se refere, submete Op
Gk
a BD
w
, recebe o resultado de BD
w
e transporta o resultado de volta para o GTM. O GTM então repassa o resultado de
cada operação Op
Gk
para AgE
i
e este para AgT
i
, o qual repassa finalmente para o
programa ou usuário que fez a solicitação S.
119
NT: mobile database community (MDBC).
120
NT: wrapper.
121
NT: runner.
122
NT: mobile transaction manager (MTM).
SESAMO – F.Stefan Trabalhos Correlatos - 112 -
Cada operação segue os três passos básicos acima descritos, até chegar a fase de
efetivação da TG móvel, a qual é cumprida por meio de um protocolo de efetivação
atômica semelhante ao EBF (vide Subseção 3.3.1).
O conjunto de fragmentos de código de uma TG submetidos a um mesmo SBD
representa uma ST. Cada SBD processa as STs da mesma forma que faz com suas transações
locais, o que garante então a execução correta das STs. O GTM não tem controle sobre a
atividade dos gerenciadores locais de transações dos SBDs acessados, a não ser durante a fase
de efetivação da TG, devido ao uso de um protocolo de efetivação atômica que segue as
regras do EBF. O GTM garante a correção do histórico de execução das TGs móveis pelo uso
de um algoritmo que usa um GSS (vide Definição 18).
5.6. Análise comparativa do SESAMO com trabalhos correlatos
Neste tópico, será apresentada uma análise comparativa dos GTs (gerenciadores de
transações) descritos neste capítulo, em relação ao SESAMO. Alguns dos critérios usados
para efeito de comparação das propostas foram selecionados dentre os requisitos mais
importantes, segundo os autores pesquisados, para o gerenciamento de TGs, atividade esta da
qual o CC faz parte. Outros critérios foram acrescentados por fazerem parte das atividades do
GD (Seção 2.1), que é um dos componentes do SGBD que influencia no desempenho do GT
(Seção 2.1) [33].
As seguintes convenções são usadas nas próximas subseções:
Cada SBD autônomo que participa de uma TG será referido por SBD-participante.
SBDs-participantes fixos são aqueles situados em servidores de BD estacionários,
ligados a uma rede fixa de computadores;
Cada ESM (estação de suporte à mobilidade) visitada por uma TG será denominada
como ESM-participante; e
Os dispositivos computacionais móveis serão referidos pelo acrônimo CM
(computador móvel). CM-originador refere-se ao computador móvel que solicitou o
início de execução de uma TG móvel.
SESAMO – F.Stefan Trabalhos Correlatos - 113 -
5.6.1 Modelo de transação e critério de correção
Nesta seção, serão analisadas as seguintes propriedades do modelo de transação de cada
mecanismo proposto:
A identificação do modelo e os tipos de transação;
O critério de correção do modelo. A análise usa como referência o critério de
correção tradicional, o qual assegura que a preservação das propriedades ACID de
cada transação executada em um BD preserva a consistência desse BD. A análise
indica então quais das propriedades ACID o modelo de transação preserva e de que
forma ele faz isso.
A Tabela 7 mostra que o Kangaroo e o PSTM mantêm a atomicidade global ao custo de
procedimentos de compensação, os quais são complexos. O Pro-motion garante a atomicidade
global, mas poderá precisar de procedimentos de compensação, durante a fase de conciliação
entre o CM-originador e os SBDs-participantes. Somente o V-lock e o GTM preservam a
atomicidade de uma forma mais simples, via protocolos de efetivação atômica.
O SESAMO não aborda a atomicidade global. Essa omissão, no entanto, não representa
uma desvantagem, pois mesmo que a atomicidade global fosse violada, a consistência dos
SBDs-participantes não seria violada, devido à flexibilização promovida pelo critério de
correção da SSM. Maiores detalhes podem ser vistos nas Seções 4.2 e 4.6.
A consistência e o isolamento globais são assegurados por todos os GTs comparados, à
exceção do Kangaroo, o qual poderá violar a consistência global de um SBDM. No Pro-
motion, os Compactos também auxiliam na preservação das propriedades globais de
consistência, isolamento e durabilidade das TGs.
Em todos os mecanismos comparados, a preservação da durabilidade global e de todas
as propriedades das STs fica ao encargo dos SBDs-participantes. No Pro-motion, além dos
SBDs-participantes, os Compactos gerados também auxiliam na tarefa de preservação das
propriedades de consistência e isolamento das STs.
SESAMO – F.Stefan Trabalhos Correlatos - 114 -
Tabela 7 – Controladores de concorrência: modelo de transação e critério de correção
Modelo de
transação
Tipos de
transação
Atomicidade Consistência Isolamento Durabilidade
Global Compensação
Não garante Não garante
Desdobrável Compensação
Serialidade Serialidade
Kangaroo
(Dunham et al,
1997)
Transação
multinivelada
aberta
E
Transação
desdobrável
Subtransação
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
Global
Protocolo
EBF
Compactos Compactos Compactos
Pro-Motion
(Walborn e
Chrysanthis,
1999)
Transação
multinivelada
aberta
E
Transação
desdobrável
Desdobrável Compensação
Compactos Compactos
SBDs-
participantes
Global Compensação
Serialidade Serialidade
PSTM
(Dirckze e
Gruenwald,
2000)
Transação
multinivelada
aberta
Subtransação
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
Global
Protocolo
EBF
Serialidade
distribuída
Serialidade
distribuída
V-lock
(Lim e
Hurson, 2002)
Transação
multinivelada
aberta
Subtransação
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
Global
Protocolo
semelhante
ao EBF
SSM Desnecessário
GTM
(Brayner e
Morais, 2003)
Transação
semanticamente
seriável
Subtransação
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
Global Não aborda SSM Desnecessário
SESAMO
(Brayner e
Alencar, 2005)
Transação
semanticamente
seriável
Subtransação
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
SBDs-
participantes
5.6.2 Infra-estrutura de gerenciamento de dados
Nesta Subseção, são comparadas as seguintes propriedades de cada CC no tocante à
atividade de gerenciamento de dados:
A arquitetura dos SBDs-participantes. A classificação aqui utilizada baseia-se nos
critérios definidos nas Subseções 3.1.3 e 3.4.4;
O meio de acesso aos dados, isto é, a tecnologia que permite aos SGBDs envolvidos
no SBDM se comunicarem de forma transparente sem ter que lidar com aspectos
relacionados à distribuição dos dados;
Localização primária dos dados. Trata-se da unidade computacional que contém a
fonte oficial dos dados, os quais podem estar replicados em outras unidades
computacionais da rede;
SESAMO – F.Stefan Trabalhos Correlatos - 115 -
Suporte à replicação. Esta característica indica se o mecanismo dispõe de
procedimentos que fazem a replicação dos dados, no intuito de manter sua
disponibilidade, mesmo nos momentos de conexão instável ou de desconexão da
rede; e
Suporte à fragmentação. Esta característica visa aumentar a disponibilidade dos
dados.
A Tabela 8 mostra que todos os mecanismos acessam uma arquitetura cliente-servidor,
à exceção da usada pelo GTM e SESAMO, os quais usam uma arquitetura cooperativa. Todos
os mecanismos acessam BDs múltiplos, mas somente o Kangaroo, o V-lock, o GTM e o
SESAMO acessam BDs heterogêneos. O meio de acesso aos dados é predominantemente via
agentes itinerantes, à exceção do PSTM e SESAMO, os quais presumem o uso de interfaces
de serviço oferecidas pelos SBDCs.
Em todos os mecanismos comparados, exceto no GTM e no SESAMO, a localização
primária dos dados são, necessariamente, servidores de BDs fixos. No GTM e SESAMO, os
BDs podem residir em CMs. Somente o Pro-motion e o V-lock oferecem suporte à replicação
dos dados primários nos CMs. Quanto à fragmentação dos dados, somente o Pro-motion dá
esse suporte.
Tabela 8 – Controladores de concorrência: infra-estrutura de gerenciamento de dados
Arquitetura dos SBDs
participantes
123
Meio de acesso
aos dados
Localização
primária dos
dados
Suporte à
replicação
Suporte à
fragmentação
Kangaroo
Cliente-servidor -
Múltiplos –
Heterogêneos
Agentes das
ESMs
SBDs-
participantes
fixos
Não investiga Não investiga
Pro-motion
Cliente-servidor –
Múltiplos
Agente-de-
compactos +
Gerenciador-de-
Mobilidade +
Gerenciador-de-
Compactos
SBDs-
participantes
fixos
Via compactos Via compactos
PSTM
Cliente-servidor -
Múltiplos
Interface de
serviços em
cada SBD-
participante
SBDs-
participantes
fixos
Não investiga Não investiga
V-lock
Cliente-servidor –
Múltiplos -
Heterogêneos
Agentes MSE
SBDs-
participantes
fixos
Somente para
operações de
leitura
Não investiga
GTM
Colaborativos–
Múltiplos –
Heterogêneos
Agentes AMDB
CMs Não investiga Não investiga
123
A classificação aqui utilizada baseia-se nos critérios usados nas seções 3.1.3 e 3.4.4.
SESAMO – F.Stefan Trabalhos Correlatos - 116 -
Arquitetura dos SBDs
participantes
123
Meio de acesso
aos dados
Localização
primária dos
dados
Suporte à
replicação
Suporte à
fragmentação
SESAMO
Colaborativos –
Múltiplos – Heterog.
Não investiga CMs Não investiga Não investiga
5.6.3 Infra-estrutura de gerenciamento de transações globais
Nesta Subseção, serão comparadas algumas propriedades de cada GT sob análise,
relativas à atividade de gerenciamento de transações em um sentido amplo, englobando não
só o controle de concorrência, mas também a efetivação atômica de transações e
procedimentos de recuperação pós-falhas. As propriedades analisadas são:
Identificação do componente de gerenciamento de transações usado para cada tipo
de transação com que o mecanismo lida;
Local de controle de cada tipo de transação;
Suporte à migração e desconexão do CM originador da TG durante a execução
desta, de forma a reagir especificamente a esses problemas;
Possibilidade de efetivação antecipada de cada ST, sem depender do destino da TG
de origem, bem como das outras STs dessa TG;
Suporte ao gerenciamento de recuperação do SBDM. Esta característica indica se o
gerenciador de TGs já tem alguma implementação de um protocolo específico para
recuperar o SBDM após a ocorrência de falhas; e
Preservação da autonomia dos SBDs-participantes em termos de gerenciamento de
transações e gerenciamento das estruturas de dados.
Na Tabela 9, pode ser constatado que o Pro-motion e SESAMO permitem que as TGs
possam ser criadas nos próprios CMs que as originaram (CMs-originadores). No Kangaroo e
no PSTM, a criação das transações ocorre nas ESMs. No GTM e no V-lock, as TGs são
criadas no chamado CM-coordenador.
De forma geral, os GTs analisados efetuam o gerenciamento das transações nas ESMs
ou em outros nós da rede, sejam CMs ou servidores de bancos de dados fixos. Somente no
SESAMO, o controle de concorrência é feito totalmente pelo CM-originador da transação, o
SESAMO – F.Stefan Trabalhos Correlatos - 117 -
que representa um ganho de autonomia por parte do CM, além de reduzir a quantidade de
mensagens na rede, necessárias para o gerenciamento das transações.
O Kangaroo e o PSTM oferecem suporte para a migração dos CMs, durante a execução
das transações. Apenas o PSTM permite a execução de quaisquer operações durante os
momentos de desconexão dos CMs, o que representa uma vantagem em relação aos demais
sob o ponto de vista da disponibilidade dos dados, embora a garantia de consistência mútua
dos dados, entre as fontes primária e secundária, poderá ser violada. Tal problema é comum
em mecanismos que usam a replicação de dados [46]. O Pro-motion e o V-lock somente
oferecem suporte à desconexão, mas apenas para operações de leitura de dados. O GTM e o
SESAMO não investigam essa questão.
A efetivação antecipada e independente das STs pode ser feita apenas no Kangaroo, no
PSTM e no SESAMO, visto que o Pro-motion, o V-lock e o GTM usam algum tipo de
protocolo de efetivação atômica. O Pro-motion pode, dependendo da transação, efetivar
antecipadamente algumas STs, o que o fará utilizar os procedimentos eventuais de
compensação.
Sob o aspecto do gerenciamento da recuperação, apenas o Pro-motion prevê uma
estrutura de recuperação, a qual está baseada nas informações contidas nos Compactos. O
Kangaroo dispõe apenas de mecanismos de registro de ocorrências a ser usado em um futuro
mecanismo de recuperação. Os demais GTs não contam com mecanismos de recuperação
automática.
Sob o ponto de vista da preservação da autonomia dos SBDs-participantes, somente o
Kangaroo e o SESAMO atendem a esse requisito. Os demais violam parcialmente a
autonomia como forma de impor aos SBDs-participantes uma ordem de seriação das STs. O
Pro-motion, o V-lock e o GTM violam a autonomia, devido ao uso de um protocolo de
efetivação atômica [46] baseado no EBF. O PSTM viola a autonomia devido ao requisito de
incluir estruturas de dados auxiliares (ingressos) nos esquemas de dados dos SBDCs, com a
finalidade de forçar conflitos diretos entre STs.
SESAMO – F.Stefan Trabalhos Correlatos - 118 -
Tabela 9 – Controladores de concorrência: infra-estrutura de gerenciamento de transações globais
Tipo da
transação
Gerenciador
da transação
Local de
controle da
transação
Suporte à
migração e
desconexão
Permite
efetivação
parcial e
antecipada
Suporte ao
Gerencia-
mento da
Recuperação
Preserva de
forma
integral a
autonomia
dos SBDs-
participantes
Global (KT)
Agente de
acesso aos
dados
ESMs
visitadas
pelo CM-
originador
Só
migração,
via criação
de uma JT p/
cada
migração
Sim, através
de diferentes
JTs
Somente
registra
ocorrências
Kangaroo
Desdobrável
(JT)
Agente de
acesso aos
dados
ESM que
criou a JT
- Não
Somente
registra
ocorrências
Sim
Global
Agente-de-
Compactos
CM-
originador
Somente
desconexão
Dependente
da transação
Sim
Pro-motion
Desdobrável
Gerenciador
-de-
Compactos
SBDs-
participantes
- Sim Sim
Não, pois
usa EBF ou
impõe um
CC externo
GTG
ESMs
visitadas
pelo CM-
originador
PSTM Global
Gerenciador
de
Subtransa-
ções
Servidores
fixos de
SBDs
Sim Sim
Não
investiga
Não, pois
força
conflitos de
STs nos
SGBDs-
participantes
V-lock Global
Coordena-
dor de TGs
Nó MSE
que contém
os esquemas
de dados
destino
Somente
desconexão
Não
Não
investiga
Não, pois
exige o uso
do protocolo
EBF
GTM
CM-
coordenador
Agente-
Tradutor
CM-
coordenador
Não
investiga
Não
Não
investiga
Não, pois
exige uso de
protocolo de
efetivação
atômica
SESAMO
CM-
originador
GTG
CM-
originador
Não
investiga
Sim
Não
investiga
Sim
5.6.4 Análise adicional
Nesta Subseção, serão apresentados os aspectos mais relevantes detectados na análise
dos GTs comparados. As seguintes características estão presentes:
Distribuição total do gerenciamento de transações. Esta característica indica se o
mecanismo analisado possibilita que o gerenciamento de TGs seja realizado em
todos os nós da rede;
SESAMO – F.Stefan Trabalhos Correlatos - 119 -
Garantia de consistência dos dados primários e replicados. Esta característica
somente terá sentido para aqueles GTs em que são usadas técnicas de replicação
e/ou de fragmentação, visando aumentar a disponibilidade dos dados;
Preservação integral da autonomia dos SBDs-participantes. A autonomia, nesse
contexto, refere-se aos aspectos locais de gerenciamento dos dados e seus
esquemas, como também o gerenciamento de transações; e
Quantidade total de mensagens trafegadas durante uma sessão de trabalho S, que
ocorre num intervalo de tempo T.
A quantidade total de mensagens acima referida baseia-se nas seguintes premissas:
Durante o processamento das TGs consideradas, não ocorrem momentos de
desconexão e nem de migração dos computadores da rede;
Todas as TGs e suas STs são executadas com sucesso;
Não ocorrem falhas de comunicação ou falhas nos sistemas computacionais
envolvidos nos processamentos das TGs e das STs;
Desconsideram-se as mensagens trafegadas para fins de localização dos nós da rede
que gerenciam as TGs e dos nós onde residem os SBDs-participantes de cada TG;
O símbolo qmt representa a quantidade de TGs ocorridas durante a sessão S;
O símbolo qmSpt indica a quantidade média de STs por cada TG executada.
Considera-se que os dados requeridos por cada ST não estão nem no nó da rede de
onde se originou a TG e nem no nó da rede que inicia o processamento da TG;
O símbolo qmOps indica a quantidade média de operações em cada ST. Estamos
considerando que o conteúdo de cada operação ocupa apenas uma mensagem;
O símbolo TmG representa a quantidade necessária de mensagens trafegadas para
efeito de início do processamento de todas as TGs solicitadas durante a sessão de
trabalho S;
O símbolo TmS representa a quantidade necessária de mensagens trafegadas para
efeito de início do processamento das STs de todas as TGs solicitadas durante a
sessão S;
SESAMO – F.Stefan Trabalhos Correlatos - 120 -
O símbolo TmO representa a quantidade necessária de mensagens trafegadas para
efeito de execução das operações de todas TGs da sessão S;
A quantidade total de mensagens trafegadas na sessão S é o resultado da expressão
TmG + TmS + TmO.
Tabela 10 – Controladores de concorrência: resumo da análise
Distribuição
integral do
GT
Garantia de
consistência nas
fontes de dados
primárias e
secundárias
Preservação
integral da
autonomia dos
SBDCs
Qtd de mensagens trafegadas na rede
durante sessão S
Kangaroo Não Não Sim
TmG = qmt
TmS = qmt*qmSpt
TmO = 4*qmt*qmSpt*qmOps
Pro-motion Sim Sim Não
TmG = 0
TmS = qmt*qmSpt
TmO = 4*qmt*qmSpt*qmOps
PSTM Não Sim Não
TmG = qmt
TmS = qmt*qmSpt
TmO = 4*qmt*qmSpt*qmOps
V-lock Não Sim Não
TmG = 2*qmt
TmS = qmt*qmSpt
TmO = 6*qmt*qmSpt*qmOps
GTM Não Sim Não
TmG = qmt
TmS = qmt*qmSpt
TmO = 4*qmt*qmSpt*qmOps
SESAMO Sim Sim Sim
TmG = 0
TmS = qmt*qmSpt
TmO = 4*qmt*qmSpt*qmOps
A partir da Tabela 10, podem ser obtidas as seguintes constatações:
O SESAMO e o Pro-motion são os únicos que permitem a distribuição total do
gerenciamento de transações, obtendo, conseqüentemente TmG igual a zero. O
Kangaroo, o PSTM e o GTM apresentam TmG = qmt, devido às suas arquiteturas
serem cliente-servidor, em que a transação é iniciada de fato nas ESMs. O V-lock
tem TmG = 2*qmt, devido à necessidade de uma terceira unidade computacional
para efeito de início efetivo de cada TG;
Em todos os mecanismos analisados, o valor de TmS é o mesmo, ou seja,
qmt*qmSpt. Isto significa que, para cada ST a ser iniciada, uma mensagem é
enviada do coordenador da TG até o SBD destinatário das operações da ST;
SESAMO – F.Stefan Trabalhos Correlatos - 121 -
Em todos os mecanismos analisados, à exceção do V-lock, o valor de TmO é o
mesmo, ou seja, 4*qmt*qmSpt*qmOps. Esse valor significa que para cada operação
ser executada e ter seus resultados entregues ao CM-originador, quatro mensagens
são necessárias. Duas dessas mensagens ocorrem na ida da operação até o SBD-
destinatário, ou seja, do CM para a ESM e da ESM para o SBD. As outras duas
mensagens fazem o caminho inverso. No V-lock duas mensagens são adicionadas,
devido à inclusão de mais uma unidade computacional no caminho das mensagens
entre o CM originador da transação e o SBD-destinatário. Tal unidade é o
Coordenador da TG, dinamicamente escolhido para cada TG originada;
O Kangaroo apresenta a desvantagem de não garantir a consistência global dos
dados acessados;
O Pro-motion, o PSTM, o V-lock e o GTM apresentam a desvantagem de violarem
de alguma forma a autonomia dos SBDs-participantes; e
Assim, dos mecanismos aqui analisados, o SESAMO é o único que atende a todos
os requisitos desejáveis, além de apresentar, juntamente com o Pro-motion, a menor
quantidade de mensagens trafegadas durante a sessão de trabalho S.
5.7. Resumo do capítulo
Neste capítulo, foram analisados trabalhos correlatos ao SESAMO, com ênfase nas
seguintes propriedades essenciais para o gerenciamento de transações em um SBDM com
suporte à mobilidade: garantia de consistência dos dados dos SBDs-componentes;
preservação da autonomia funcional dos SBDs-componentes; e gerenciamento distribuído e
descentralizado de transações globais. A partir da comparação dos trabalhos correlatos com o
SESAMO, chegou-se à constatação de que nenhum deles, além do SESAMO, proporciona
todas as citadas propriedades. Tal constatação já é uma evidência da contribuição que o
SESAMO proporciona para a área de gerenciamento de transações em SBDMs com suporte à
mobilidade. No Capítulo 6, será descrito o processo de avaliação experimental do SESAMO,
com o objetivo de apresentar a seguinte evidência adicional da contribuição do SESAMO: o
ganho no grau de concorrência que o SESAMO pode proporcionar em relação ao critério de
correção usado nos trabalhos correlatos, ou seja, a Serialidade.
- 122 -
CAPÍTULO VI
Avaliação Experimental
- 123 -
6. Avaliação Experimental
Neste capítulo, serão descritos os recursos usados para avaliar o desempenho do
algoritmo do CC proposto pelo SESAMO, ao qual nos referiremos por protocolo SESAMO,
ou simplesmente SESAMO, comparando-o com o desempenho de um algoritmo baseado nas
regras do protocolo BBF-preciso, deste ponto em diante referido apenas por protocolo BBP,
ou simplesmente BBP. Em seguida, são apresentados os resultados obtidos e a análise
correspondente.
6.1. Simulador
O desempenho do SESAMO foi avaliado por meio de um simulador desenvolvido em
Java (versão j2sdk1.4.2), cujas especificações do projeto lógico estão descritas no Anexo I
desta dissertação. O simulador foi estendido para efeito de avaliação do BBP, possibilitando,
assim, a comparação do desempenho dos protocolos citados.
A seguir, são descritos os critérios de desempenho, o ambiente computacional, os
algoritmos, os parâmetros e os procedimentos usados nas simulações.
6.1.1 Critérios de desempenho
O simulador mede o desempenho de cada protocolo em termos de:
Vazão (throughput), medida em termos de quantidade de TGs efetivadas por
segundo.
Eficiência, medida em termos de percentual de TGs efetivadas em relação ao total
de TGs iniciadas dentro do intervalo de tempo utilizado para simular a operação dos
protocolos.
6.1.2 Ambiente computacional
A execução das simulações foi realizada em um ambiente computacional cujas
características estão descritas na Tabela 11.
SESAMO – F.Stefan Avaliação experimental - 124 -
Tabela 11 – Ambiente computacional usado na simulação do SESAMO
Característica Especificação
Sistema operacional Microsoft Windows XP Professional – 2002 – SP 2
Unidade central de processamento (CPU) Intel(R) Pentium(R) 4 CPU 1.8 GHz
Memória RAM 256 MB
Ambiente de execução Java JRE 1.4.2-b28
6.1.3 Protocolo SESAMO
No SESAMO, cada TG gera um MS (Definição 14) para cada US (Definição 13)
acessada por ela. Cada MS gera uma ST para cada BD acessado por ele. Para efeito de
simplificação do simulador, foi considerado que cada US corresponde a um BD, de forma que
cada MS somente gera uma única ST.
Cada operação de uma TG é associada a uma ST, de acordo com o BD por ela
referenciado. Qualquer ST poderá ser efetivada antecipadamente desde que ela tenha
executado todas as suas operações e tenha sido submetida pela TG uma operação denominada
encerrarBD, indicando como parâmetro o BD ao qual aquela ST está relacionada. A
efetivação antecipada de uma ST faz com que todos os bloqueios (sobre itens de dados)
retidos por ela sejam liberados, ficando esses itens de dados disponíveis para serem acessados
por STs geradas por outras TGs concorrentes. As demais STs serão efetivadas somente após o
GTG receber a operação de efetivação da TG e todas as operações desta já tiverem sido
executadas.
Na implementação do SESAMO, o processamento ocorre, resumidamente, da seguinte
forma: há dois processos que funcionam simultaneamente (threads), um que coleta operações
a sincronizar (o qual chamaremos Sincronizador) e o outro (o qual chamaremos de Executor)
que submete operações aos SBDCs do SBDM considerado. Os significados dos acrônimos
FOAS, FOJS e FOSA, a seguir mencionados, bem como das funções correspondentes estão
definidos na Seção 4.4. Os parâmetros P5 e P7, abaixo mencionados, estão descritos na
Tabela 12. A seguir, estão descritos os passos dos dois processos citados.
Sincronizador (vide diagrama correspondente na Figura 9)
1-A cada intervalo de tempo T definido pelo parâmetro P7, verificar se existe na FOAS
uma operação a ser processada, oriunda de uma TG. Caso não exista operação ou se T for
SESAMO – F.Stefan Avaliação experimental - 125 -
igual ou superior ao intervalo de tempo definido pela fórmula P7*NTGA (acrônimo que
corresponde ao Número de TGs Ativas em um dado momento), então executar o passo 6.
Caso contrário, então executar o passo 2. Durante a operação do SESAMO, o NTGA pode
variar de 0 ao limite definido pelo parâmetro P5.
Figura 9 - SESAMO: processo sincronizador
2-Se a operação for INICIAR, acrescentar o valor 1 ao NTGA e retornar. Se a operação
for EFETIVAR, executar o passo 3 e retornar. Executar o passo 8. Se a TG estiver no estado
“em espera”, executar o passo 7 e retornar. Se a operação for ENCERRARBD, executar o
passo 4 e retornar. Nos demais casos, ou seja, leitura ou escrita, executar o passo 5 e retornar.
Obs: neste simulador, não foi considerada a ocorrência de operações de aborto.
3-Marcar a TG como “em efetivação”. Para cada ST gerada pela TG em questão e cuja
situação não seja “em efetivação”, executar o passo 4. Retornar.
4-Marcar como “em efetivação” a ST relativa ao BD referenciado, criar a operação
EFET_SUB (efetivar subtransação), associá-la à ST em questão, marcá-la como “em
execução”, inseri-la no FOJS e retornar.
SESAMO – F.Stefan Avaliação experimental - 126 -
5-Tentar obter o bloqueio sobre o item de dado referenciado pela operação. Caso o
bloqueio seja obtido, remover a operação da FOAS, marcá-la como “em execução”, inseri-la
na FOJS e retornar. Caso contrário, marcar a TG como “em espera”, executar o passo 7 e
retornar.
6-Verificar se existe alguma operação na FOSA. Se existir, tentar obter o bloqueio sobre
o item de dado referenciado pela operação. Caso o bloqueio seja obtido, remover a operação
da FOSA e inseri-la na FOJS, mudar a situação da TG para “em execução” e retornar. Caso
contrário, retornar.
7- Remover a operação da FOAS, inseri-la na FOSA e retornar.
8-Associar a operação a uma ST (de acordo com o BD referenciado) e acrescentar o
valor 1 ao contador de operações associadas a essa ST.
Executor (vide diagrama correspondente na Figura 10)
1-Verificar continuamente, para cada operação da FOJS, a sua situação. Se a situação
for “em execução” então executar passo 2a, passar para a próxima operação da FOJS e
retornar ao início do passo 1. Se a situação for “submetida”, passar para a próxima operação
da FOJS e retornar ao início do passo 1. Se a situação for “executada”, então executar passo
3, remover a operação da FOJS, passar para próxima operação da FOJS e retornar ao início do
passo 1. Obs: a situação da operação será modificada de “submetida” para “executada” pelo
componente ISBDM, no momento em que este recebe dos SBDCs a confirmação das
operações a eles submetidas.
2a-Se a operação for “EFET_SUB”, então: Se todas as operações da ST em questão já
tiverem sido executadas, então submeter a operação ao devido SBDC, mudar a situação para
“submetida” e retornar. Caso contrário, apenas retornar. Se a operação for de leitura ou
escrita, então submetê-la ao devido SBDC, mudar sua situação para “submetida” e retornar.
2b-Se a operação for “EFET_SUB”, então: Se todas as operações da TG em questão já
tiverem sido executadas, então submeter a operação ao devido SBDC, mudar a situação para
“submetida” e retornar. Caso contrário, apenas retornar. Se a operação for de leitura ou
escrita, então submetê-la ao devido SBDC, mudar sua situação para “submetida” e retornar.
SESAMO – F.Stefan Avaliação experimental - 127 -
Figura 10 - SESAMO: processo executor
3-Se a operação for “EFET_SUB”, então executar passo 4a e retornar. Caso contrário,
acrescentar o valor 1 ao contador de operações executadas da ST em questão e retornar.
4a-Liberar os bloqueios retidos pela ST em questão. Acrescentar o valor 1 ao contador
de STs executadas da TG em questão. Se todas as STs dessa TG tiverem sido executadas,
então diminuir 1 do valor de NTGA e retornar. Caso contrário, retornar.
4b-Acrescentar o valor 1 ao contador de STs executadas da TG em questão. Se todas as
STs dessa TG tiverem sido executadas, então liberar os bloqueios retidos por todas as STs da
TG em questão, diminuir 1 do valor de NTGA e retornar. Caso contrário, retornar.
6.1.4 Protocolo BBP
No protocolo BBP, cada TG gera uma ST para cada BD acessado por ela. Cada
operação é associada a uma ST, de acordo com o BD por ela referenciado. As STs serão
efetivadas somente após o GTG receber a operação de efetivação da TG e todas as operações
desta TG já tiverem sido executadas. Dessa forma, o protocolo BBP retém todos os bloqueios
obtidos por uma TG até que todas as operações dessa TG sejam executadas, ou seja, não
poderá ocorrer a efetivação antecipada de uma ST, em relação à TG que a gerou.
SESAMO – F.Stefan Avaliação experimental - 128 -
Em termos de implementação, o BBP segue os mesmos passos vistos na Subseção
6.1.3, com as seguintes diferenças: em vez de executar o passo 2a, executa-se o 2b e, em vez
de executar o passo 4a, executa-se o 4b.
6.1.5 Parâmetros da avaliação
Na Tabela 12, estão apresentados os principais parâmetros usados pelo simulador na
avaliação dos algoritmos do SESAMO e BBF-preciso. Os valores dos parâmetros P5 a P7
foram baseados nas simulações realizadas em [46]. Os valores dos demais parâmetros (P1 a
P4) foram definidos arbitrariamente e fixados com o objetivo de simplificar o processo das
simulações. De forma geral, os parâmetros definidos não comprometem a generalização dos
resultados obtidos, pois ambos os algoritmos foram avaliados sob as mesmas condições.
Nos parâmetros P3 e P4, são mencionadas as operações iniciar e efetivar. A primeira
sinaliza para o GTG (gerenciador de transações globais) do simulador que deve ser iniciada
uma nova TG. A segunda operação indica que a TG deve ser efetivada.
Tabela 12 – Parâmetros usados na simulação de desempenho do SESAMO
Id Parâmetro Valor padrão
P1 Este parâmetro indica o nome e a composição dos BDs que
participam da simulação. Cada BD foi definido com apenas 300
itens, no sentido de se testar os algoritmos sob efeito de gargalos de
processamento (hot spots).
bd1 = { x
1
, x
2
, ... , x
300
}
bd2 = { p
1
, p
2
, ..., p
300
}
P2 Unidades semânticas. Tal informação somente tem significado para
o SESAMO.
us1 = { bd1 }
us2 = { bd2 }
P3 TG padrão usada na simulação do protocolo BBP. O uso de uma TG
padrão visou apenas diminuir a quantidade de variáveis que
influenciariam nas simulações. Obs: x
i
e x
j
são itens de bd1
aleatoriamente selecionados, para cada TG iniciada. Da mesma
forma, p
k
e p
w
são selecionados a partir de bd2.
É formada pela seguinte seqüência:
iniciar, ler(x
i
), gravar(x
j
),
ler(p
k
), gravar(p
w
), efetivar
P4 TG padrão para o protocolo SESAMO. Trata-se da mesma TG
padrão usada para simular o BBF-preciso, acrescida da operação
encerrarBD, a qual foi incluída entre a terceira e quarta operações da
TG padrão.
É formada pela seguinte seqüência:
iniciar, ler(x
i
), gravar(x
j
),
encerrarBD(bd1),
ler(p
k
), gravar(p
w
), efetivar
P5 Número de TGs ativas. Em qualquer momento da simulação,
sempre haverá esta quantidade de TGs ativas. Este número
representa o nível global de multi-programação.
Para cada simulação, foi fixado um
número entre 10 e 100.
P6 Tempo de resposta que um SGBD remoto leva para processar e
confirmar a execução de uma operação qualquer (leitura, escrita,
efetivação ou aborto). Foi considerada uma conexão sem fio estável.
400 ms
P7 Freqüência com que o GTG coleta operações (oriundas de TGs) da
fila de operações a sincronizar (FOAS). Tais operações se originam
de dispositivos computacionais clientes do GTG. As TGs inserem de
forma intercalada suas operações na FOAS.
Uma operação a cada 15 ms
SESAMO – F.Stefan Avaliação experimental - 129 -
6.1.6 Procedimentos
A realização das simulações consistiu dos seguintes procedimentos:
Para cada número TGs ativas selecionado, foram realizadas cinco iterações do
processo de simulação, sendo que cada iteração teve a duração de 5 segundos. Tal
intervalo foi escolhido arbitrariamente, com base nas simulações definidas em [46].
Ao final das cinco iterações, foram calculadas as médias aritméticas dos dados
medidos, ou seja: número de transações iniciadas e número de transações
efetivadas.
6.2. Resultados obtidos
Nesta seção, são apresentados os resultados obtidos a partir das simulações realizadas.
São apresentados os gráficos que representam o desempenho dos dois protocolos simulados,
em termos de eficiência e vazão.
6.2.1 Eficiência
Conforme pode ser visto na Figura 11, o BBP superou o SESAMO apenas nas
simulações em que foi usado um número de transações ativas menor que 20. A partir de
números maiores, o SESAMO superou bastante a eficiência do BBF-preciso. A título de
exemplo, para o número de 60 TGs ativas, a eficiência do SESAMO ficou em torno de 40%,
enquanto no BBP a eficiência ficou em torno de 7%. Com 80 TGs ativas, a eficiência do BBP
foi a zero, enquanto, no SESAMO, a eficiência ficou em torno de 33%.
Em ambos os protocolos, quando o número de TGs ativas foi de 25, ocorreu um ponto
de inflexão no gráfico que representa a variação da eficiência em função do número de TGs
ativas. Tal comportamento é resultado da ocorrência crescente dos bloqueios cíclicos, os quais
reduzem progressivamente a eficiência dos protocolos.
SESAMO – F.Stefan Avaliação experimental - 130 -
Eficiência
0%
20%
40%
60%
10 20 30 40 50 60 70 80 90 10
0
Número de TGs ativas
Efetivação de TGs
iniciadas
SESAMO
BBF-preciso
Figura 11 - SESAMO: avaliação da eficiência
6.2.2 Vazão
Conforme pode ser visto na Figura 12, a vazão do BBP superou discretamente a do
SESAMO para um número de TGs ativas baixo, ou seja, menor que 20. A partir desse ponto,
o SESAMO superou bastante a vazão do BBP, chegando a uma diferença de 5,8 TGs
efetivadas/seg quando o número de TGs ativas foi de 60. Com 80 TGs ativas, a vazão do
BBF-preciso passou a ser zero, permanecendo assim para números maiores de TGs ativas.
Com 80 TGs ativas, a vazão do SESAMO foi de 6 TGs efetivadas/seg, tendo ficado com um
valor ainda razoável (em torno de 3,5 TGs efetivadas/seg) para o número de 100 TGs ativas.
Os gráficos de vazão apresentaram pontos de inflexão de forma similar ao que ocorreu
nos gráficos de eficiência. A causa também foi a ocorrência crescente dos bloqueios cíclicos.
Vazão
0,00
1,00
2,00
3,00
4,00
5,00
6,00
7,00
10 20 30 40 50 60 70 80 90 100
Número de TGs ativas
TGs efetivadas / seg.
SESAMO
BBF-preciso
Figura 12 – SESAMO: avaliação da vazão
SESAMO – F.Stefan Avaliação experimental - 131 -
6.3. Discussão
Conforme os resultados apresentados na Seção 6.2, o protocolo SESAMO foi superior
ao BBP, tanto na eficiência quanto na vazão, em mais de 70% das simulações realizadas.
Além disso, a taxa de declínio dos valores da eficiência e vazão do SESAMO em relação à do
BBP demonstra que o SESAMO é bem mais escalável no que se refere ao aumento do
número de TGs ativas.
Tais resultados são uma evidência de que a abordagem proposta pelo SESAMO para o
controle de concorrência distribuído de TGs em SBDMs com suporte à mobilidade pode
proporcionar um melhor grau de concorrência do que as abordagens que utilizam a
Serialidade como critério de controle de concorrência.
- 132 -
CAPÍTULO VII
CONCLUSÃO
- 133 -
7. Conclusão
Nesta seção, são apresentadas uma síntese do trabalho, as contribuições obtidas e as
perspectivas futuras de desenvolvimento do trabalho.
7.1. Síntese da proposta
Nesta dissertação, foi proposto o SESAMO, que é um controlador de concorrência para
SBDMs que oferecem suporte à computação móvel. No Capítulo 1, apresentou-se a
motivação para o desenvolvimento deste trabalho, bem como os seus objetivos e premissas.
No Capítulo 4, foram apresentadas as principais características do SESAMO, quais sejam: (i)
implementa a Serialidade Semântica, resultando na preservação da consistência e da
autonomia dos SBDCs (SBDs-componentes); (ii) distribui o gerenciamento de transações
globais, reduzindo a quantidade de mensagens na rede, característica desejável na computação
móvel; (iii) e implementa uma forma de flexibilização da propriedade de isolamento das
transações globais. No Capítulo 5, a partir de uma análise comparativa, mostrou-se que, à
exceção do SESAMO, todos os trabalhos correlatos violam ou a consistência ou a autonomia
dos SBDCs de um SBDM qualquer considerado. Por fim, no Capítulo 6, a partir de uma
avaliação experimental, foram apresentados os ganhos de vazão de processamento e eficiência
que o SESAMO pode proporcionar em relação a um controlador de concorrência baseado no
protocolo padrão de mercado (BBF-preciso), no que se refere ao controle de concorrência
distribuído de transações globais em um SBDM.
7.2. Contribuições
Nesta dissertação, identificamos as seguintes contribuições científicas para a área de
gerenciamento de transações em sistemas de bancos de dados múltiplos com suporte à
mobilidade:
7.2.1 Descentralização do controle de concorrência usando a SSE
A principal contribuição desta dissertação foi identificar que as características do
modelo de transação da Serialidade Semântica possibilitam que o controle de concorrência de
SESAMO – F.Stefan Conclusão - 134 -
TGs em SBDMs com suporte à mobilidade seja realizado de forma distribuída e
descentralizada, assegurando a consistência dos dados dos SBDs-componentes, mas sem
violar a autonomia funcional destes.
7.2.2 Projeto de uma estratégia distribuída de controle de concorrência
Foi definida uma estratégia de controle de concorrência (chamada de SESAMO) para
SBDMs com suporte à mobilidade, baseada na constatação identificada na Subseção 7.2.1.
Além disso, foi definido um protocolo de controle de concorrência específico para a referida
estratégia.
7.2.3 Flexibilização da propriedade de isolamento
Foi definida e implementada uma forma de flexibilizar a propriedade de isolamento de
transações globais, mediante a exploração das características da Serialidade Semântica. Foi
mostrado que, nas transações globais que representam a execução de dois ou mais módulos
semânticos, cada conjunto de STs que pertencem a um mesmo módulo semântico pode ser
efetivado de forma antecipada e independente do sucesso dos outros módulos, sem
comprometer a consistência global dos bancos de dados que integram o SBDM. É provável
que essa funcionalidade tenha sido o fator que proporcionou a superioridade do SESAMO, em
relação ao protocolo baseado no BBF-preciso, quanto ao grau de concorrência obtido nas
simulações.
7.2.4 Simulação dos ganhos potenciais no grau de concorrência
A partir de simulações realizadas por meio de um aplicativo construído para comparar o
desempenho do SESAMO em relação ao um protocolo baseado nas regras do BBF-preciso,
foram apresentados resultados que evidenciam o ganho no grau de concorrência que o uso do
SESAMO pode proporcionar, em relação ao uso de outras estratégias que usam a Serialidade
como critério de controle de concorrência.
SESAMO – F.Stefan Conclusão - 135 -
7.2.5 Adequabilidade ao ambiente de computação móvel
A proposta SESAMO proporciona o alcance das seguintes características desejáveis
para o ambiente de computação móvel, sob a perspectiva do gerenciamento de transações em
SBDMs: (i) Gerenciamento descentralizado de TGs; (ii) Vazão otimizada; e (iii) Garantia de
consistência dos dados e preservação da autonomia dos SBDs-componentes. Como
conseqüência da descentralização do gerenciamento de TGs, o tráfego global de mensagens
na rede tende a reduzir, em relação a soluções que centralizam essa atividade. Em decorrência
das referidas propriedades, o SESAMO torna-se vantajoso para o ambiente de computação
móvel.
7.3. Trabalhos futuros
Os seguintes trabalhos futuros poderão ser desenvolvidos, como aprimoramento do
presente trabalho.
Investigar e desenvolver um Gerenciador de Recuperação para as transações globais
controladas pelo CC SESAMO.
Investigar métodos de tratamento dos problemas que a atividade de gerenciamento
de transações globais em SBDMs pode ter, tendo como causa fatores característicos
do ambiente de computação móvel, tais como: instabilidade, lentidão ou não
disponibilidade da rede de comunicação sem fio; e mobilidade dos dispositivos
computacionais.
- 136 -
Anexo I – Projeto Lógico do Simulador
I.1. Diagrama de Casos de Uso
Na Figura 13 abaixo, está representado o diagrama de casos de uso do Simulador
construído para avaliar o desempenho do protocolo proposto (o SESAMO) para realizar o
processamento de TGs (transações globais). Nas próximas sessões estão descritas as regras de
negócio e os algoritmos de cada um dos casos de uso abaixo representados.
Figura 13 - SESAMO: Diagrama de Casos de Uso
I.2. Regras de Negócio
[RN1] Uma TG está ativa caso já tenha sido iniciada pelo GTG e não tenha sido
abortada, nem efetivada e nem esteja suspensa.
[RN2] Um banco de dados é valido quando estiver registrado no catálogo global de
dados do SBDM que estiver sendo acessado pelo GTG.
SESAMO – F.Stefan Anexo I - 137 -
[RN3] Uma tabela é válida quando o banco de dados ao qual ela está associada for
válido e se ela estiver registrada no catálogo global de dados no SBDM que estiver
sendo acessado pelo GTG.
[RN4] Uma operação sobre um item de dados (leitura, atualização, inclusão ou
exclusão) somente será recebida pelo GTG caso atenda aos seguintes requisitos:
esteja associada a uma TG ativa (vide RN1); esteja associada a um banco de dados
válido (RN2); esteja associada a uma tabela válida (RN3).
[RN5] Uma operação de efetivar TG ou de abortar TG somente será recebida pelo
GTG caso esteja associada a uma TG ativa (RN1).
[RN6] Uma operação encerrarBD somente será recebida pelo GTG caso atenda aos
seguintes requisitos: esteja associada a uma TG ativa (RN1); esteja associada a um
banco de dados válido (RN2); a TG informada ainda não tenha encerrado suas
operações sobre o BD informado.
[RN7] Uma ST está ativa caso já tenha sido iniciada pelo GTG e não tenha sido
abortada e nem efetivada.
[RN8] Uma operação de leitura ou gravação somente será executada em um SBD
remoto caso esteja associada a uma ST ativa (RN7).
[RN9] Uma operação de efetivar (ou abortar) uma ST somente será executada, em
um SBD remoto, caso esteja associada a uma ST ativa (RN7).
I.3. Algoritmos dos Casos de Uso
CSU-01 - Iniciar TG
Sumário: O GC requisita ao GTG o início de uma nova TG.
1-O GC requisita ao GTG o início de uma nova TG.
2-O GTG cria uma nova TG, devolvendo ao GC uma mensagem contendo a
identificação interna da TG.
CSU-02 - Executar operação de TG
Sumário: O GC requisita ao GTG a execução de uma operação sobre um item de dado.
1-O GC requisita ao GTG o início de uma nova operação, informando os seguintes
dados: identificação da TG associada, banco de dados alvo, tabela alvo do banco de
SESAMO – F.Stefan Anexo I - 138 -
dados, chave primária do item de dado alvo, tipo de operação (leitura, atualização,
inclusão ou exclusão), cláusula SQL a ser executada no item de dado alvo.
2-O GTG verifica a regra de negócio RN4 está sendo atendida. Se não estiver, executa
caso de uso CSU-05.A e retorna mensagem de aborto.
3-O GTG executa a operação, através do caso de uso CSU-10.
4-O GTG devolve ao GC a mensagem recebida do CSU-10.
CSU-03 – Encerrar operações sobre BD
Sumário: O GC informa ao GTG que uma determinada TG não mais enviará operações
sobre um determinado BD.
1-O GC requisita ao GTG o encerramento de operações sobre um BD, informando os
seguintes dados: identificação da TG associada e banco de dados alvo.
2-O GTG verifica se a regra de negócio RN6 foi atendida. Se não estiver, executa caso
de uso CSU-05.A e retorna mensagem de aborto.
3-O GTG identifica o MS correspondente à operação.
4-O GTG verifica se todos os BDs que fazem parte da US correspondente ao MS em
questão já foram encerrados.
4.1.Caso afirmativo, então executar os seguintes passos:
a)Executar caso de uso CSU-11.
b)Retornar ao GC a mensagem recebida do CSU-11.
4.2.Caso negativo, retorna ao GC uma mensagem de confirmação.
CSU-04 – Efetivar TG
Sumário: O GC requisita ao GTG a efetivação de uma determinada TG.
1-O GC requisita ao GTG a efetivação de uma TG, informando os seguintes dados:
identificação da TG associada.
2-O GTG verifica se a regra de negócio RN5 está sendo atendida. Se não estiver,
executa caso de uso CSU-05.A e retorna mensagem de aborto.
3-Para cada MS associado à TG informada, o GTG executa os seguintes passos:
3.1.Executar caso de uso interno CSU-11.
3.2.Se mensagem retornada de CSU-11 for “confirmação”, então processar próximo
MS, voltando para o passo 3. Caso contrário, retornar mensagem de aborto e
terminar caso de uso.
4-O GTG devolve ao GC uma mensagem de confirmação.
CSU-05 – Abortar TG – via GC
Sumário: O GC requisita ao GTG o aborto de uma determinada TG.
1-O GC requisita ao GTG o aborto de uma TG, informando os seguintes dados:
identificação da TG associada.
2-O GTG executa a operação, através de um caso de uso interno (CSU-05.A).
3-O GTG devolve ao GC a mensagem recebida de CSU-05.A.
CSU-05.A – Abortar TG – geral
SESAMO – F.Stefan Anexo I - 139 -
Sumário: O GTG aborta uma determinada TG.
1-Alterar estado da TG para “abortada”.
2-Para cada uma das STs associadas à TG em questão, executar os seguintes passos:
2.1.Executar caso de uso CSU-09.
3-Retornar uma mensagem de confirmação.
CSU-06 - Iniciar SG
Sumário: O GTG requisita a um SBD remoto o início de uma nova transação local e
cria uma ST correspondente.
1-O GTG requisita a um certo SBD remoto o início de uma transação local neste SBD
remoto.
2-O SBD remoto responde com uma mensagem de confirmação.
3-O GTG estabelece uma conexão entre a referida TG e o referido SBD remoto e cria
uma ST que corresponde àquela transação local.
CSU-07 - Executar operação de SG
Sumário: O GTG requisita a um SBD remoto a execução de uma operação sobre um
item de dado.
1-O GTG verifica se a regra de negócio RN8 está sendo atendida. Se não estiver,
executa caso de uso CSU-05.A e retorna mensagem de aborto.
2-O GTG requisita a um certo SBD remoto, através da conexão associada a uma ST, a
execução de uma nova operação, informando os seguintes dados: tabela alvo do
banco de dados, chave primária do item de dado alvo, tipo de operação (leitura,
atualização, inclusão ou exclusão), cláusula SQL a ser executada no item de dado
alvo.
3-O SBD remoto devolve ao GTG uma das seguintes mensagens: confirmação (se a
operação tiver sido uma atualização, inclusão ou exclusão); uma tupla com o
resultado (se a operação tiver sido uma leitura); ou aborto (informando que a ST foi
abortada).
4-Retornar mensagem recebida do SBD remoto.
CSU-08 – Efetivar SG
Sumário: O GTG requisita a um SBD remoto a efetivação de uma transação local
correspondente a um ST ativa do GTG.
1-O GTG verifica se a regra de negócio RN9 está sendo atendida. Se não estiver,
executa caso de uso CSU-05.A e retorna mensagem de aborto.
2-O GTG requisita a um certo SBD remoto, através da conexão associada a uma ST, a
efetivação da transação local correspondente do SBD remoto.
3-O SBD remoto devolve ao GTG uma das seguintes mensagens: confirmação (se a
operação tiver sido bem sucedida); ou aborto (informando que a transação local
correspondente do SBD remoto foi abortada).
SESAMO – F.Stefan Anexo I - 140 -
4-Retornar mensagem recebida do SBD remoto.
CSU-09 – Abortar subtransação
Sumário: O GTG requisita a um SBD remoto o aborto de uma transação local
correspondente a uma ST ativa do GTG.
1-O GTG verifica se a regra de negócio RN9 está sendo atendida. Se não estiver,
executa caso de uso CSU-05.A e retorna mensagem de aborto.
2-O GTG requisita a um certo SBD remoto, através da conexão associada a uma ST, o
aborto da transação local correspondente do SBD remoto.
3-O SBD remoto devolve ao GTG uma mensagem de confirmação do aborto da
transação local correspondente.
4-Retornar mensagem recebida do SBD remoto.
CSU-10 – Controlar execução da operação
Sumário: A operação é associada a um MS e a uma ST, obtém bloqueio ao item de dado
alvo e é enviada para execução no respectivo SBD remoto.
1-Uma nova operação é recebida, via caso de uso CSU-02.
2-Associar operação a um MS e a uma ST, via caso de uso CSU-10.A.
3-Verificar se já existe algum bloqueio, sobre o item de dado informado, que conflite
com o bloqueio necessário para a operação.
3.1.Se existir um ou mais bloqueios conflitantes, então aguardar que eles sejam
liberados. Quando não houver mais nenhum bloqueio conflitante sobre o item de
dado alvo da operação, prosseguir o processamento no passo 4.
4-A operação fica aguardando a concessão de um bloqueio sobre o item de dado alvo,
via caso de uso CSU-10.B. Ao obter o bloqueio, o processamento prossegue no passo
5
adiante.
5-Enviar operação para o SBD remoto, via caso de uso CSU-07.
6-Verificar a mensagem retornada por CSU-07:
6.1.Se for “aborto”, então o GTG atualiza o estado da operação como “abortada” e
aborta a TG que deu origem à ST em questão, via CSU-05.
6.2.Caso contrário, o GTG atualiza o estado da operação como “executada”.
7.Retornar mensagem recebida do CSU-07.
CSU-11 – Efetivar um Módulo Semântico
Sumário: Executa, se possível, a efetivação de todas as STs associadas a um
determinado MS.
1-Verificar se todos os BDs que fazem parte da US correspondente ao MS em questão
já foram encerrados.
1.1.Caso afirmativo, então continuar o processamento no passo 2.
1.2.Caso negativo, retorna para o CSU-03 a mensagem de confirmação.
2-Executar a efetivação de todas as STs associadas ao MS em questão, através de um
protocolo de efetivação atômica, usando o caso de CSU-08.
SESAMO – F.Stefan Anexo I - 141 -
2.1.Se alguma ST tiver sido abortada, então abortar toda a TG, via caso de uso CSU-
05.A e retornar uma mensagem de aborto.
3-Após efetivar todas as STs globais, executar os seguintes passos:
3.1.Atualizar o estado do MS e das STs efetivadas.
3.2.Liberar todos os bloqueios retidos pelas operações associados ao MS que foi
efetivado.
4-Retornar mensagem de confirmação.
CSU-10.A – Associar MS/SUBT
Sumário: O GTG associa a operação a um MS e a uma ST.
1-O GTG verifica se já existe um MS ao qual a operação deverá ser associada.
1.1.Se já existir, associar a operação ao referido MS;
1.2.Se não existir, então executar os seguintes passos:
a)Identificar a US destino da operação, com base no catálogo de dados global, o qual
deverá ter a associação entre BDs e USs;
b)Criar um MS, que corresponde à combinação de uma TG com uma US destino;
c) Associar a operação ao recém-criado MS.
2-O GTG verifica se já existe uma ST à qual a operação deverá ser associada.
2.1.Se já existir, associar a operação à referida ST;
2.2.Se não existir, executar os seguintes passos:
a)Iniciar uma nova ST, via caso de uso CSU-06;
b)Associar a operação à ST recém-criada.
CSU-10.B – Obter bloqueio sobre item de dado
Sumário: O GTG seleciona automaticamente uma operação à qual concede um bloqueio
de acesso a um determinado item de dado.
1-Procurar, dentre todas as operações destinadas ao item de dado em questão e com
estado igual a “em espera”, a operação cuja marca de tempo da respectiva TG seja a
menor.
2-Atualizar o estado do item de dado, registrando informação sobre o tipo de bloqueio
que foi concedido sobre o mesmo.
3-Alterar o estado da operação selecionada de “em espera” para “em execução”.
CSU-12 – Detectar BCG (bloqueio cíclico global)
Sumário: Executa periodicamente um procedimento de verificação, detecção e quebra
de bloqueios cíclicos globais, ou seja, bloqueios cíclicos formados por TGs recebidas pelo
GTG.
1-Construir um grafo de espera global (GEG), tendo como vértices as TGs que
estiverem retendo bloqueios sobre item de dado e as que estiverem na fila de espera
por bloqueios. Cada aresta liga dois vértices, sendo o sentido da aresta indica que a
TG representada pelo vértice de origem está aguardando pela liberação do bloqueio
retido pela TG representada pelo vértice de destino da aresta.
SESAMO – F.Stefan Anexo I - 142 -
2-Calcular os seguintes dados para cada uma das TGs consideradas no GEG:
2.1.Quantidade de operações executadas (qoe);
2.2.Quantidade de operações que aguardam pela liberação de bloqueios retidos por ela
(qor);
3-Classificar, em ordem crescente, as TGs consideradas pelo seguinte critério (qoe-qor).
4-Verificar existência de ciclo no GEG.
5-Se existir ciclo no GEG, então executar os seguintes passos:
5.1.Abortar (via caso de uso CSU-05.A) a próxima TG ativa que tiver o menor valor de
(qoe-qor);
5.2.Retornar ao passo 4.
6-Terminar caso de uso.
- 143 -
Bibliografia e Referências
1. BADRINATH, B. R. & RAMAMRITHAN, Krithi. Semantics-based Concurrency
Control: beyond commutativity. ACM Transactions on Database Systems (TODS), New
York, USA: ACM Press, v. 17, n. 1, March, 1992, p. 163-199. ISSN: 0362-5915
.
2. BARGHOUTI, Naser S. & KAISER, Gail E. Concurrency Control in Advanced Database
Applications. ACM Computing Surveys (CSUR), New York, USA: ACM Press, v. 23, n.
3, 1991, p. 269-317. ISSN: 0360-0300.
3. BERENSON, Hal; BERNSTEIN, Phil; GRAY, Jim; MELTON, Jim; O’NEIL, Elizabeth
J. & O’NEIL, Patrick E. A Critique of ANSI SQL Isolation Levels. Proceedings of the
1995 ACM SIGMOD International Conference on Management of Data, San Jose, USA,
May 22-25, 1995. ISBN:0-89791-731-6. ACM SIGMOD Record, New York, USA: ACM
Press, v. 24, n. 2, June, 1995. ISSN: 0163-5808.
4. BERNSTEIN, Philip A.; HADZILACOS, Vassos & GOODMAN, Nathan. Concurrency
Control and Recovery in Database Systems. Addison-Wesley, 1987. ISBN 0-201-10715-5
5. BERNSTEIN, Philip A.; SHIPMAN, David W.; ROTHNIE Jr., James B. Concurrency
Control in a System for Distributed Databases (SDD-1). ACM Transactions on Database
Systems (TODS), New York, USA: ACM Press, v. 5, n. 1, 1980, p. 18-51. ISSN: 0362-
5915.
6. BRAYNER, Angelo. Lock Downgrading: An Approach to Increase Inter-transaction
Parallelism in Advanced Database Applications. Proceedings of the 12
th
International
Conference of Database and Expert Systems Applications (DEXA2001), Munich,
Germany, September 3-5, 2001. Lecture Notes in Computer Science, Berlin, Germany:
Springer, n. 2113, 2001, p. 330-339. ISBN: 3-540-42527-6.
7. BRAYNER, Angelo & ALENCAR, Frank Stefan. A Semantic-Serializability Based
Fully-Distributed Concurrency Control Mechanism for Mobile Multi-Database
Systems. Proceedings of the 8
th
International Workshop on Mobility in Databases and
Distributed Systems (MDDS'2005), Copenhagen, Denmark, August 22-26, 2005. IEEE
Computer Society, 2005, p. 1085-1089.
SESAMO – F.Stefan Bibliografia e Referências - 144 -
8. BRAYNER, Angelo & M. FILHO, José de Aguiar. Increasing Mobile Transaction
Concurrency in Mobile Database Communities. Proceedings of the V Wireless
Communication Workshop (WCSF03), São Lourenço, MG, Brazil, October 27–30, 2003.
9. BRAYNER, Angelo & M. FILHO, José de Aguiar. Sharing Mobile Databases in
Dynamically Configurable Environments. Proceedings of the 15
th
Conference on
Advanced Information Systems Engineering (CAiSE’03), Klagenfurt/Velden, Austria,
June 16-18, 2003. Lecture Notes in Computer Science, Berlin, Germany: Springer, n.
2681, 2003, p. 724-737. ISBN: 3-540-40442-2.
10. BRAYNER, Angelo & HÄRDER, Theo. Global Semantic Serializability: An Approach to
Increase Concurrency in Multidatabase Systems. Proceedings of the 9
th
International
Conference on Cooperative Information Systems (CoopIS 2001), Trento, Italy, September
5-7, 2001. Lecture Notes in Computer Science, Berlin, Germany: Sprinter-Verlag, n.
2172, 2001, p. 301-315. ISBN: 3-540-42524-1.
11. BRAYNER, Angelo; HÄRDER, Theo & RITTER, Norbert. Semantic Serializability: A
Correctness Criterion for Processing Transactions in Advanced Database Applications.
Data & Knowledge Engineering (DKE), Amsterdam, Netherlands: Elsevier, v. 31, n. 1,
1999, p. 1-24. ISSN: 0169-023X.
12. BREITBART, Yuri; GARCIA-MOLINA, Hector & SILBERSCHATZ, Abraham.
Overview of Multidatabase Transaction Management. The VLDB Journal, Heidelberg,
Germany: Springer-Verlag, v. 1, n. 2, 1992, p. 181-239. ISSN: 1066-8888.
13. BREITBART, Yuri; GEORGAKOPOULOS, Dimitrios; RUSINKIEWICZ, Marek &
SILBERSCHATZ, Abraham. On rigorous transaction scheduling
.
IEEE Transactions on
Software Engineering (TSE), Los Alamitos, USA: IEEE Computer Society, v. 17, n. 9,
1991, p. 954-960. ISSN 0098-5589.
14. BREITBART, Yuri & TIEMAN, Larry R. ADDS - Heterogeneous Distributed Database
System. Proceedings of the 3
rd
International Seminar on Distributed Data Sharing Systems
(DDSS), Parma, Italy, March 28-30, 1984. North-Holland, 1985, p. 7-24. ISBN 0-444-
87637-5
SESAMO – F.Stefan Bibliografia e Referências - 145 -
15. BRZEZINSKI, Z.; GETTA, J., RYBNIK, J. & STEPNIEWSKI, W. UNIBASE - An
Integrated Access to Databases. Proceedings of the 10
th
International Conference on Very
Large Data Bases (VLDB), Singapore, August 27-31, 1984. Morgan Kaufmann, 1984, p.
388-396. ISBN 0-934613-16-8.
16. CÁRDENAS, Alfonso F. Heterogeneous Distributed DataBase Management: The HD-
DBMS. Proceedings of the IEEE, v. 75, n. 5, May, 1987, p. 588-600.
17. CAREY, Michael J. Granularity Hierarchies in Concurrency Control. Proceedings of the
2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS),
Atlanta, GA, USA, March 21-23, 1983. ACM Press, 1983, p. 156-165. ISBN 0-89791-
097-4
18. CASANOVA, Marco A. The Concurrency Control Problem for Database Systems.
Lecture Notes in Computer Science, Berlin, Germany: Springer, v. 116, 1981.
19. CELLARY, Wojciech & MORZY, Tadeusz. Locking with Prevention of Cyclic and
Infinite Restarting in Distributed Database Systems. Proceedings of the 11
th
International
Conference on Very Large Data Bases (VLDB), Stockholm, Sweden, August 21-23, 1985.
Morgan Kaufmann, 1985, p. 115-126.
20. COULOURIS, George; DOLLIMORE, Jean & KINDBERG, Tim. Distributed Systems.
Concepts and Design. Addison-Wesley, 3
rd
Edition, 2001. ISBN 0-32126-354-5.
21. DIRCKZE, Ravi A. & GRUENWALD, Le. A pre-serialization transaction management
technique for mobile multidatabases. Mobile Networks and Applications (MONET),
Kluwer/Springer, v. 5, n. 4, December, 2000, p. 311-321. ISSN: 1383-469X.
22. DUNHAM, Margaret H. & HELAL, Abdelsalam S. Mobile computing and Databases:
Anything New?. ACM SIGMOD Record, New York, USA: ACM Press, v. 24, n. 4,
December, 1995. ISSN: 0163-5808.
23. DUNHAM, Margaret H.; HELAL, Abdelsalam S. & BALAKRISHNAN, Santosh. A
mobile transaction model that captures both the data and movement behavior. Mobile
Networks and Applications (MONET), Kluwer/Springer, v. 2, n. 2, October, 1997, p. 149-
162. ISSN: 1383-469X.
SESAMO – F.Stefan Bibliografia e Referências - 146 -
24. DWYER, P. & LARSON, J. Some experiences with a distributed database testbed system.
Proceedings of the IEEE, v. 75, n. 5, May, 1987, p. 633-647.
25. EISENBERG, Andrew; MELTON, Jim; KULKARNI, Krishna; MICHELS, Jan-Eike &
ZEMKE, Fred. SQL:2003 Has Been Published. ACM SIGMOD Record, New York,
USA: ACM Press, v. 33, n. 1, March, 2004. ISSN: 0163-5808.
26. ELMAGARMID, Ahmed K. & DU, Weimin. A Paradigm for Concurrency Control in
Heterogeneous Distributed Database Systems. Proceedings of the 6
th
International
Conference on Data Engineering (ICDE), Los Angeles, CA, USA, February 5-9, 1990.
IEEE Computer Society, 1990, p. 37-46. ISBN 0-8186-2025-0.
27. ESWARAM, Kapali P.; GRAY, Jim; LORIE, Raymond & TRAIGER, Irving. The
notions of consistency and predicate locks in a database system. Communications of the
ACM (CACM), New York, USA: ACM Press, v. 19, n. 11, November, 1976, p. 624-633.
ISSN: 0001-0782.
28. FERREIRA, João E. & FINGER, Marcelo. Controle de concorrência e distribuição de
dados: teoria clássica, suas limitações e extensões modernas. São Paulo: Escola de
Computação 2000 - IME-USP, 2000.
29. GARCIA-MOLINA, Hector. Using Semantic Knowledge for transaction processing in a
distributed database. ACM Transactions on Database Systems (TODS), New York, USA:
ACM Press, v. 8, n. 2, June, 1983, p. 186-213. ISSN: 0362-5915
.
30. GEORGAKOPOULOS, Dimitrios; RUSINKIEWICZ, Marek & SHETH, Amit P. Using
Tickets to Enforce the Serializability of Multidatabase Transactions. IEEE Transactions
on Knowledge and Data Engineering (TKDE), Los Alamitos, USA: IEEE Computer
Society, vol. 6, n. 1, February, 1994, p. 166-180. ISSN 1041-4347.
31. GRAY, Jim N. Notes on Data Base Operating Systems. Operating Systems, An Advanced
Course. Lecture notes in Computer Science, Berlin, Germany: Springer-Verlag, n. 60,
1978, p. 393-481. ISBN: 3-540-08755-9.
32. GRAY, Jim N. The Recovery Manager of the System R Database Manager. ACM
Computing Surveys (CSUR), New York, USA: ACM Press, v. 13, n. 2, June, 1981, p.
223-242. ISSN: 0360-0300.
SESAMO – F.Stefan Bibliografia e Referências - 147 -
33. GUPTA, Ramesh; HARITSA, Jayant & RAMAMRITHAM, Krithi. Revisiting Commit
Processing in Distributed Database Systems. Proceedings of the 1997 ACM SIGMOD
International Conference on Management of Data, Tucson, Arizona, USA, May 11-15,
1997, p. 486-497. ISBN:0-89791-911-4.
34. HÄRDER, Theo & REUTER, Andreas. Principles of transaction-oriented database
recovery. ACM Computing Surveys (CSUR), New York, USA: ACM Press, v. 15, n. 4,
1983, p. 287-317. Reprinted in: Readings in Database Systems, M. Stonebraker, J.
Hellerstein (Eds.), third edition, Morgan Kaufmann, Los Altos, CA, March 1998.
35. HOLLYDAY, Joanne; AGRAWAL, Divyakant & ABBADI, Amr El. Disconnection
Modes for Mobile Databases. Wireless Networks (WN), Kluwer/Springer, v. 8, n. 4, July,
2002, p. 391-402. ISSN: 1022-0038.
36. HUANG, Shi-Ming; KWAN, Irene & LI, Chih-He. A Study on the Management of
Semantic Transaction for Efficient Data Retrieval. ACM SIGMOD Record, New York,
USA: ACM Press, v. 31, n. 3, September, 2002, p. 28-33.
37. IBM. Using the federated database technology of IBM DB2 Information Integrator. By
Anjali Grover, Eileen Lin and Ioana Ursu, October, 2003.
ftp://ftp.software.ibm.com/software/data/pubs/papers/iifed.pdf.
38. JACOBSON, G.; PIATETSKY-SHAPIRO, G.; LAFOND, C.; RAJINIKANTH, M. &
HERNANDEZ, J. CALIDA: A knowledge-based system for integrating multiple
heterogeneous databases. Proceedings of the 3rd International Conference on Data and
Knowledge Bases, Jerusalem, Israel, June, 1988, p. 3-18.
39. KORTH, Henry F.; LEVY, Eliezer & SILBERSCHATZ, Abraham. A formal approach to
recovery by compensating transactions. Proceedings of the 16
th
Iternational Conference on
Very Large Databases (VLDB), Brisbane, Australia, September 1990, p. 95-106.
40. KUMAR, Vijay; PRABHU, Nitin; DUNHAM, Margaret H. & SEYDIM, Ayse Yasemin.
TCOT - A Timeout-Based Mobile Transaction Commitment Protocol. IEEE Transactions
on Computers (TOC), Los Alamitos, USA: IEEE Computer Society, v. 51, n. 10, October,
2002, p. 1212-1218.
SESAMO – F.Stefan Bibliografia e Referências - 148 -
41. KUNG, H. T. & ROBINSON, John T. On Optimistic Methods for Concurrency Control.
ACM Transactions on Database Systems (TODS), New York, USA: ACM Press, v. 6, n.
2, June 1981, p. 213-226.
42. LAM, Kam-Yiu; LI, Guohui & KUO, Tei-Wei. A Multi-Version Data Model for
Executing Real-Time Transactions in a Mobile Environment. Proceedings of the 2
nd
ACM
International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE),
Santa Barbara, California, USA, May 20, 2001, p. 90-97.
43. LANDERS, T. A. & ROSENBERG, Ronni. An Overview of MULTIBASE. Proceedings
of DDB, 1982, p. 153-184.
44. LANGE, Danny & OSHIMA, Mitsuru. Programming and Deploying Java Mobile Agents
with Aglets. Addison-Wesley Professional, 1998, Massachusetts, USA. ISBN 0-20-
132582-9.
45. LIN, Huaizhong; CHEN, Chun & ZHOU, Bo. A Probability-Based Approach of
Transaction Consistency in Mobile Environments. Proceedings of the International
Conference on Computer Networks and Mobile Computing (ICCNMC’01), October,
2001. IEEE Computer Society, 2001, p. 505.
46. LIM, James B. & HURSON, Ali R. Transaction Processing in Mobile, Heterogeneous
Database Systems. IEEE Transactions on Knowledge and Data Engineering (TKDE), Los
Alamitos, USA: IEEE Computer Society, vol. 14, n. 6, Nov/Dec, 2002, p. 1330-1346.
47. LITWIN, W. An overview of the multidatabase system MRDSM. Proceedings of the
ACM National Conference, Denver, USA, October,1985, pp. 495-504.
48. LITWIN, W.; BOUDENANT, J.; ESCULIER, C.; FERRIER, A.; GLORIEUX, A.; LA
CHIMIA, J.; KABBAJ, K.; MOULINOUX, C.; ROLIN, P.; & STANGRET, C. SIRIUS
Systems for Distributed Data Management. In Distributed Data Bases, H.-J. Schneider,
Ed. North-Holland, The Netherlands, 1982, p. 311-366.
SESAMO – F.Stefan Bibliografia e Referências - 149 -
49. MOHAN, C.; HADERLE, Don; LINDSAY, Bruce; PIRAHESH, Hamid & SCHWARZ,
Peter. ARIES: a Transaction Recovery Method Supporting Fine-Granularity Locking and
Partial Rollbacks Using Write-Ahead Logging. ACM Transactions on Database Systems
(TODS), New York, USA: ACM Press, v. 17, n. 1, March, 1992, p. 94-162. ISSN: 0362-
5915
.
50. MOHAN, C.; LINDSAY, Bruce G. & OBERMARCK, Ron. Transaction Management in
the R* Distributed Database Management System. ACM Transactions on Database
Systems (TODS), New York, USA: ACM Press, v. 11, n. 4, 1986, p. 378-396.
51. ORACLE. Oracle’s Solutions for the Distributed Environment An Oracle White Paper.
June, 2002. Disponível na WWW (out/2005).
http://www.oracle.com/technology/products/dataint/pdf/distributed_environment.pdf
52. ORACLE. Oracle Technology Network. Disponível na WWW (out/2005).
http://www.oracle.com/technology/oramag/oracle/02-jul/o42special_jdbc.html - ACID
53. ÖZSU, M. Tamer & VALDURIEZ, Patrick. Principles of distributed systems. Prentice-
Hall, Inc., 2
nd
Edition, 1999. ISBN 0-13-659707-6.
54. PAPADIMITRIOU, Christos. The Serializability of Concurrent Database Updates.
Journal of Association for Computing Machinery (JACM), v. 26, n. 4, p. 631-653,
October, 1979.
55. PITOURA, Evagelia & BHARGAVA, B. Data Consistency in Intermittently Connected
Distributed Systems. IEEE Transactions on Knowledge and Data Engineering (TKDE),
Los Alamitos, USA: IEEE Computer Society, vol. 11, n. 6, Nov/Dec, 1999, p. 896-915.
ISSN 1041-4347.
56. PU, Calton. Superdatabases for Composition of Heterogeneous Databases. Proceedings of
ICDE, 1988, p. 548-555.
57. RAMAKRISHNAN, Raghu & GEHRKE, Johannes. Database Management Systems.
McGraw-Hill, 3
rd
Edition, 2003. ISBN 0-07-115110-9.
SESAMO – F.Stefan Bibliografia e Referências - 150 -
58. ROMAN, G.-C.; PICCO, G. P. & MURPHY, A. L. Software Engineering for Mobility: A
Roadmap. Proceedings of the 22
nd
International Conference on Software Engineering,
Limerick, Ireland, June 4-11, 2000, A. Finkelstein Ed., p. 241-258.
59. RUSINKIEWICZ, M.; ELMASRI, R.; CZEJDO, B.; GEORGAKOPOULOS, D.;
KARABATIS, G.; JAMOUSSI, A.; LOA, L. & LI, Y. 1989. OMNIBASE: Design and
Implementation of a Multidatabase System. Proceedings of the 1
st
Annual Symposium in
Parallel and Distributed Processing, Dallas, Texas, USA, May, 1989, p. 162-169.
60. SALEM, Kenneth; GARCIA-MOLINA, Hector & SHANDS, Jeannie. Altruistic Locking.
ACM Transactions on Database Systems (TODS), New York, USA: ACM Press, v.19, n.
1, March, 1994, p. 117-165.
61. SHETH, Amit P. & LARSON, James A. Federated Database Systems for Managing
Distributed, Heterogeneous, and Autonomous Databases. ACM Computing Surveys
(CSUR), New York, USA: ACM Press, v. 22, n. 3, 1990, p. 183-236.
62. SILBERSCHATZ, Abraham; KORTH, Henry F. & SUDARSCHAN, Sundararajar.
Database system concepts. McGraw-Hill, 4
th
Edition, 2002. ISBN 0-07-228363-7.
63. TANDEM Performance Group, The. A Benchmark of NonStop SQL on the Debit Credit
Transaction (Invited Paper). SIGMOD Conference, 1988, p. 337-341.
64. TEMPLETON, M.; BRILL, D.; CHEN, A.; DAO, S.; LUND, E.; MCGREGOR, R. &
WARD, P. Mermaid: A front-end to distributed heterogeneous databases. Proceedings of
the IEEE, v. 75, n. 5, May, 1987, p. 695-708.
65. THOMAS, Robert H. A Majority Consensus Approach to Concurrency Control for
Multiple Copy Databases. ACM Transactions on Database Systems (TODS), New York,
USA: ACM Press, v. 4, n. 2, June, 1979, p. 180-209.
66. TÜRKER, Can & ZINI, Gabriele. A Survey of Academic and Commercial Approaches to
Transaction Support in Mobile Computing Environments. Technical Report #429,
November, 2003, ETH Zurich. Departament of Computer Science. Institute of
Information Systems.
SESAMO – F.Stefan Bibliografia e Referências - 151 -
67. WALBORN, Gary D. & CHRYSANTHIS, Panos K. Supporting Semantics-Based
Transaction Processing in Mobile Database Applications. Proceeding of the 14th IEEE
Symposium on Reliable Distributed Systems (SRDS), September, 1995, Bad Neuenahr,
Germany.
68. WALBORN, Gary D. & CHRYSANTHIS, Panos K. Transaction Processing in PRO-
MOTION. Proceedings of the 1999 ACM Symposium on Applied Computing (SAC), San
Antonio, Texas, USA, 1999, p. 389-398. ISBN: 1-58113-086-4.
69. YAN, Ling-Ling; ÖZSU, M. Tamer & LIU, Ling. Accessing Heterogeneous Data
Through Homogenization and Integration Mediators. CoopIS 1997, p. 130-139.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
