Joao Brietzke Blog

← voltar

Uma peça troca tudo: por que agrupar e ordenar são a mesma estrutura

14 de jul. de 2026 — #matematica-discreta

Agrupar (GROUP BY, particionar) e ordenar (build, deps, sort) são a mesma estrutura matemática: uma relação com três propriedades. Trocar uma única peça, de simétrica para antissimétrica, leva de juntar em baldes a organizar em fila.

Todo dev faz duas coisas o tempo todo. Agrupa (GROUP BY, particionar, juntar o que é parecido) e ordena (resolver dependências de build, sort, decidir o que vem antes). A gente aprende as duas separadas, como se fossem truques diferentes. Não são.

Agrupar e ordenar são a mesma estrutura matemática, uma relação com três propriedades, e a diferença entre elas é uma peça trocada. Trocou a peça, saiu de "juntar em baldes" pra "organizar em fila". Este post é sobre essa peça.

A ideia central que atravessa tudo: uma relação é só uma lista de setas. "a se relaciona com b" é uma seta a → b. Cada propriedade é uma pergunta sobre o desenho das setas. Só isso.

Antes de tudo: conjunto e relação

Pra tudo que vem a seguir fazer sentido, dois conceitos precisam estar no lugar. São simples, e você já usa os dois no código sem chamar pelo nome.

Um conjunto é uma coleção de coisas, sem repetição e sem ordem. {1, 2, 3} é um conjunto. No código, é o Set: joga elementos dentro, os repetidos somem, e a ordem não importa pra dizer se dois conjuntos são iguais. É "quem está no clube", nada mais.

Uma relação é o passo seguinte: em vez de perguntar "quem está no clube?", ela pergunta "quem está ligado a quem?". Você anota cada ligação como um par, e a relação é a coleção desses pares. "Ana mora em SP, Bia mora no RJ" vira:

moraEm = { (Ana, SP), (Bia, RJ) }

Cada par é uma ligação; a lista inteira é a relação. E aqui está a ponte que você provavelmente já intuía: isso é exatamente uma tabela de banco de dados. Cada linha é um par, a tabela inteira é a relação. Não é coincidência que bancos SQL sejam chamados de "relacionais": eles são construídos sobre relações nesse sentido matemático.

De onde vêm os pares possíveis? De todas as combinações. Com Pessoas = {Ana, Bia} e Cidades = {SP, RJ}, existem quatro combinações possíveis (o produto cartesiano). A relação "mora em" é o recorte das que são verdade:

combinações possíveis        a relação "mora em"
(o produto cartesiano)       (só as verdadeiras)
  (Ana, SP)  ← verdade          { (Ana, SP),
  (Ana, RJ)                       (Bia, RJ) }
  (Bia, SP)
  (Bia, RJ)  ← verdade

Ou seja: uma relação é um subconjunto do produto cartesiano. O produto é o "possível" (todas as combinações), a relação é o "verdadeiro" (as que você marca). Quem decide o que é verdade é uma regra: "mora em" marca os pares onde a pessoa de fato mora na cidade; "é menor que" marca os pares de números onde o primeiro é menor; e assim por diante.

O caso mais rico, e o que interessa neste post, é quando a relação liga um conjunto com ele mesmo: pessoas com pessoas ("é amigo de", "segue"), números com números ("≤", "<"), módulos com módulos ("depende de"). É aí que a relação ganha propriedades, e são essas propriedades que decidem se ela agrupa ou ordena. É pra elas que vamos agora.

Âncora: conjunto = quem está no clube. Relação = quem está ligado a quem (uma lista de pares, igual a uma tabela). O resto do post é sobre o formato dessas ligações.

O tronco: reflexiva + transitiva

Antes da peça que troca, existe a base que não troca: duas propriedades que tanto o agrupar quanto o ordenar têm em comum.

Reflexiva. Todo elemento tem uma seta pra si mesmo (um lacinho a → a). A pergunta é: todo mundo se relaciona consigo próprio?

Transitiva. Todo atalho de dois pulos tem o pulo direto. Se dá pra ir a → b → c, então existe a → c. A pergunta é: o caminho encadeia?

