Bases de dados OO
Sumário
 Conceitos gerais
 Exemplo do ObjectStore)







Arquitectura
Criação de objectos
Gestão da concorrência
Colecções
Perguntas
Índices
Associações
BDOO - 1
Transacções
Transacção é uma unidade lógica de trabalho, uma parte consistente e fiável de uma execução
de um programa.
• suporte ao acesso concorrente à BD
• suporte à tolerância a falhas
(acesso a dados persistentes deve ocorrer sempre dentro de uma transacção)
 Tolerância a falhas
• garante-se que as alterações na memória persistente devidas a uma transacção ou
são todas feitas ou não é nenhuma;
• uma transacção considera-se completada com sucesso só após todas as alterações
estarem registadas em memória estável — transacção cometida; uma falha do
servidor ou da rede após o cometimento já não afecta o resultado.
 Implementação
• baseia-se na existência de um ficheiro de log, onde se vão registando as alterações
até ao cometimento
• cometimento em duas fases: só depois de este estar registado no log se propagam
as alterações para a BD (fácil refazer uma transacção cometida, em caso de falha)
• qualquer escrita na BD antes do cometimento implica capacidade para desfazer
• propagação retardada — servidor sabe onde está a versão mais actual (log ou BD)
BDOO - 2
Concorrência
 Controlo de concorrência visa evitar interferências entre os vários processos
• alterações a dados persistentes são privadas e invisíveis pelos outros processos até à
conclusão da transacção
• alterações dos outros processos aos dados persistentes são invisíveis à transacção
 Implementação
• bloqueio em duas fases — os bloqueios ou se conseguem todos de uma vez, ou
nenhum; só se volta a pedir outro bloqueio depois de libertar todos os existentes
• propagação retardada pode aumentar a concorrência, mas o log pode crescer muito
• objectivo: transacção atómica — considera-se a transacção toda executada no
instante do seu início (timestamps)
 Razões para uma transacção abortar
• instrução explícita
• interrupção devida a deadlock
• transferência não-local de controlo, por exemplo, devida a uma excepção tratada
exteriormente à transacção lexical
• falha de sistema
BDOO - 3
Extensão
 transacção excessivamente grande — pode prender muitos recursos — baixo nível de
concorrência
•
excessivamente pequena — pode permitir a outros o acesso a dados num estado
intermédio inconsistente
•
consistência da BD deve estar garantida antes e depois da transacção
 tipos de definição de transacção
•
lexical — a transacção está contida num escopo lexical (e.g., ficheiro) e marca-se
com macros
•
dinâmicas — princípio e fim são definidos dinamicamente
 Transacções lexicais
•
OS_BEGIN_TXN(identifier,exception**,transaction-type)
OS_END_TXN(identifier)
•
identifier pode ser qualquer; exception guarda o género de excepção; transaction-type:
os_transaction::update — transacção pode ter que escrever na BD — ou
os_transaction::read_only — não escreve
BDOO - 4
Exemplo
#include <stdio.h>
#include <ostore/ostore.hh>
#include "dbname.h"
int main(int, char **)
{
objectstore::initialize();
OS_ESTABLISH_FAULT_HANDLER
os_typespec *int_type = os_typespec::get_signed_int();
os_database *db1 = os_database::open(example_db_name);
OS_BEGIN_TXN(tx1, 0, os_transaction::update)
os_database_root *a_root = db1->find_root("count");
int *countp = (int*) (a_root->get_value(int_type));
printf("hello2: hello, world.\n");
printf("hello2: the counter is now %d\n",*countp);
++*countp;
printf("hello2: incremented counter to %d\n",*countp);
OS_END_TXN(tx1)
db1->close();
OS_END_FAULT_HANDLER
return 0;
}
BDOO - 5
Bloqueios
 bloqueio — garantia de acesso exclusivo ou, pelo menos, de acesso controlado a um
conjunto de dados
•
bloqueio para leitura e bloqueio para escrita; compatibilidade
•
bloqueio são implícitos, mas pode-se controlar a granularidadedos objectos
bloqueados (página, segmento, BD)
 deadlock
