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

Requisito R1.4: escalabilidade dos códigos expressos em n bits, quando copiados para um tipo de dado ampliado, com n+a bits. O último sucessor de um prefixo original de n poderá expandir a bits no dado ampliado, fazendo uso dos seus sucessores, sem invadir outros prefixos.

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

N\in \{4,8,16,32\}

; 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 $X_{2}$ 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) de até 8 bits, ilustra problemas da Base4 e Base16.

(size,value)	BitString	Base4	Base16
(1,0)	`0`	?	?
(2,0)	`00`	0	?
(3,0)	`000`	?	?
(4,0)	`0000`	00	0
(5,0)	`00000`	00?	0?
(6,0)	`000000`	000	0?
(7,0)	`0000000`	000?	0?
(8,0)	`00000000`	0000	00
(8,1)	`00000001`	0001	01
(7,1)	`0000001`	000?	0?
(8,2)	`00000010`	0002	02
(8,3)	`00000011`	0003	03
(6,1)	`000001`	001	0?
(7,2)	`0000010`	001?	0?
(8,4)	`00000100`	0010	04
(8,5)	`00000101`	0011	05
...	...	...	...

Sempre que size for impar, não haverá como representar em Base4; para Base16 size precisa ser múltiplo de 4.

As interrogações na coluna "Base4" destacam a tentativa frustrada de representar as bitStrings com o algoritmo da notação posicional numérica da Base 4, mesmo permitindo zeros a esquerda. Os dígitos da Base4 tradicoinal usam necessariamente 2 bits, sendo indefinido o dígito restante quando a quantidade total é impar: 0, 000, 0000001, etc. possuem comprimento impar. Analogamente, como a Base16 requer 4 bits a cada dígito, fica sem representação para diversas bitStrings.

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 $N=2^{n}$ , com n variando de 2 (4=2²) a 5 (32=2⁵). 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, $n\_codes=2^{k+1}-2$ , 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

...

As operações de árvore podem estar subordinadas à ordenação, se levarmos em conta o potencial de algoritmos como o wikipedia:Nested set model.

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

Com a ordenação interna consistente também otimizamos o algoritmo do wikipedia:Nested set model, ...

Ver também