Serialização Relaxada em Banco de
Dados Múltiplos
Andressa Sebben
[email protected]
Dados do artigo
MEHROTRA, S., RASTOGI, R., KORTH,
H. F., AND SILBERSCHATZ, A. 1992.
Relaxing serializability in multidatabase
systems.
Second International Workshop on
Research Issues on Data Engineering:
Transaction and Query Processing,
Mission Palms, Arizona, Feb.
Sumário
Introdução
Modelo de banco de dados múltiplo
Execuções não serializáveis
Aplicação em ambientes MDBS
Conclusão
Introdução
Modelo de transações padrão:
Transações executadas isoladamente mapeiam o BD de um estado
consistente para outro estado consistente
Em Transações concorrentes, a consistência é garantida requerendo que
a escala resultante da execução concorrente seja serializável
Se cada transação isoladamente preserva a consistência, então uma
escala serializável também preserva.
Serialização: padrão de correção em BDs
Difícil de ser alcançada em Bancos de Dados Múltiplos – MDBS
São necessários outros critérios de correção além da
serialização
Bancos de Dados Múltiplos - MDBS
Sistema que integra BDs pré-existentes e
independentes
Os SGBDs locais podem empregar hardware e software
heterogêneo
Podem utilizar diferentes modelos lógicos, linguagens DDL e
DML, controle de concorrência, etc.
Simula a integração lógica dos BDs, sem que haja uma
integração física correspondente
Permitem a execução de transações que acessam
dados em diversos SGBDs locais
Modelo de banco de dados múltiplo
Transações: locais ou globais
Ti é uma seqüência de leituras (ri) e escritas (wi) resultantes de
um programa
Escala global: execução concorrente de transações globais e
locais
Escala local: subconjunto da escala global
Local Transaction Manager ou LTM em cada banco local
Global Transaction Manager ou GTM, operando sobre todos os
LTM
Modelo de banco de dados múltiplo (2)
SBGDs locais:
Autonomia de arquitetura
Autonomia de comunicação
Impactos da autonomia no modelo MDBS:
SGBDs locais não sabem da existência dos demais SGBDs
É necessário um GTM para garantir a consistência
Operações externas podem acessar o banco sem o
conhecimento do GTM
Controle de Concorrência em MDBS
Dificuldades:
Autonomia de arquitetura:

Os diversos SGBDs possam utilizar diferentes esquemas de controle
de concorrência, o que dificulta a serialização em MDBS.
Autonomia de comunicação:


Não comunicam ao GTM informações sobre controle de concorrência
O GTM pode não tomar conhecimento da ordem de serialização das
transações em vários locais
Controle de Concorrência em MDBS (2)
Papel do GTM:
Para cada operação global a ser executada, o GTM
seleciona o SGBD local onde a operação deverá ser
executada;
Para cada SGBD, o GTM aloca um servidor (um por SGBD
por transação) e submete a operação ao servidor;
O servidor encaminha a operação ao SGBD, que, por tê-la
recebido de uma única máquina, trata-a como uma operação
local.
Execuções não serializáveis
Restrições de integridade como critério de correção
Trabalhar com 2 tipos de RI:
explícitas: aquelas que podem ser formalmente definidas e
facilmente expressadas;
implícitas: aquelas que não são facilmente expressadas.
Algumas transações necessitam visualizar o BD
consistente com respeito a apenas restrições explícitas,
enquanto que outras transações devem ver o banco
consistente com relação a ambas.
Execuções não serializáveis (2)
Ex: um banco que suporta transações de crédito,
transferência e auditoria.
Uma restrição explícita seria que cada conta tenha saldo
positivo
Uma restrição implícita seria que qualquer transação que
recupera dados de múltiplas contas veja uma soma correta
dos saldos de todas as contas.
Considere:
T1 uma transação de transferência que transfere R$ 500,00 de uma
conta A num site s1 para uma conta B num site s2.
T2 uma transação de auditoria que retorna a soma das contas A e B
Uma escala global não serializável S, resultante da execução
concorrente de T1 e T2
As escalas locais S1 e S2, nos sites s1 e s2 respectivamente:
S1: r1(a) w1(a) r2(a)
S2: r2(b) r1(b) w1(b)
Correção RS
Nova noção de correção: RS-Correcteness
garante que a consistência do BD é preservada e que cada
transação vê um estado consistente do BD
Transações RS
Restrições explícitas e implícitas
Transações não RS
Apenas restrições explícitas
Correção RS (2)
Uma escala global S consistindo de transações RS e
transações não RS é dita ser RS-correta se:
preserva as restrições de integridade explícitas do banco de
dados;
transações em S visualizam estados consistentes com
respeito às restrições de integridade explícitas
nenhum ciclo no grafo de serialização de S contém uma
transação RS (ou seja, nenhuma transação em S é
serializada tanto antes como depois de uma transação RS).
Convenções p/ o restante do trabalho
Apenas restrições explícitas serão consideradas
Assume-se que qualquer transação quando executada
em isolamento, preserva as Restrições de Integridade
do BD.
Como resultado, qualquer escala serializável é dita RS
correta.
Aplicação em ambientes MDBS
Novo protocolo: Forced Conflict 2PL ou
FC2PL
Deve ser seguido pelo GTM a fim de garantir a
correção RS das escalas globais
SGBSs locais que o adotam são denominados “2PLsites”. Os demais são chamados “não 2PL-sites”.
O SGBD local em cada site si contém uma unidade de
dados ticketi
Bloqueios globais e locais.
FC2PL
Toda TG obtém o bloqueio global correspondente a um item de
dado, junto ao GTM, antes de acessar o item de dado;
Uma TG, uma vez que libera um bloqueio global, não obtém
mais nenhum bloqueio global;
Uma TG não pode obter um bloqueio global em um item de dado
se um bloqueio conflitante é mantido no item por outra TG;
Uma TG não libera um bloqueio global a não ser que todos os
bloqueios locais correspondentes ao bloqueio global mantido
pela TG para itens de dados em 2PL-sites terem sido obtidos;
FC2PL (2)
O bloqueio global para um item de dado acessado por uma TG
em um não 2PL-site é liberado apenas após sua operação no
item de dado completar a execução;
Toda TG com operações em um não 2PL-site si faz um
write(ticketi) antes de executar qualquer de suas
operações no site;
Qualquer transação não RS com operações em um 2PL-site si
executa um read(ticketi);
Transações RS executam write(ticketi) em qualquer 2PL
site si .
Teorema 1
Considere um MDBS onde todos os locais são Não2PL. Se o protocolo FC2PL for utilizado, então todas as
escalas globais serão serializáveis.
Teorema 2
Nenhum ciclo no grafo de serialização de uma escala
FC2PL S contém transações RS.
Teorema 3
Seja S uma escala FC2PL. Se não há restrições de
integridade entre itens de dados locais e globais, e os
programas de transação global possuem estrutura fixa,
então S preserva a consistência do banco de dados, e
as transações em S visualizam estados consistentes
do banco de dados
Conclusão
O artigo propõe uma forma mais geral para garantir a
correção de um MDBS;
As escalas RS-corretas garantem, além das restrições
de integridade, que as transações verão estados
consistentes do banco;
O protocolo proposto garante que as escalas são RScorretas, sem afetar a autonomia global dos sites.