•
Transacção T1
1)
Transacção T2
bloqueia(A)
2)
bloqueia(B)
3) bloqueia B ?
4)
•
bloqueia(A) ?
é necessário interromper pelo menos uma das transacções, desfazer alguns
efeitos que estejam já propagados e reiniciá-la
BDOO - 6
Bases de dados OO
Sumário
 Conceitos gerais
 Exemplo do ObjectStore)







Arquitectura
Criação de objectos
Gestão da concorrência
Colecções
Perguntas
Índices
Associações
BDOO - 7
Colecções
 Colecção é um objecto que serve para agrupar outros objectos
•
operações de inserção e remoção e da teoria de conjuntos
•
representação eficiente e adaptável
•
suporte para perguntas simples e mais complexas
 Modelar
•
extensão da classe
•
atributo multi-valor (relação não normalizada)
•
associações binárias, através de dicionários
BDOO - 8
Exemplo dos componentes
memorizar, por peça, o número de série, os seus componentes imediatos e engenheiro responsável
class part_list //lista ligada
{
public:
part *first;
part_list *rest;
};
ou
class part
{
public:
int part_id;
part_list *children;
employee *responsible_engineer;
part(int id) {
part_id = id;
responsible_engineer = 0;
}
};
class part //com conjunto
{
public:
int part_number;
os_Set<part*> &children;
employee *responsible_engineer;
part (int n) : children(os_Set<part*>::create(db1)){
part_number = n;
responsible_engineer = 0;
}
};
BDOO - 9
Escolha de colecção
Muda entre ordenado e desordenado ou entre desordenado
com duplicados e desordenado sem duplicados?
não
sim
Mantém a ordem de inserção?
os_Collection
não
Associa uma chave com cada elemento?
sim
os_Dictionary
não
os_Set
Adiciona automaticamente um número
especificado de elementos nulos?
não
Admite duplicados?
não
sim
os_List
sim
os_Array
sim
os_Bag
BDOO - 10
Criação de colecções
os_Set
os_Bag
os_database *db
os_List
os_Collection
static os_Set<E> &create(
os_Array
os_segment *seg
os_database *db,
os_object_cluster *clust
os_unsigned_int32 behavior = 0,
os_configuration *config
os_unsigned_int32 expected_cardinality = 10,
const os_coll_rep_descriptor *rep = 0,
os_int32 = os_collection::don't associate_policy
);
static os_Dictionary<K,E> &create(
os_database *db,
os_unsigned_int32 expected_cardinality = 10,
os_unsigned_int32 behavior = 0
);
•
utilizar o
construtor
respectivo
os_Set(), só
para colecções
na pilha ou
como membro
dado de outra
classe.
BDOO - 11
Comportamento
os_Set
Permite
Duplicados
Proibido
Sinaliza
Mantém
Duplicados
Ordem
Não, por omissão Proibido
Permite
Nulos
Não, por omissão
os_Bag
os_List
os_Dictionary
os_Array
Requerido
Sim, por omissão
Requerido
Não, por omissão
Proibido
Não, por omissão
Proíbido
Não, por omissão
Não, por omissão
Não, por omissão
Requerido
Requerido
•
Proibido
Requerido
Proibido
Requerido
outros comportamentos
- executar pick() numa colecção vazia sinaliza excepção (ou não)
- não mantém cursor (ou mantém, i.e., garante que inserções e apagamentos são
considerados no resto de uma visita)
•
uma os_Collection permite os vários comportamentos, e mudá-los a meio do uso, com ou
sem verificação dos elementos já metidos.
BDOO - 12
Representação
 A representação das colecções muda com a cardinalidade efectiva ou prevista
 Colecções pequenas (0 a 4) embutidas noutros objectos — os_tinyarray
 Colecções embutidas (5 a 20) e não embutidas (0 a 20) — os_chained_list
 Colecções grandes (21 a ...) usam outros métodos baseados em tabelas de dispersão
 É possível definir outras gamas de valores e outras representações que existem, de forma
