Código Natural/Requisitos e motivações
Todo código natural pode ser representado por uma cadeia de bits, mas nem por isso é uma cadeia de bits. O conjunto dos códigos naturais é munido de diversas operações e tipos alternativos de representação. A escolha das operações essenciais e tipos de representação relevantes é que estabelece o conceito de código natural.
A seguir os problemas motivadores e requisitos utilizados originalmente para se obter a definição das operações essenciais. Os requisitos são, indiretamente, soluções dos problemas.
Requisitos na representação interna
Códigos em um banco de dados podem ser identificadores ou simples atributos (ex. hashes de integridade). A aplicação mais importante é a identificação única, que, tradicionalmente, nos bancos de dados é implementada través de números naturais, ditos "seriais", tipicamente em 32 ou 64 bits.
- Requisito R1.1: ser um tipo de dado de n bits, com o código natural "embutido" em um número inteiro de comprimento m compatível, com diferença m-n a menor possível; e com implementações de alta performance em m=32 e m=64.
- Requisito R1.2: oferecer uma função "sucessor(x)", que retorna o próximo x numa listagem ordenada; da maneira análoga que um contador numérico de "+1".
- Requisito R1.3: permitir as ordenações lexicográfica (prioritária) e por nível (secundária).
Através da ordenação lexicográfica é possível associar conjuntos aninhados a intervalos, e portanto realizar operações hierárquicas de alta performance fazendo uso apenas dos identificadores. Por isso R2.3 é de grande importância para "identificadores inteligentes", que preservam informação sobre a sua hierarquia.
Requisitos na representação textual
- Ver definições adicionais em Código natural/Notação posicional.
Números binários são representações válidas da notação posicional numérica base2, e podem ser representados de forma mais compacta (mais amigável para o ser humano) através de bases maiores, tais como base8 (sistema octal) ou base10 (sistema decimal). Códigos, todavia, não possuem um sistema posicional adequado, não existe um padrão para se representar todos os códigos naturais, nem sequer na base4 é possível.
- Requisito R2.1. Essa "representação compacta e amigável para humanos" é necessária, e portanto é o primeiro requisito.
A escolha das bases mais adequadas, todavia, também requer justificativas: descritas em Código natural/Notação posicional, e resultam em um conjunto limitado de bases, as quais se tornam requisitos:
- Requisito R2.2. Oferecer representações nas bases N com ; principalmente base 16.
Outro problema é a ordem: listagens de códigos representados em outras bases, precisam seguir a mesma ordem que as listagens binárias, ou seja, a ordem lexicográfica natural dos bits. Isso porque códigos naturais, independentemente da representação, precisam exibir a ordem hierárquica, de modo que "ramos da hierarquia" fiquem listados dentro de um intervalo único. Em por exemplo iniciamos pelo 0, depois 00, depois 01, depois 1, etc. O ramo dos "filhos de 0" ficam ordenados no intervalo [0,00,01] da listagem lexicográfica. Os "filhos de 1" no intervalo [1,10,11].
- Requisito R2.3. A ordenação de texto orientada a diferentes idiomas, num banco de dados relacional, é conhecida como collation; portanto é necessário estabelecer a collations adequadas a cada base de representação textual do código natural.
Problemas na representação textual baseN
A tabela abaixo, listando códigos em sua ordem natural (lexicográfica da expressão bitString), ilustra problemas da Base4 e a solução Base4h, bem como a solução hbit.
(size,value) BitString Base4 Base4h hbitBitstring hbit (1,0) 0
? G 10
2 (2,0) 00
0 0 100
4 (3,0) 000
? 0G 1000
8 (4,0) 0000
00 00 10000
16 (5,0) 00000
? 00G 100000
32 (6,0) 000000
000 000 1000000
64 (7,0) 0000000
? 000G 10000000
128 (8,0) 00000000
0000 0000 100000000
256 (8,1) 00000001
0001 0001 100000001
257 (7,1) 0000001
? 000Q 10000001
129 (8,2) 00000010
0002 0002 100000010
258 (8,3) 00000011
0003 0003 100000011
259 (6,1) 000001
001 001 1000001
65 (7,2) 0000010
? 001G 10000010
130 (8,4) 00000100
0010 0010 100000100
260 (8,5) 00000101
0011 0011 100000101
261 ... ... ... ... ... ...
A coluna "hbitBitstring" é relativa à representação das bitStrings em formato "hidden bit", definido em [KraEtAll2019]. Consiste em acrescentar o 1
na frente da bitString, para que não lhe cortem os zeros à esquerda, ao interpretá-la como número inteiro positivo (em formato decimal na coluna hbit).
A coluna "Base4" é a tentativa (frustrada) de representar as bitStrings com o algoritmo da notação posicional numérica da Base 4. A coluna "Base4h" é a inovação proposta em [KraEtAll2019], que adaptou o algoritmo para expressar códigos ao invés de números, permitindo zeros a esquerda e quantidade variável de dígitos.
- Nota. Conjuntos finitos de códigos naturais sempre podem ser expressos como conjuntos de hbits, portanto através de números naturais. O conjunto de todos os Códigos Naturais todavia é infinito, e neste caso particular (com infinitos elementos), a representação hbit não é permitida pelo Teorema de Cantor. Portanto, matematicamente, size-value é um tradutor mais rigoroso para expressões em .
Tamanho do problema
Quantos códigos naturais de k bits deixam de ser representados na Base N?
Avaliando a seguir apenas bases com N em {4, 8, 16, 32} da RFC 4648 das aplicações da Internet e (base 4) das aplicações em geocódigos. São todas na forma , com n variando de 2 (4=22) a 5 (32=25). O valor de n fornece também o número de bits por dígito da base, por exemplo base N=8 temos n=3, portanto cada dígito da base 8 tem 3 bits.
Na tabela abaixo foram avaliadas experimentalmente as taxas de ocupação para diversos valores de k, resultando em uma quantidade de códigos, , e nas quantidades de representações válidas a cada base.
Base and occupancy rate of n_codes | |||||||||
k (bits) | n_codes | base4 | base8 | base16 | base32 | ||||
1 | 2 | 0 | 0% | 0 | 0% | 0 | 0% | 0 | 0% |
2 | 6 | 4 | 67% | 0 | 0% | 0 | 0% | 0 | 0% |
3 | 14 | 4 | 29% | 8 | 57% | 0 | 0% | 0 | 0% |
4 | 30 | 20 | 67% | 8 | 27% | 16 | 53% | 0 | 0% |
5 | 62 | 20 | 32% | 8 | 13% | 16 | 26% | 32 | 52% |
6 | 126 | 84 | 67% | 72 | 57% | 16 | 13% | 32 | 25% |
7 | 254 | 84 | 33% | 72 | 28% | 16 | 6% | 32 | 13% |
8 | 510 | 340 | 67% | 72 | 14% | 272 | 53% | 32 | 6% |
9 | 1022 | 340 | 33% | 584 | 57% | 272 | 27% | 32 | 3% |
10 | 2046 | 1364 | 67% | 584 | 29% | 272 | 13% | 1056 | 52% |
11 | 4094 | 1364 | 33% | 584 | 14% | 272 | 7% | 1056 | 26% |
12 | 8190 | 5460 | 67% | 4680 | 57% | 4368 | 53% | 1056 | 13% |
13 | 16382 | 5460 | 33% | 4680 | 29% | 4368 | 27% | 1056 | 6% |
14 | 32766 | 21844 | 67% | 4680 | 14% | 4368 | 13% | 1056 | 3% |
15 | 65534 | 21844 | 33% | 37448 | 57% | 4368 | 7% | 33824 | 52% |
16 | 131070 | 87380 | 67% | 37448 | 29% | 69904 | 53% | 33824 | 26% |
Average on stable cycle: | 50% | 33% | 25% | 20% | |||||
Loss, 100% - occupancy: | 50% | 67% | 75% | 80% |
Os valores percentuais foram calculados com relação a n_codes, as médias finais de occupancy com relação aos ciclos.
O comportamento da taxa de ocupação é cíclico e converge rapidamente, sendo destacado em negrito o primeiro ciclo estável de cada base. A média dentro do ciclo estável é a esperada pelo número de bits: em 2 bits (base 4) apenas os códigos de 1 bit deixam de ser representados, portanto 50%; em 3 bits (base 8) os códigos de 1 e 2 bits deixam de ser representados, portanto apenas 1/3 = 33% é representado; em 4 bits apenas 1/4=25% e em 5 bits apenas 1/5=20%.
Conclusão: nas bases de aplicação mais frequente (as bases 8 e 16), entre 67% e 75% dos códigos naturais deixam de ser representados. É uma perda muito grande, vale a penas investir numa solução.
Padronização da eventual solução
Conforme visto na definição dos códigos naturais, existe uma proposta de solução (propostas base 4h, base 8h e base 16h), mas ela permanece como proposta enquanto não foi aceita como padrão de fato para a "representação humana compacta" dos códigos naturais.
A padronização portanto é mais um problema da representação textual, o último obstáculo a ser vencido.
Problemas na representação interna e processamento
...
Problema da ordenação na representação interna
... Para ser amigável, evitando traduções, os códigos base-h devem ser representados por texto com collation especial. Supondo que a base-h seja um padrão, é natural propor um agrupamento para ela. Imagine definir uma coluna como representação base16h:...