reflexiva (o lacinho):        transitiva (o atalho):
  a ↺                           a → b → c
  b ↺                                 ⇒
  c ↺                           a ───────→ c   (o direto existe?)

Essas duas juntas capturam uma ideia de "alcançar": você já está onde está (reflexiva) e caminhos se emendam (transitiva). É a espinha de acessibilidade, herança de tipos e resolução de dependências. Guarde: este é o tronco. O que vem a seguir é escolher uma terceira propriedade pra colocar em cima dele.

Cuidado: transitiva não é "encadear qualquer coisa". "É pai de" encadeia (pai do pai), mas o resultado é avô, não pai, uma relação diferente. Transitiva exige que a mesma relação chegue direto no fim. Se a → b → c não te dá a → c da mesma relação, não é transitiva. Âncora: transitiva = "a mesma seta chega no destino", não "existe algum caminho".

A bifurcação

Em cima do tronco, cabe uma de duas peças. E cada uma leva a um lugar oposto:

              reflexiva + transitiva
                       │
          ┌────────────┴─────────────┐
      + SIMÉTRICA              + ANTISSIMÉTRICA
          │                         │
     EQUIVALÊNCIA              ORDEM PARCIAL
      "agrupar"                 "ordenar"
     GROUP BY, shard            build, deps, sort

As duas peças são quase opostas, e é por isso que o destino muda tanto:

  • Simétrica: "se a seta vai, ela sempre volta" (a → b obriga b → a). A volta é obrigatória.
  • Antissimétrica: "se vai e volta entre coisas diferentes, é proibido" (a → b e b → a só se a for o próprio b). A volta é proibida.

Uma exige a volta, a outra proíbe. Essa é a peça. Vamos ver cada ramo.

Ramo 1: simétrica → equivalência ("agrupar")

Pega a relação "tem o mesmo signo que". Ela tem o tronco (reflexiva: você tem o mesmo signo que você; transitiva: se A e B compartilham signo e B e C também, os três compartilham) e ganha a peça simétrica (se A tem o signo de B, B tem o de A, sempre volta).

Quando as três agem juntas, elas forçam as pessoas a se organizarem em baldes fechados. Repara no mecanismo:

Ana ─ Áries ─ Bia        (mesmo signo: conectam)
Bia ─ Áries ─ Caio       (mesmo signo: conectam)
      ⇒ (transitiva)  Ana e Caio TÊM que se conectar
      ⇒ (simétrica)   todas as conexões são mão-dupla

resultado: todo Áries ligado a todo Áries, e a ninguém de fora.

Isso é uma classe de equivalência: um balde fechado. E o conjunto inteiro vira uma coleção de baldes:

{ Áries: Ana, Bia, Caio }   { Touro: Duda }   { Gêmeos: Eva, Fábio }

A propriedade que sai de graça: esses baldes particionam o conjunto. Nada sobra (todo mundo tem signo) e nada se sobrepõe (ninguém tem dois). Cada elemento cai em exatamente um balde, e isso não é sorte da implementação, é a matemática das três propriedades garantindo.

// "mesmo signo" particiona em baldes. Isto É um GROUP BY
const baldes = {};
for (const p of pessoas) (baldes[p.signo] ??= []).push(p.nome);
// { Áries: ["Ana","Bia","Caio"], Touro: ["Duda"] }  ← as classes

Toda vez que você escreve GROUP BY, particiona um banco por shard key, ou deduplica por uma chave, está usando uma relação de equivalência. A garantia de que "agrupar sempre dá grupos sem sobra e sem sobreposição" vem daqui.

Cuidado: toda relação "tem o mesmo ___" é equivalência automática. Mesma cidade, mesma idade, mesmo CEP, mesmo signo. Reflexiva (você compartilha o "mesmo ___" consigo), simétrica (compartilhar é mão-dupla) e transitiva (compartilhar encadeia) saem de brinde. Âncora: "mesmo ___" = agrupar = GROUP BY.

Ramo 2: antissimétrica → ordem parcial ("ordenar")

Agora troca só a peça do meio. Em vez de simétrica (volta obrigatória), coloca antissimétrica (volta proibida entre diferentes). As setas, que antes iam e voltavam formando baldes, agora apontam num sentido só. E sentido significa ordem.

