Como andam as suas Relações?

Relações

Introdução

Definição de Oxford

relação
substantivo feminino
1.vinculação de alguma ordem entre pessoas, fatos ou coisas; ligação, conexão, vínculo. "uma r. entre os dois crimes"

Pela definição da para se ter uma ideia, 'vinculacão de alguma ordem entre coisas'. Matematicamente falando, dentro da teoria dos conjuntos, uma relação binária em um conjunto A pode ser descrita como R(x,y) que pode ser verdadeira ou falsa para cada par ordenado (x,y) de elementos de A. Não se preocupe pois vamos destrinchar essa afirmacão acima.
Vamos entender através de um exemplo. Pense na relacão R, x divide y, ou seja, y é múltiplo de x. Agora pense num conjunto A = {2, 3, 4, 5, 6}, a relação R, x divide y, só é verdade para alguns pares ordenados desse conjunto A. Vejamos:

• o par (2,3) pertence à relacao R ? Falso, pois 2 não divide 3
• o par (2,4) pertence. Pois 2 divide 4
• o par (2,5) não pertence.
• o par (3,6) pertence, pois 6 é múltiplo de 3.
• o par (2,6) também pertence pelo mesmo motivo acima.

Ou seja, apenas os pares: {(2,4), (2,6), (3,6)} pertencem à relação R, x divide y.

Disclaimer: estou usando uma versão naive de teoria dos conjuntos. Os exemplos aqui demonstrados são todos finitos.

Formalmente falando: seja A um conjunto finito, uma relacão (binária) em A é um subconjunto de A x A. Ou seja, um subcojunto do produto cartesiano de A com A.
Essa operacão produto cartesiano se dá da seguinte forma:
Imagine um conjunto A = {1, 2, 3}, o produto cartesiano de A por A, A x A resulta no conjunto
A x A = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3))}

Seja A = {1, 2} e B = {a, b, c}, A x B = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}

Ora, por que uma Relação G em A está contida em A x A? Bem, como A x A produz TODOS os possíveis pares ordenados (x,y), obviamente qualquer relacão em A vai estar contida no seu produto cartesiano.
Os elementos individuais, por ex., (1,a) ou (2,c), são chamados de tupla. As relações podem ter várias cardinalidades, ou seja, a quantidade de elementos por tupla.
Uma relacão binária tem tuplas de tamanho 2, ternárias 3, e assim por diante.

O custo dessa operacão é O(m x n) onde m e n são os tamanhos dos conjuntos. Em outras palavras, uma operacao quadrática.

Ele faz a combinação de todos os elementos de 2 ou mais conjuntos.
Em pseudo Python:

def prod_cartesiano(c1, c2):
   res = [] 
   for i in c1:
      for j in c2:
         res.append((i,j))
   return res

Algumas definições importantes

Seja G uma relacao binária em A, então:

• G é reflexiva se para todo x pertencente à A, (x,x) pertence à G. Por ex., Se G for uma relacão sobre {1, 2}, e G for reflexiva, significa que G possui (1,1) e (2,2) como elementos.
• G é simétrica se para todo x e y pertencente a G, se (x,y) estiver em G, implica que (y,x) também estará.
• G é antissimétrica se, (x,y) pertence a G e (y,x) pertence a G, isso significa que x = y.
• G é transitiva se (x,y) pertence à G e (y,z) pertence à G, implica que (x,z) está em G.

Operacoes Clássicas

Seja G um grafo cujos vértices V são {a, b, c, d} e as arestas estão representadas na relação R: {(a,b), (a,c), (b,c), (c,d)}

Fecho Reflexivo

O fecho reflexivo visa adicionar novas tuplas na relação de forma que para todo x pertencente à V, (x,x) está em R.
Aplicando o fecho reflexivo na relação R acima, temos que adicionar as tuplas: {(a,a), (b,b), (c,c), (d,d)} na relação R.

R(reflexivo) = {(a,a)*, (a,b), (a,c), (b,b)*, (b,c), (c,c)*, (c,d), (d,d)*}

Fecho Transitivo

O fecho transitivo visa adicionar novas tuplas na relação de forma que, se (a,b) e (b,c) estiverem na relação, então precisamos adicionar (a,c) na relação, pois existe um caminho levando de a para b e de b para c.
R(transitivo) = {(a,b), (a,c), (b,c), (c,d), (a,d)*, (b,d)*}

Explicação:

• (a,d) entra na relação pois: (a,c) e (c,d) estão na relação R
• (b,d) entra na relação pois: (b,c) e (c,d) estão na relação R

Obs.: A implementação do fecho transitivo é a mais complicadinha e fica de exercício para o leitor =)

Fecho Simétrico

O fecho simétrico visa adicionar novas tuplas de maneira que, se (a,b) está em R, logo (b,a) também estará no fecho simétrico de R de modo que a != b.
No nosso exemplo acima, precisaremos adicionar as seguintes tuplas na relação:

• (b,a) entra no fecho pois: (a,b) pertence à R
• (c,a) entra no fecho pois (a,c) está em R
• (c,b) entra no fecho pois (b,c) está em R
• Finalmente, (d,c) está no fecho simétrico pois (c,d) está em R.

Sugiro vocês implementarem essas operações na linguagem de programação de vossa preferência.

Funções como relações

Funções também podem ser vistas como relações, obviamente nem toda relação configura-se como função, porém toda função pode ser escrita como uma relação.

Vejamos o seguinte exemplo:

Seja a função f: f(x) = x + 1 definidas para os Naturais N = {0,1,2,3,4,5,...}, podemos especificar uma relação R que contem todos os pares (x,y) que correspondem à função.
R = {(0,1), (1,2), (2,3), (3,4), (4,5), (5,6), ... }

Bancos de dados relacionais

No fim das contas, uma relação pode ser vista como uma tabela, tal qual os bancos de dados relacionais. Na verdade, toda a teoria matemática por trás dos bancos de dados relacionais foi baseada na teoria dos conjuntos e nas relações. O que temos é uma álgebra de relações, com operações específicas para filtrar linhas e colunas e fazer 'join' de relações ou tabelas (quando possível).
No próximo post eu vou focar um pouco mais na Álgebra Relacional.

Conclusões

Bem, chegamos ao fim de mais um Post aqui nesse blog aleatório. Como podemos ver as relações, no contexto da teoria dos conjuntos, tem aplicações práticas em diversas áreas, inclusive na lógica relacional (Alloy). Podemos representar diversas estruturas e até mesmo bancos de dados inteiros utilizando esse tipo de abstração. Um beijo de luz.

Comments

[Leandro Proença]

Sensacional o conteúdo, no aguardo de mais!