Como andam as suas Relações?
Tags: math, set, theory, graph
Published: 2024-04-24 12:41:40

# 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:
```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)}`

![Grafo como Relação](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4r1o3c8fhtqhfdktsrj7.png)

## 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 Reflexivo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i48p6hxfjjnj44jl58n0.png)

## 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 Transitivo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kpjqj0mvt9sh78uq5ca8.png)

## 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.

![Fecho Simétrico](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/08c2qcfxvnxdvs9utiro.png)

## 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.