Relações

2026-07-26 matematica-discreta banco-de-dados, algoritmos, compiladores basico

Relações

Uma relação captura a ideia de que elementos estão associados entre si. É a estrutura que aparece por trás de grafos, ordenações, hierarquias de tipos e do modelo relacional de bancos de dados — daí o nome.

Definição

Uma relação binária de $A$ em $B$ é um subconjunto $R \subseteq A \times B$. Escrevemos $a,R,b$ quando $(a,b) \in R$.

Quando $A = B$, dizemos que $R$ é uma relação sobre $A$. Este é o caso mais importante, e o que corresponde a um grafo dirigido: os elementos são vértices e os pares são arestas.

Propriedades

Seja $R$ uma relação sobre $A$:

Propriedade	Definição
Reflexiva	$\forall a, (a,R,a)$
Irreflexiva	$\forall a, \neg(a,R,a)$
Simétrica	$\forall a,b, (a,R,b \to b,R,a)$
Antissimétrica	$\forall a,b, (a,R,b \wedge b,R,a \to a = b)$
Transitiva	$\forall a,b,c, (a,R,b \wedge b,R,c \to a,R,c)$

Um cuidado: antissimétrica não é o mesmo que "não simétrica". A relação $\le$ é antissimétrica; $<$ é antissimétrica e irreflexiva ao mesmo tempo.

Relações de equivalência

Uma relação reflexiva, simétrica e transitiva é uma relação de equivalência. Ela captura a ideia de "ser igual para efeitos práticos".

O resultado central é que toda relação de equivalência sobre $A$ particiona $A$ em classes disjuntas cuja união é $A$, e reciprocamente toda partição define uma equivalência. Escreve-se $[a]$ para a classe de $a$, e $A/{\sim}$ para o conjunto das classes.

Exemplos:

Congruência módulo $n$: $a \equiv b \pmod n$ particiona $\mathbb{Z}$ em $n$ classes.
"Ter o mesmo tamanho" sobre um conjunto de cadeias.
"Estar no mesmo componente conexo" sobre os vértices de um grafo.

Em computação, uma equivalência é o que legitima usar um representante no lugar do objeto. É o que a estrutura union-find calcula, o que a minimização de autômatos explora ao fundir estados indistinguíveis e o que uma função de hash consistente exige: se dois objetos são equivalentes, seus hashes precisam coincidir.

Ordens parciais

Uma relação reflexiva, antissimétrica e transitiva é uma ordem parcial. O par $(A, \preceq)$ é um conjunto parcialmente ordenado.

"Parcial" significa que pode haver elementos incomparáveis — nem $a \preceq b$ nem $b \preceq a$. Quando todos os pares são comparáveis, a ordem é total.

Exemplos de ordem parcial:

$\subseteq$ sobre subconjuntos: ${1}$ e ${2}$ são incomparáveis.
Divisibilidade sobre inteiros positivos: $2$ e $3$ são incomparáveis.
Dependência entre tarefas: duas tarefas independentes não têm ordem entre si.

A ordenação topológica transforma uma ordem parcial numa ordem total compatível com ela. É o que um sistema de build faz para escolher a sequência de compilação, e o que um gerenciador de pacotes faz para ordenar a instalação. Se o grafo de dependências tiver ciclo, não é ordem parcial — e não há ordenação possível.

Composição e fechos

A composição de relações combina passos:

$$R \circ S = {(a,c) : \exists b, (a,S,b \wedge b,R,c)}$$

O fecho transitivo $R^+$ é a menor relação transitiva que contém $R$: existe caminho de $a$ a $b$ por uma ou mais arestas. O fecho reflexivo-transitivo $R^*$ inclui também os caminhos de comprimento zero.

O algoritmo de Floyd-Warshall calcula o fecho transitivo em $O(n^3)$:

def fecho_transitivo(adj, n):
    R = [linha[:] for linha in adj]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if R[i][k] and R[k][j]:
                    R[i][j] = True
    return R

Fecho transitivo responde a perguntas do tipo "esta tarefa depende, direta ou indiretamente, daquela?" — que é o que um analisador de impacto faz num repositório grande.

Exemplo trabalhado

Seja $R$ sobre ${1,2,3,4}$ dada por "$a$ divide $b$". Os pares são $(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)$.

Reflexiva: sim, todo número divide a si mesmo.
Simétrica: não — $1$ divide $2$, mas $2$ não divide $1$.
Antissimétrica: sim, entre positivos, $a \mid b$ e $b \mid a$ forçam $a = b$.
Transitiva: sim.

Logo $R$ é ordem parcial, mas não total: $2$ e $3$ são incomparáveis.

Aplicações em computação

Bancos de dados. Uma tabela é uma relação no sentido literal. Dependências funcionais entre atributos governam a normalização.

Union-find. Mantém classes de equivalência sob união com custo praticamente constante, e é o núcleo do algoritmo de Kruskal.

Sistemas de tipos. Subtipagem é uma ordem parcial. A transitividade é o que permite passar um Gato onde se espera um Animal.

Análise de dependências. Grafos de build, imports de módulos e migrações de banco são ordens parciais processadas por ordenação topológica.

Comparadores. Um comparador de ordenação precisa ser uma ordem total consistente. Um comparador que viola transitividade pode fazer o algoritmo de ordenação lançar exceção ou entrar em laço, e o defeito é notoriamente difícil de reproduzir.

Erros comuns

Confundir antissimetria com ausência de simetria.
Supor que toda ordem é total e esquecer os elementos incomparáveis.
Escrever um comparador não transitivo, tipicamente ao comparar por vários critérios de forma inconsistente.
Esquecer que igualdade e hash precisam concordar com a equivalência usada.

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512. Judith L. Gersting (2014). Mathematical Structures for Computer Science. W. H. Freeman. ISBN 9781429215107.

Referências

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
Judith L. Gersting (2014). Mathematical Structures for Computer Science. W. H. Freeman.