TC – DEI, 2005/2006
Armazenamento de Dados
-- Ficheiros & Bases-de-Dados --
Paulo Marques
[email protected]
http://www.dei.uc.pt/~pmarques
Tecnologia dos Computadores 2005/2006
Motivação
Departamento de Engenharia Informática
 Numerus clausus = 120, Duração média=4.5anos
 Alunos Inscritos… 120x4.5 = 630
 Adicionemos alunos de mestrado, doutoramento, docentes e
funcionários… ~ 1000 pessoas
Sistema de Informação…
 struct Pessoa {
char nome[80];
long BI;
char morada[200];
pixel_rgb fotografia[640][480];
...
};
 sizeof(Pessoa)  900 Kbyte
 900Kbyte * 1000  900 Mbyte
TC – DEI, 2005/2006
Motivação (2)
É necessário armazenar os dados de forma
persistente (i.e. não volátil)
Não é possível manter simultaneamente todos
os dados em memória, mesmo quando o
programa está em execução
 Os 900 Mbyte foram uma estimativa por baixo!
TC – DEI, 2005/2006
Sistemas de Informação
Actualmente, é comum separar-se as
aplicações em dados persistentes e “lógica de
negócio”
 Em sistemas “pequenos”: Ficheiros directos
 Em sistemas “grandes”: Bases-de-dados
Lógica
de
Controlo
Dados
Persistentes
Programa
TC – DEI, 2005/2006
Sistema de Ficheiros
Sistema de Ficheiros:
 Recurso directamente disponível a nível do sistema operativo
O SO apenas oferece primitivas para:
 Abrir e fechar ficheiros
 Ler e escrever blocos de bytes no ficheiro
O programador é responsável por programar toda a
gestão de dados nos ficheiros
 Índices para pesquisas rápidas, tolerância a erros, gestão de
concorrência, etc.
Aplicação
TC – DEI, 2005/2006
Bases-de-Dados
Existe um programa especial (SGBD – Sistema de
Gestão de Base-de-Dados) que faz toda a gestão dos
dados
 Oracle, MS-SQL Server, Postgre, MySQL, etc.
O programa estabelece uma ligação à base-de-dados
utilizando um protocolo chamado ODBC
 A BD pode estar na mesma máquina ou noutra máquina
Através da ligação, envia os seus dados e pode fazer
pesquisas
 SQL = Structured Query Language
ODBC
Aplicação
Base
de
Dados
SGBD
(Sistema de
Gestão de BD)
TC – DEI, 2005/2006
Sistemas de Ficheiros
Acesso a ficheiros
O sistema operativo disponibiliza funções para:
 Abrir e fechar ficheiros  open() / close()
 Ler e escrever dados  read()/write()
Quando se abre um ficheiro, é retornado um
handle (inteiro) que representa o ficheiro nesse
processo
TC – DEI, 2005/2006
Acesso a ficheiros (2)
Associado a cada handle, que representa um ficheiro
aberto, também existe um FILE POINTER (FP)
 O FP representa a posição corrente de leitura ou escrita no
ficheiro
 O FP é incrementado automaticamente sempre que há uma
leitura ou escrita
FP
Ficheiro
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14
Associado a cada handle existe um buffer de dados
 Principio da localidade temporal e espacial
 Funciona como cache e pre-fetch
TC – DEI, 2005/2006
Como é que o SO organiza os ficheiros?
Árvore de Directórios
TC – DEI, 2005/2006
Como é que o SO sabe onde estão os ficheiros?
TC – DEI, 2005/2006
Um exemplo prático FAT (DOS/Windows)
O disco encontra-se dividido em sectores
(clusters), a unidade mínima de informação a
que se consegue aceder num disco
No início do disco (disquete) existe:
 Boot sector
 File Allocation Table (FAT)
 Disk Root Directory
TC – DEI, 2005/2006
FAT
Cada entrada da FAT indica qual o próximo sector que
um certo ficheiro ocupa
Cada entrada da Disk Root Directory indica o nome e
atributos de um certo ficheiro, assim como o seu
primeiro sector
Disco
Boot
Exame.doc
RH
2003.12.06-14:21
10345
…
210
Frequência.doc
RH
2003.12.05-17:30
14121
…
201
FAT
Directory Table
Data
O ficheiro “Frequência.doc”
ocupa os sectores 201, 203,
204 e 205
207 203 EOF 204 205 EOF 202 208 209 215 FREEEOF 214 BAD EOF
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
TC – DEI, 2005/2006
Questões…
A Disk Root Table apenas contém as entradas
do directório raiz do disco. Como é que são
guardadas os sub-directórios?
FAT16 quer dizer que os ponteiros na FAT são
de 16 bits.
 Qual é o número máximo de ficheiros que o disco