Pega "A depende de B" entre módulos. Tronco presente (reflexiva: um módulo "depende de si"; transitiva: se A precisa de B e B de C, A precisa de C). A peça nova, antissimétrica, diz: se A depende de B, B não pode depender de A, senão é um ciclo.

Sem voltas, não há baldes. Há cadeias com direção:

app ──→ react ──→ scheduler
(app vem "no topo"; scheduler é a "base")

Surge um antes e um depois. E o "parcial" é a parte que interessa: nem todo par é comparável. Dois módulos independentes não têm seta entre si, são incomparáveis:

        app
       /   \
    react  lodash     ← react e lodash: nenhum depende do outro
       \   /             (ramos paralelos, incomparáveis)
      shared-utils

Isso é um DAG (grafo direcionado sem ciclos). "Achatar" essa hierarquia numa sequência executável de build é a ordenação topológica, exatamente como o npm, o make e o webpack decidem em que ordem processar as coisas.

Cuidado: "parcial" não é "quebrada/incompleta". Quer dizer que comparar tudo com tudo não faz parte da definição: existem ramos paralelos legítimos. Forçar uma fila única onde há incomparáveis é erro de modelagem. Você tem um grafo, não uma lista. Âncora: antissimétrica dá direção (sem ciclo) → hierarquia/DAG → ordenar.

A peça que troca o destino

Aqui está tudo numa imagem. Mesmo tronco (reflexiva + transitiva). Troca uma propriedade e o objeto inteiro vira outro:

equivalência ordem parcial
a peça trocada simétrica (volta obrigatória) antissimétrica (volta proibida)
o que as setas fazem conectam em baldes fechados apontam num sentido (direção)
a estrutura que nasce partição (baldes disjuntos) hierarquia / DAG
o efeito agrupar ordenar
no seu código GROUP BY, sharding, dedup build, import, sort topológico, herança
exemplos mesma cidade, mesma idade, mesmo signo ≤, ⊆, "depende de", versões

A simetria diz "estamos juntos", sem direção, então grupos. A antissimetria diz "eu venho antes de você", com direção, então fila ou árvore. É literalmente a diferença entre juntar o parecido e organizar em ordem: as duas operações que você mais faz, reveladas como a mesma estrutura com uma peça diferente.

Por que isso importa no dia a dia

Você não vai desenhar um schema pensando "deixa eu verificar a antissimetria". Mas as perguntas que você já faz são essas propriedades disfarçadas:

  • "Modelo esse relacionamento como uma linha ou duas?" é simetria. Amizade (simétrica) é uma linha lida nos dois sentidos; "seguir" (não-simétrica) precisa de duas.
  • "Isso pode ter ciclo?" é antissimetria. Se "depende de" admitisse volta, o build entraria em loop. A antissimetria é a condição de "sem ciclos".
  • "Dá pra enfileirar tudo ou é um grafo?" é parcial vs total. Se há incomparáveis, é ordem parcial (DAG), não uma lista ordenada.
  • "Esse agrupamento cobre tudo sem sobrepor?" é equivalência. As três propriedades garantem baldes disjuntos que cobrem o conjunto.

Ter o nome não é decorar jargão, é reconhecer o padrão em vez de redescobrir na tentativa e erro. É a diferença entre "achei que precisava de recursão aqui" e "essa relação é transitiva, logo preciso do fecho transitivo".

Resumo

  • Uma relação é uma lista de setas. Cada propriedade é uma pergunta sobre o desenho delas.
  • Reflexiva + transitiva é o tronco comum: a ideia de "alcançar".
  • Adiciona simétrica (volta obrigatória) e vira equivalência, que particiona em baldes: agrupar (GROUP BY).
  • Adiciona antissimétrica (volta proibida) e vira ordem parcial, uma hierarquia com incomparáveis (DAG): ordenar (build, deps, sort topológico).
  • A diferença entre as duas maiores operações do seu dia, agrupar e ordenar, é uma única peça trocada sobre a mesma base.

A frase pra levar: mesma base, troca uma peça, muda o destino. Simétrica agrupa, antissimétrica ordena.