a afinar para o problema concreto; as definições podem ser agrupadas numa política e
esta passada para a classe paramétrica em causa
Para destruir uma colecção
static void os_Set::destroy(os_Set<E>&)
BDOO - 13
Manipulação de colecções
 inserção
void insert(const E)
dicionários
void insert(const K &key, const E element)
void insert(const K *key_ptr, const E element)
Ex:
os_database *db1;
message *a_msg;
os_Set<message*> &temp_set = os_Set<message*>::create(db1);
…
temp_set.insert(a_msg);
temp_set.insert(a_msg); //nada se a colecção estiver sem allow_duplicates e
sem signal_duplicates
 remoção
void remove(const E);
dicionários
void remove(const K &key, const E element);
E remove_value(const K &key, os_unsigned_int32 n = 1 );
BDOO - 14
Navegação nas colecções
 Cursores — utilizam-se para atravessar as colecções e processá-las elemento a elemento
 Caminhos (path) — representam um caminho para navegar, a começar nos elementos de uma
colecção
•
servem para especificar chaves de índices e para associar uma ordem a um cursor
•
em conjunto com uma definição de gama, servem para restringir os elementos visitados
pelo cursor
 Gamas — também servem para obter de um dicionário os elementos cujas chaves a satisfazem
 uma vez posicionado com um cursor ou um índice numérico podem-se usar as funções:
- void os_Collection::insert_after(E, const os_Cursor<E>&)
- void os_Collection::insert_after(E, os_unsigned_int32)
-
insert_before
-
remove_at
-
replace_at
-
retrieve
etc...
BDOO - 15
Cursores
os_database *db1;
…
os_collection<person*> &people
= os_Collection<person*>::create(db1);
… // inserções em people
os_collection<person*> &teenagers
= os_Collection<person*>::create(db1);
person *p;
os_Cursor<person*> c(people);
for (p = c.first(); c.more(); p = c.next())
if (p->age >= 13 && p->age <= 19)
teenagers.insert(p);
•
o cursor atravessa a colecção pela ordem desta, ou arbitrariamente, se não houver uma
•
no caso de existirem duplicados, também são visitados
BDOO - 16
Caminhos
 os caminhos são usados para especificar a ordem de travessia e as chaves de índices
 para percorrer um conjunto de componentes pela ordem dada pelo respectivo número
os_index_path::create("part*", "part_number", db1);
- os caminhos começam na colecção dos apontadorespara componentes e terminam
nos números
- os caminhos são criados na heap, pelo que devem ser destruídos quando já não
forem precisos
static void destroy(os_index_path&);
- os caminhos podem ter vários passos: para iterar com base no número do
engenheiro responsável
os_index_path::create("part*", "responsible_engineer->emp_id", db1);
- se no caminho aparecer uma colecção, cada um dos seus elementos é considerado
os_index_path::create("employee*", "supervisees[]->name", db1);
- para associar um caminho a um cursor
os_Cursor(const os_Collection&, const os_index_path& );
BDOO - 17
Exemplo
os_index_path &a_path = os_index_path::create("part*", "responsible_engineer->emp_id", db1);
os_Cursor<part*> c(a_set, a_path);
part *p = 0;
for (p = c.first(); p; p = c.next())
printf("%d", p-> responsible_engineer->emp_id);
•
se existir um índice neste caminho, ele é usado para tornar a travessia mais eficiente
•
se não existir, o construtor do cursor copia os elementos da colecção para uma
estrutura separada, aplica o caminho a cada elemento, copia a chave terminal para
essa estrutura e ordena-a de acordo com essa chave
•
se a interpretação do caminho passar por desreferenciar um apontador ordena-se por
endereço, para melhorar a paginação (se for apontador para string, usa-se o valor da
string)
•
alterações nos dados podem implicar alterações na colecção e nos cursores; para
que o comportamento reflicta as alterações é necessário especificar
os_Collection::maintain_cursors e
no cursor os_Cursor::safe
BDOO - 18
Gamas
 uma gama é um objecto da classe os_coll_range, que serve para