pode ter?
 Tendo um disco de 40Gbytes, qual seria o tamanho
de cada sector (cluster)? Vê algum problema nisso?
(hoje, em Windows, quando não se utiliza NTFS
utiliza-se FAT32)
TC – DEI, 2005/2006
Voltemos ao Sistema de Informação…
Suponhamos que armazenamos todas as
pessoas do DEI num ficheiro sequencial…
“Pessoas.dat”
JOANA FRANCISCA
10896534
R. Fernão Lop
Qual é o problema se quisermos encontrar o aluno
com o BI Nº 10896534?
Esquecendo as caches…
Tempo médio de acesso ao disco = 10ms
Em média temos de percorrer ½ ficheiro = 500 entradas
500 entradas X 10ms = 5000ms = 5s!!!
TC – DEI, 2005/2006
Utilização de Índices
Se se sabe que vão ser feitas pesquisas por BI, cria-se
uma tabela especial que para cada BI indica qual a
entrada no ficheiro que a contém.
 Esta tabela chama-se um índice sobre o BI
 A tabela é armazenada conjuntamente no ficheiro ou num
ficheiro à parte
“Pessoas.dat”
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … …
10896534
12
11843234
43
17345342
234
(…)
BI
(…)
Entrada
TC – DEI, 2005/2006
Utilização de Índices
Os índices resultam porque…
 Tipicamente o tamanho do índice é muito mais pequeno do
que o tamanho dos dados
 Muitas vezes é mesmo possível manter todo o índice em
memória
 Os índices podem estar ordenados (pesquisa binária) ou pode
fazer-se hashing*
Um índice deste género também é conhecido como
TABELA INVERTIDA (Inverted Table)
* Hashing  Uma técnica muito inteligente e rápida que permite
encontrar um elemento numa tabela usando tipicamente apenas uma
comparação. Irá falar muito dela durante o próximo ano (PA3)
TC – DEI, 2005/2006
Tamanho do Índice
Atenção: em muitos sistemas, o tamanho dos
índices pode tornar-se um problema
No nosso caso e admitindo que o Sistema de
Informação comporta no máximo 10.000
alunos, qual é que teria de ser o tamanho do
índice para BIs?
TC – DEI, 2005/2006
» If you don’t find it in the index,
look very carefully through the
entire catalogue «
Sears, Roebuck and Co. Consumer’s Guide, 1897
TC – DEI, 2005/2006
TC – DEI, 2005/2006
Bases-de-Dados
ODBC
Aplicação
Base
de
Dados
SGBD
(Sistema de
Gestão de BD)
A aplicação estabelece uma
ligação ao SGBD que é
responsável por manter todos
os dados da aplicação
O protocolo de comunicação
utilizado é ODBD
A linguagem utilizada para
falar com a BD chama-se SQL
(Structured Query Language)
A base-de-dados tem
obrigação de:
 Mandar os dados de forma
persistente
 Facilitar a forma como a
gestão dos dados é realizada
 Responder a interrogações e
actualizações de forma
rápida
 Tolerar falhas (e.g. faltar a luz
a meio de uma escrita)
TC – DEI, 2005/2006
Modelo de Dados
A maioria das bases-de-dados actuais seguem
o chamado MODELO RELACIONAL
 No Modelo Relacional, os dados são vistos em
termos de tabelas e relações entre tabelas
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
505404534
José Malaquias
R. Pinhal Marrocos, 43, 3030-290
Coimbra
1981
...
…
...
...
Tabela Alunos
TC – DEI, 2005/2006
Tabelas
Chave Primária: Atributo especial que permite
identificar univocamente um tuplo
Atributo: Algo que caracteriza a entidade
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
505404534
José Malaquias
R. Pinhal Marrocos, 43, 3030-290
Coimbra
1981
...
…
...
...
Tuplo: Conjunto ordenado de dados relacionados
TC – DEI, 2005/2006
Relacionamentos
Tabela Alunos
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
505404534
José Malaquias
R. Pinhal Marrocos, 43, 3030-290
Coimbra
1981
...
…
...
...
Tabela Cadeiras
NUM_CADEIRA
NOME_CADEIRA
ANO
SEMESTRE
1
Tecnologias dos Computadores
1
1
3
Programação e Algoritmos II
1
2
6
Sistemas Operativos
2
1
...
…
...
...
Tabela Inscrições
NUM_INSC
NUM_CADEIRA
NUM_ALUNO
ANO
NOTA
3243
1
501000885
1998
12
4321
3
501000885
1998
13
1232
1
501003426
1998
19
3487
6
505404534
1999
NULL
...
...
...
...
...
TC – DEI, 2005/2006
Relacionamentos
A tabela Inscrições está relacionada com a
tabela Alunos e Cadeiras
 As chaves primárias dos relacionamentos aparecem
