Skip to content. | Skip to navigation

Personal tools

Navigation

You are here: Home / Teaching / ci218 / CI218 - Trabalho prático 1

CI218 - Trabalho prático 1

Forma Normal de Boyce-Codd (BCNF)

 

Neste trabalho, iremos implementar o algoritmo de decomposição na BCNF dado um conjunto de dependências funcionais (DFs).

Algoritmo de decomposição na BCNF

 

  • Calcular as chaves da super relação R0 (via algoritmo do fecho);
  • Repita até que todas as relações decompostas de R estejam na BCNF
    • Escolha qualquer Rn com X -> Y que viola a BCNF (inicialmente n=0);
    • Decompor Rn em R1(X, B) e R2(Y, Resto);
    • Calcular as DFs para R1 e R2;
    • Calcular as chaves para R1 e R2;

Exemplo:

Dado a super relação: R0(cpf,nome,ender,Ecodigo,Enome,Ecidade,IRA,prioridade)

Dado a seguinte lista de DFs:

  1. Ecodigo->Enome,Ecidade
  2. IRA->prioridade
  3. cpf->nome,ender,IRA

Chave via algoritmo do fecho: {cpf, Ecodigo}+

Decomposição iniciando pela DF1 em R0:

  • R1(Ecodigo,Enome,Ecidade)
  • R2(cpf,nome,ender,Ecodigo,IRA,prioridade)
  • R3(IRA,prioridade)
  • R4(cpf,nome,ender,Ecodigo,IRA)
  • R5(cpf,nome,ender,IRA)
  • R6(cpf,Ecodigo)

Resposta (relações decompostas na BCNF, incluindo a super relação R0):

  • R0(cpf,nome,ender,Ecodigo,Enome,Ecidade,IRA,prioridade)
  • R1(Ecodigo,Enome,Ecidade)
  • R3(IRA,prioridade)
  • R5(cpf,nome,ender,IRA)
  • R6(cpf,Ecodigo)

 

Entrada:

A entrada deve ser feita pela entrada padrão (stdin). O arquivo é formado por uma sequência de linhas, onde cada linha representa uma DF no formato X->Y  (o subconjunto de atributos "X" que determina funcionalmente o subconjunto de atributos "Y"). Cada linha tem 2 campos: o primeiro campo representa o subconjunto de atributos "X" separados por virgula. O segundo campo representa o subconjunto de atributos "Y" separados por virgula. Os caracteres "->" determinam a separação dos subconjuntos "X" e "Y".  A ordem das DFs é usada para realizar a decomposição.

Saída:

A saída deve ser feita pela saída padrão (stdout). O arquivo será composto por uma sequência de linhas. Uma linha para cada relação decomposta onde Rn, com n >=1, é o nome da relação decomposta. Cada linha tem o seguinte formato: Rn(atributo1,atributo2,...,atributoM). A relação "R0" define a super-relação que deve ser apresentada à partir das DFs. A saida será ordenada por "n".

Exemplo de arquivos com uma entrada e uma saída válida:

Entrada Saída

Ecodigo->Enome,Ecidade

IRA->prioridade

cpf->nome,ender,IRA

R0(Ecodigo,Enome,Ecidade,IRA,prioridade,cpf,nome,ender)

R1(Ecodigo,Enome,Ecidade)

R3(IRA,prioridade)

R5(cpf,nome,ender,IRA)

R6(cpf,Ecodigo)


 

Requisitos mínimos:

O trabalho deve ser feito de forma que possa ser compilado e executado nas servidoras de computação do Departamento de Informática. Além disso, o executável não deve ter nenhuma opção de linha comando. O nome do executável deve ser: bcnf.

O que deve ser entregue:

Além dos arquivos fonte, deve acompanhar um makefile e a documentação sintetizada do sistema implementado. Qualquer particularidade deve estar descrita neste texto. Para compilar será usado o comando make (sem nenhum parâmetro), portanto preparem o Makefile para fazer isso. Para testar será executado um script como o abaixo.

     $ bcnf < teste.in > teste.out

Onde teste.in é o arquivo de entrada do teste e teste.out é o esperado como saída.

Forma de entrega:

O trabalho deve ser empacotado em um arquivo login1-login2.tar.gz, onde login1-login2 é uma string com os logins dos integrantes da equipe nas servidoras do DInf. Ao descompactar este arquivo deverá ser criado um diretório de nome login1-login2 que conterá todos os demais arquivos. O make e o script acima deverão funcionar dentro deste diretório (não em subdiretórios).

Este arquivo deve ser enviado por e-mail ao endereço do professor (eduardo) com o assunto "CI218-trab1" (exatamente).

Equipe:

O trabalho pode ser feito em equipes de 1 (um) ou 2 (dois) alunos.