Código Natural/Identificação taxonômica
Identificadores únicos, tais como contadores sequenciais em bases de dados, são fundamentais para a indexação e controle de registros. O ideal, todavia, é que esse identificador traga embutida alguma informação relativa à taxonomia da entidade identificada. Isso porque os identificadores de grupos taxonômicos também precisam ser únicos e padronizados.
A ilustração do conjunto de frutas ajuda a entender os agrupamentos (taxons).
Taxonomias bit a bit
A cada prefixo pode-se expressar uma regra. Por exemplo:
- Primeiro bit do ID: define se é laranja (1) ou maçã (0).
Os conjuntos L dos identificadores de laranjas e M das maçãs da ilustração ao lado são definidos por: e .
- Primeiro bit do ID de maçã: especializa como vermelha (0) ou verde (1). Portanto IDs com prefixos "00" (maçã red), "01" (maçã green) e "0" para maçã genérica. Daí rotular uma maçã com ID "0" é uma falha, é um código exclusivo de taxon.
Os conjuntos R dos identificadores de maçãs red e G das maçãs green da ilustração ao lado são definidos por: e . Ambos subconjuntos de M, estabelecendo portanto uma hierarquia taxonômica entre as maçãs.
Os identificadores de frutas são livres, podem ter qualquer quantidade de bits, podem ter tamanho fixo ou variável, e não precisam percorrer uma sequência especial. A taxonomia só impõe a existência de prefixos e regras de interpretação para esses prefixos.
A sintaxe geral da cadeia de bits é simples: "$prefixo$contador
". Com as variáveis prefixo e contador, tendo apenas o prefixo um comprimento definido pelas regras taxonômicas.
Se o conjunto dos identificadores de fruta for ordenado lexicograficamente (preorder), cada taxon corresponderá a um único intervalo. Lembrando que os taxons são os "ramos da árvore taxonômica", associados aos prefixos. Na ilustração os IDs de maçã estão no intervalo 0
até 011
, o subconjunto das maçãs verdes no subintervalo 01
até 011
, e os IDs de laranja de 1
até 111
.
Como boa prática para identificação pode-se evitar IDs com contador vazio: os IDs da ilustração saltam os códigos 0
, 1
e 01
.
Reserva de bits para o prefixo do contador
No exemplo acima as laranjas fizeram uso de um prefixo de apenas 1 bit e as maçãs uso de um prefixo de 2 bits.
Se a taxonomia é sujeita a modificações, podemos reservar mais bits para cada um dos grupos taxonômicos (taxons).
No exemplo poderíamos no futuro distinguir laranjas, entre comuns e avermelhadas. Todas elas com prefixo 1
mas reservando mais bits para futuras diferenciações: duas estratégias são possíveis:
- Se as existentes são comuns, batizamos elas de
10
e reservamos11
para as avermelhadas. Não fica nenhuma reserva de segurança.
- Se as existentes são misturadas, batizamos a mistura de
100
e reservamos101
para as identificadas como comuns e110
para as avermelhadas; ficando ainda a reserva111
para outra eventual variedade de laranja.
Quanto maior o risco de uma futura diferenciação, maior a demanda por reserva.
Prefixos lexicográficos
Na sintaxe "$prefixo$contador
", o prefixo é necessariamente um código e a contagem para identificação dos taxons é necessariamente lexicográfica. Ver função hsucc em step01def-lib_NatCod.sql. Exemplos:
- Dois taxons requerem no mínimo 1 bit. O primeiro é hsucc("")="0", o segundo é seu sucessor, hsucc("0")="1".
- Dois taxons com reserva de 2 bits, requerindo portanto 3 bits. Com reserva balanceada: taxons "001" e "101".
- Três taxons e todos com até 5 subtaxons cada. Pode-se adotar um prefixo de 2 bits fixos para os pais, mais dois variáveis para os filhos, ou balancear valores de zero a 3*5=15 entre 4 ou mais bits.
Contadores numéricos
Na sintaxe "$prefixo$contador
", o contador pode ser representado como número. Computacionalmente o ID é um código, seu prefixo um código, e por fim o contador, depois de isolado (ainda como código) pode sofrer cast para um número inteiro positivo.
Sendo um número, podemos calcular o sucessor succ($contador)
através da aritmética usual, $contador+1
.
Contadores lexicográficos
Na sintaxe "$prefixo$contador
", o contador pode ser mantido como código.
Sendo um código, podemos calcular succ($contador)
através do "sucessor lexicográfico" (também denominado "hierarchical successor"). Ver função hsucc em step01def-lib_NatCod.sql.
Taxonomias Base N
O caso mais simples é a Base4, com dígitos de 2 bits. É necessário então reservar no mínimo 2 bits para a taxonomia. Aqui adotamos a estratégia de reserva de apenas um bit para a diferenciação das laranjas, e mais um bit para a diferenciação das maçãs.
A conversão para Base4h resulta na segunda coluna da tabela abaixo, com prefixos em negrito, e conjunto "Green apples" ilustrado.
Base2h Base4h Taxon 00 0 Red Apple (illustrated) 000 0G Red Apple (illustrated) 0000 00 Red Apple (illustrated) 0001101 012Q Red Apple 0010101 022Q Red Apple 01 1 Green apple (illustrated) 0101 11 Green apple 010 1G Green apple (illustrated) 011 1Q Green apple (illustrated) 10 2 Organge (illustrated) 10101 22Q Organge 1011 23 Organge 101 2Q Organge (illustrated)
Atribuição dos IDs dentro de uma taxonomia
- Supor que a partir de k bits, digamos k=4, seja possível destacar prefixos válidos para conjuntos e subconjuntos alinhados.
Imaginemos o caso de uma pequena loja de departamentos, que começou por organizar os produtos mais vendidos: frutas e roupas. Entre as frutas, as mais vendidas são as maçãs, e entre as roupas, os jeans, as camisetas e alguns tipos de roupa feminina.
Olhando para a "régua base 4h" acima decidimos que frutas ficarão todas com o prefixo 0
, sendo as maçãs com 00
e as demais frutas com prefixos 01
, 02
e 03
. Os prefixos 1 e 2
ficam reservados a outros produtos, e o prefixo 3
ficou com as roupas.
Cada uma dessas classes de produtos foi destacado abaixo num diagrama de conjuntos, e os prefixos eleitos indicados no ponto interior mais à esquerda de cada conjunto. No ponto interior mais à direita, o limite superior que uma instância daquela classe de produto pode receber como identificador único.
Neste cenário, no inventário inicial foram suficientes 11 bits para identificar todos os produtos com seus prefixos. Por exemplo os IDs das maçãs vermelhas ficaram no intervalo 000
até 00033Q
. A ampliação do banco de dados, adotando o dobro, 22 bits, acarretou a ampliação do intervalo da mesma classe, seus IDs passaram a ser de 000
até 00033333333
. O aumento de bits não afeta os identificadores, apenas amplia a possibilidade de incluir mais produtos dentro da mesma classe.
Identificadores sem contador
A sintaxe "$prefixo$contador
" não deve ser confundida com a sintaxe interna do prefixo. Havendo necessidade de se identificar apenas os grupos taxonômicos, com sua hierarquia, podemos fazer uso do prefixo como identificador,
Prefixo e contador ao mesmo tempo
Exemplo. Ao identificar as partições recursivas de um quadrado, estamos identificando as células (como instâncias) e os taxons ao mesmo tempo. Abaixo usando a base4 para rotular. A célula "0" tem as filhas "00", "01", "02" e "03".
Modelagem dos níveis hierárquicos
Uniforme vs heterogêneo...
- Por base N de referência: exemplo do geocódigo quadrilátero que precisa preserva compatibilidade com a base4
- Por agregação: ... junta 2 ou mais níveis hierárquicos da base N para obter um nível...