como atributos da chave do relacionamento
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
505404534
José Malaquias
R. Pinhal Marrocos, 43, 3030-290
Coimbra
1981
...
…
...
...
NUM_CADEIRA
NOME_CADEIRA
ANO
SEMESTRE
1
Tecnologias dos Computadores
1
1
3
Programação e Algoritmos II
1
2
6
Sistemas Operativos
2
1
...
…
...
...
NUM_INSC
NUM_CADEIRA
NUM_ALUNO
ANO
NOTA
3243
1
501000885
1998
12
4321
3
501000885
1998
13
1232
1
501003426
1998
19
3487
6
505404534
1999
NULL
...
...
...
...
...
TC – DEI, 2005/2006
Exemplo Prático – MS Access
TC – DEI, 2005/2006
Queries
Como as tabelas estão relacionadas, é possível fazer
“interrogações” (queries) à base-de-dados
 Exemplo: “Quais os nomes e anos de nascimento dos alunos
que estiveram inscritos a Tecnologias dos Computadores em
1998”
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
7
505404534
José Malaquias
R. Pinhal Marrocos, 43, 3030-290
Coimbra
1981
...
…
...
...
6
7
2
NUM_CADEIRA
NOME_CADEIRA
1
ANO
SEMESTRE
Tecnologias dos Computadores
1
1
3
Programação e Algoritmos II
1
2
6
Sistemas Operativos
2
1
...
…
...
...
NUM_INSC
NUM_CADEIRA
NUM_ALUNO
ANO
NOTA
3243
1
501000885
1998
12
3
501000885
1998
1
501003426
1998
3487
6
505404534
1999
NULL
...
...
...
...
...
4321
1232
3
5
1
4
13
19
TC – DEI, 2005/2006
Queries - SQL
“Quais os nomes e os anos de nascimento dos
alunos que estiveram inscritos a Tecnologias
dos Computadores em 1998”
SELECT
FROM
WHERE
nome, ano_nasc
alunos A, cadeiras C, inscrições INS
nome_cadeira=‘Tecnologias dos Computadores’ AND
INS.ano = 1998
AND
C.num_cadeira = INS.num_cadeira
AND
INS.num_aluno = A.num_aluno
TC – DEI, 2005/2006
Queries - SQL
As queries em SQL também retornam tabelas
 SELECT
FROM
WHERE
nome, ano_nasc
alunos A, cadeiras C, inscrições INS
nome_cadeira=‘Tecnologias dos Computadores’
INS.ano = 1998
C.num_cadeira = INS.num_cadeira
INS.num_aluno = A.num_aluno
NUM_ALUNO
NOME
MORADA
ANO_NASC
501000885
José António
R. D. Carlos I, 126, 3000-204
Coimbra
1980
501003426
Carlos Alberto
R. Alexandre Herculano, 12A,
3030-123 Coimbra
1982
505404534
...
6
José Malaquias
7
2
R. Pinhal Marrocos, 43, 3030-290
Coimbra
NUM_INSC
1232
...
NOME_CADEIRA
1
ANO
SEMESTRE
1
Tecnologias dos Computadores
1
1
3
Programação e Algoritmos II
1
2
NUM_CADEIRA 6 NUM_ALUNO Sistemas
ANO Operativos
NOTA
2
1
...
...
3243
4321
7
1981
NUM_CADEIRA
...
…
3
1998…
1
... 501000885
3
501000885
1998
12
NOME
ANO_NASC
José António
1980
Carlos Alberto
1982
4
13
1
501003426
1998
3487
6
505404534
1999
NULL
...
...
...
...
...
5
AND
AND
AND
19
TC – DEI, 2005/2006
Inserção de Dados - SQL
Também se podem inserir dados na
base-de-dados…
INSERT INTO
VALUES
alunos
(num_aluno, nome, morada, ano_nasc)
(5010034322,
‘Teresa Matos’,
‘R. Alforrecas, 12, 3000-203 Coimbra’,
1984)
TC – DEI, 2005/2006
Recordemos…
ODBC
Aplicação
Base
de
Dados
SGBD
(Sistema de
Gestão de BD)
SELECT nome FROM alunos
O que viaja na ligação são estas
“ordens”, na linguagem SQL. A
aplicação tem de enviar as suas
ordens nesta linguagem e
processar os resultados
retornados
TC – DEI, 2005/2006
Criação de Bases-de-Dados
Na prática, quando se quer fazer uma base-dedados, não se começa por criar tabelas…
 Cria-se (modela-se) o problema:
