Archive for junho \21\UTC 2010

Dependências Funcionais

junho 21, 2010

Nesta série de posts, apresentarei os fundamentos de dependências funcionais e sua aplicação ao processo de especialização de tipos na linguagem Haskell. Dependências funcionais foram originalmente introduzidas há anos no estudo de bancos de dados relacionais [1]. Antes de apresentarmos a aplicação de dependências funcionais para a verificação / inferência de tipos, será feita uma breve revisão destes conceitos sob o enfoque da teoria de bancos de dados relacionais.

1 – Relações e Bancos de Dados Relacionais.

Um banco de dados relacional pode ser descrito como um conjunto de relações, onde cada uma destas pode ser vista como uma tabela com zero ou mais tuplas. A seguinte tabela, por exemplo, representa dados de uma consulta que representa os resultados de um questionário hipotético realizado com funcionários de uma empresa.

Nome Bairro Transporte
Alice Harbortown Automóvel
Alice Harbortown A pé
Bob Hillville Bicicleta
Bob Hillville Ônibus
Bob Hillville Automóvel
Carol Hubford Ônibus
David Hubford Trem

Esta tabela possui três colunas (campos) e sete tuplas (registros). Cada registro pode ser descrito por uma tupla (e,b,t) onde e é o nome de um empregado, b é um bairro e t é um meio de transporte. De maneira mais geral, um banco de dados pode ser descrito por um esquema que atribui um nome para cada tabela e também um nome (e possivelmente um tipo) para cada coluna.

Mais formalmente, uma tabela T é uma relação sobre uma família indexada de conjuntos \{D_{i}\}_{i\in I}, onde I é um conjunto de índices (i.e. conjunto de nomes de colunas) e D_{i} é o tipo dos valores da coluna i. Na tabela de exemplo apresentada anterioremente, o conjunto de índices  seria I=\{Nome, Bairro, Transporte \}. Os elementos desta tabela são tuplas, onde cada uma destas é uma família indexada de valores \{t_{i}\}_{i\in I} tal que t_{i}\in D_{i} para cada i\in I. Note que, se I=\{1,...,n\}, então (t_{1},t_{2},...,t_{n})\in D_{1}\times D_{2}\times ...\times D_{n}. Se i \in I, então escrevemos t_{i} para o i-ésimo componente de t. Similarmente, se X\subseteq I, então t_{X}  representa a projeção da tupla $t$ sobre as colunas c_{i}\in X.

2 – Dependências Funcionais

Um esquema de banco de dados irá tipicamente impor certas restrições de integridade para caracterizar a estrutura da informação que é permitida em tabelas do banco. Na tabela de exemplo apresentada anteriormente, é razoável assumir que cada funcionário resida em somente um bairro, isto é, na tabela acima um funcionário deverá estar associado a somente um bairro. Tal restrição é capturada através de uma dependência funcional, representada como \{ Nome \}\rightsquigarrow\{Bairro\}, que garante que dois registros do mesmo empregado devem ter o mesmo bairro associado. Todavia, não existe dependência similar entre os campos Nome e Transporte, uma vez que alguns funcionários utilizam mais de um meio de transporte. É tarefa do SGDB garantir que dependências são mantidas a medida que registros são incluídos ou atualizados. Como exemplo, considere a situação em que o funcionário David se mudasse do bairro Hubford para o bairro Hillville. Neste caso teríamos que a tupla t_{1}=(David, Hubford, Trem) deveria ser alterada para t_{2}=(David, Hillville, Trem), o que não violaria a dependência \{ Nome \}\rightsquigarrow\{Bairro\}. Mas, não poderíamos simplesmente incluir o registro t_{2}, uma vez que esta inclusão não atenderia a restrição especificada por \{ Nome \}\rightsquigarrow\{Bairro\}.

2.1 – Formalizando Dependências Funcionais

Formalmente, se T é uma tabela indexada por um conjunto I, então uma dependência funcional é um par X \rightsquigarrow Y, X determina Y, onde tanto X quanto Y são subconjuntos de I. Se X, Y são conjuntos de elementos conhecidos, isto é X=\{x_{1},x_{2},...,x_{n}\} e Y=\{y_{1},y_{2},...,y_{m}\}, podemos escrever a dependência X \rightsquigarrow Y como x_{1},x_{2},...,x_{n}\rightsquigarrow y_{1},y_{2},...,y_{m}. Se a tabela T satisfaz a dependência X \rightsquigarrow Y, então toda tupla em Y é unicamente determinada pelos valores correspondentes daquela tupla em X. Esta noção pode ser formalizada da seguinte maneira:

T\models X\rightsquigarrow Y \Leftrightarrow \forall t,s \in T. (t_{x} = s_{x})\Rightarrow (t_{y} = s_{y})

A relação T\models X\rightsquigarrow Y pode ser entendida como: “a tabela T satisfaz a dependência X\rightsquigarrow Y“. Uma extensão útil para esta notação é quando consideramos um conjunto de dependências:

T\models F \Leftrightarrow \forall (X \rightsquigarrow Y) \in F. T\models X\rightsquigarrow Y

Outra maneira de entender as dependências funcionais é por meio de regras de inferência para reflexividade, transitividade e acréscimo:

\frac{Y\subseteq X}{X\rightsquigarrow Y}

\frac{X\rightsquigarrow Y\,\,\,\, Y\rightsquigarrow Z}{X\rightsquigarrow Z}

\frac{X\rightsquigarrow Y}{X\cup Z\rightsquigarrow Y\cup Z}

Estas regras são frequentemente denominadas de axiomas de Armstrong, uma vez que William Armstrong[2] foi o primeiro a mostrar que estas são corretas e completas. Estas regras também podem ser estendidas para um conjunto de dependências; dizemos que F_{1}\vdash F_{2} se todas as dependências de F_{2} podem ser deduzidas a partir das dependências de F_{1}. Se F_{1}\vdash F_{2} e F_{2}\vdash F_{1} então os conjuntos de dependências F_{1} e F_{2} são equivalentes e podemos nos referir a uma destes como sendo a cobertura do outro conjunto de regras.

O fecho, J_{F}^{+}, de um conjunto J\subseteq I com respeito a um conjunto de dependências funcionais F é o menor conjunto tal que:

  • J\subseteq J_{F}^{+}
  • Se X\rightsquigarrow Y\in F, e X\subseteq J_{F}^{+}, então Y\subseteq J_{F}^{+}.

Intuitivamente, o fecho J_{F}^{+} é apenas o conjunto de índices que são unicamente determinados, seja direta ou indiretamente, pelos índices em J e as dependências em F.

Conclusão

Dependências funcionais são um conceito consolidado da teoria de bancos de dados relacionais. Neste post foi apresentado uma breve introdução aos principais conceitos relacionados a teoria de bancos de dados relacionais. Nos próximos posts será apresentada a aplicação destes conceitos para verificação / inferência de tipos na linguagem Haskell.

Referências

1 – E. F. Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6): 377-387, 1970.

2 – W.W. Armstrong. Dependency structures of data base relationships. In IFIP Congress, 580-583, 1974.