-
restringir um cursor aos elementos da colecção que a satisfazem
-
qualificar as pesquisas
 gamas só com um limite
os_coll_range(int rel_op, int value);
com dois limites
os_coll_range(int rel_op1, int value1, int rel_op2, int value2);
• rel_op = os_collection::EQ
(NE, LT, LE, GT, GE)
• value de um qualquer dos tipos fundamentais ou um apontador (const void* value)
• se for char* o comportamento é definido em termos de strcmp()
 Exemplo: os_coll_range(os_collection::GT, 4, os_collection::LE, 7) satisfeita por 4<xŠ7
 Restringindo um cursor (mais leve que uma pesquisa com os_collection::query)
os_Cursor<E>(const os_Collection<E> & coll, const os_index_path &path, const os_coll_range
&range, os_int32 options=os_cursor::unsafe);
os_Cursor<E>(const os_dictionary & coll, const os_coll_range &range, os_int32
options=os_cursor::unsafe);
BDOO - 19
Obtenção de elementos
 Obter elementos individuais (leve)
void* pick(
const os_index_path &path,
const os_coll_range &range) const;
Ex:
os_index_path &id_path = os_index_path::create("employee*","id",db1);
os_coll_range range_eq_1138(EQ,1138);
…
employee *e = a_coll.pick(id_path, range_eq_1138);
• mais do que um empregado com id=1138
• dicionário
 devolvido um arbitrariamente
E pick(const K &key_ref) const;
E pick(const K *key_ptr) const;
// obtém elemento com a chave indicada
E pick(const os_coll_range&) const;// obtém elemento cuja chave satisfaz gama
• elemento arbitrário
E pick() const;
a_cell= a_bus->pins.pick()->cell->container
BDOO - 20
Operações sobre uma colecção
 Pertença
• os_int32 contains(E) const;
• os_boolean contains(const K &key_ref, const E element) const; dicionário
 Contagem de repetidos
• os_int32 count(E);
• os_unsigned_int32 count_values(const K &key_ref) const;
dicionário
 Cardinalidade
• os_unsigned_int32 cardinality() const; obtém o número de ocorrências de valores
• os_int32 empty();
testa se está vazio
 Consolidar duplicados
os_database *db1;
part *a_part, *p;
employee *e;
os_Collection<employee*> &emp_bag=
os_Collection<employee*>::create(
db1, os_collection::allow_duplicates);
os_Collection<employee*> &emp_set=
os_Collection<employee*>::create(db1);
os_Cursor<part*> c(a_part->children);
for (p=c.first(); p; p=c.next() )
emp_bag.insert(p->responsible_engineer);
emp_set = emp_bag;
os_Cursor<employee*> c(emp_set);
for (e=c.first(); e; e=c.next() )
cout <<e->name<<"\t"<<emp_bag.count(e)<<"\n";
BDOO - 21
Operações entre colecções
 Operações em que ambos os operandos são colecções (iteração implícita)
operator =()
atribuição
operator |=()
adição
operator -=()
remoção
operator &=()
intersecção
operator <()
subconjunto próprio
operator >()
superconjunto próprio
operator <=()
subconjunto
operator >=()
superconjunto
operator ==()
identidade
operator !=()
verifica se alguns elementos são diferentes
Ex: a_list |= a_part->children;
BDOO - 22
Funções de ordem e dispersão
 se um caminho terminar numa classe ou em números de vírgula flutuante (em vez de
inteiros ou cadeias)
•
fornecer função de ordem para poder usar esse caminho para controlar a iteração ou
como chave de um índice ordenado
•
fornecer função de dispersão para poder usar o caminho como chave de um índice
desordenado
 registar as funções no ObjectStore
• os_index_key(type,rank-function,hash-function)
//sem espaços entre os argumentos
 função de ordem: dois argumentos instâncias da classe; devolve os_collection::LT (GT, EQ)
 função de dispersão: para cada instância da classe calcula um os_unsigned_int32 para
servir de chave.
BDOO - 23