Modelo CONCEPTURAL da Base-de-dados
 Para criar o modelo conceptual da Base-de-dados,
utilizam-se Diagramas ENTIDADERELACIONAMENTO (Diagramas ER)
Só após se ter o diagrama EntidadeRelacionamento é que se criam as tabelas:
 MODELO FÍSICO da Base-de-dados
 Muitas vezes, as ferramentas permitem passar
automaticamente do modelo conceptual para o
modelo físico
TC – DEI, 2005/2006
Modelo Entidade-Relacionamento
Modela o problema em termos de ENTIDADES e RELAÇÕES
entre entidades
As relações podem ser de:
 1 para 1 (1:1)
 1 para N (1:N)
 N para N (N:N)
As relações podem ter participação obrigatória ou não
ALUNO
N
Inscrito
N
CADEIRA
1
Possui
N
TESTE
TC – DEI, 2005/2006
Leitura do ER
Cada aluno pode estar inscrito em várias
cadeiras; cada cadeira pode ter vários alunos
inscritos
Cada aluno tem de estar obrigatoriamente
inscrito a uma cadeira; pode haver cadeiras
sem alunos (e.g. cadeiras que não funcionam
num ano)
Em cada cadeira pode haver vários testes;
cada teste só pode pertencer a uma cadeira
Pode haver cadeiras sem testes (e existem!);
Cada teste tem de ter obrigatoriamente uma
cadeira associada
TC – DEI, 2005/2006
Recordemos…
TC – DEI, 2005/2006
Informática é mais do que escrever código…
“The Mars Climate Orbiter
Spacecraft was lost
because one NASA team
used Imperial units while
another used metric units
for a key spacecraft
operation”
(BBC Online Report,
1999/09/30)
Mars Climate Orbiter, crashed into Mars on Sep 23, 1999
Cost  US$125 million dollars
TC – DEI, 2005/2006
Transacções em BDs – Motivação
REDE
Base
de
Dados
“Transfere €1.000.000 da conta
43248932 para a conta 43298743”
1:
2:
3:
4:
5:
boolean ok = conta1.retira(1000000);
if (ok)
{
conta2.coloca(1000000);
}
-- E se a aplicação “crasha” na linha 2??
-- E se deixa de haver ligação de rede na linha 4??
-- E se o servidor “crasha” entre a linha 1 e 2??
TC – DEI, 2005/2006
Transacções em BDs
Uma das razões muito importantes para se
utilizar BDs, para além da performance, é o ter
garantias de integridade de dados
Transacção: uma conjunto de operações que
devem ser executadas de forma indivisível (i.e.
atómica)
 Uma operação atómica é aquela em que ou executa
tudo ou não executa nada
 As base-de-dados têm suporte directo para
transacções
TC – DEI, 2005/2006
Transacções
Transacção
 Tem um início bem definido
 Ou existe um COMMIT ou
um ROLLBACK
 COMMIT  As alterações
tornam-se permanentes
 ROLLBACK  As alterações
são anuladas
Durante uma transacção,
as alterações na BD
apenas são visíveis para o
utilizador que as está a
fazer.
(...)
trans.beginTransaction();
boolean ok =
conta1.retira(1000000);
if (ok)
{
conta2.coloca(1000000);
trans.commitTransaction();
}
else
trans.rollbackTransaction();
 Todos os outros utilizadores
vêem os dados como se
nada estivesse a acontecer
TC – DEI, 2005/2006
Transacções – Ideia da Implementação
Sempre que um utilizador inicia uma
transacção, todos os dados sobre os quais
trabalha são privados (é feita uma cópia)
Quando é feito o COMMIT da transacção, a BD
é então actualizada
 No caso de haver conflito no acesso a dados, pode
ser necessário suspender temporariamente outras
transacções
Dentro da transacção: é
criada uma cópia de todos
os dados que estão a ser
actualizados
COMMIT: Actualiza-se
ROLLBACK: Deita-se fora
TC – DEI, 2005/2006
Para saber mais…
Computer Science – An Overview
 Capítulo 8 (8.1, 8.2, 8.3)
 Capítulo 9 (9.1, 9.2, 9.3)
Computer Science Illuminated
 Capítulo 11 (11.1, 11.2)
 Capítulo 12 (12.1, 12.3)
TC – DEI, 2005/2006