Representar pedidos em um banco de dados relacional
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho uma coleção de objetos em um banco de dados.Imagens de uma galeria de fotos, produtos de um catálogo, capítulos de um livro, etc.Cada objeto é representado como uma linha.Quero poder ordenar essas imagens arbitrariamente, armazenando essa ordem no banco de dados para que, quando eu exibir os objetos, eles estejam na ordem correta.
Por exemplo, digamos que estou escrevendo um livro e cada capítulo é um objeto.Escrevo meu livro e coloco os capítulos na seguinte ordem:
Introdução, acessibilidade, forma vs.Função, Erros, Consistência, Conclusão, Índice
Ele vai para o editor e volta com a seguinte ordem sugerida:
Introdução, Forma, Função, Acessibilidade, Consistência, Erros, Conclusão, Índice
Como posso armazenar essa ordenação no banco de dados de maneira robusta e eficiente?
Tive as seguintes ideias, mas não estou entusiasmado com nenhuma delas:
Variedade.Cada linha possui um ID de pedido, quando o pedido é alterado (por meio de uma remoção seguida de uma inserção), os IDs do pedido são atualizados.Isso facilita a recuperação, pois é apenas
ORDER BY, mas parece fácil de quebrar.// REMOVAL
UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
// INSERTION
UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
UPDATE ... SET orderID=insertionID WHERE ID=addedIDLista vinculada.Cada linha possui uma coluna para o ID da próxima linha na ordem.A travessia parece cara aqui, embora possa haver alguma maneira de usar
ORDER BYque não estou pensando.Matriz espaçada.Defina o orderingID (conforme usado no item 1) como grande, de modo que o primeiro objeto seja 100, o segundo seja 200, etc.Então, quando acontece uma inserção, basta colocá-la em
(objectBefore + objectAfter)/2.É claro que isso precisaria ser reequilibrado ocasionalmente, para que você não tenha as coisas muito próximas (mesmo com carros alegóricos, você acabaria encontrando erros de arredondamento).
Nada disso parece particularmente elegante para mim.Alguém tem uma maneira melhor de fazer isso?
Solução 9
Já que encontrei isso principalmente com Django, descobri esta solução para ser o mais viável.Parece que não existe uma "maneira certa" de fazer isso em um banco de dados relacional.
Outras dicas
Uma outra alternativa seria (se o seu RDBMS suportar) usar colunas do tipo array.Embora isso quebre as regras de normalização, pode ser útil em situações como esta.Um banco de dados que conheço que possui arrays é o PostgreSQL.
O mixin act_as_list no Rails lida com isso basicamente da maneira que você descreveu no item 1.Ele procura uma coluna INTEGER chamada posição (da qual você pode substituir pelo nome, é claro) e usa-a para fazer um ORDER BY.Quando você deseja reordenar as coisas, você atualiza as posições.Ele me serviu muito bem sempre que o usei.
Como observação lateral, você pode eliminar a necessidade de sempre fazer o reposicionamento em INSERTS/DELETES usando numeração esparsa - como o básico antigamente ...você pode numerar suas posições 10, 20, 30, etc.e se precisar inserir algo entre 10 e 20 basta inserir na posição 15.Da mesma forma, ao excluir, você pode simplesmente excluir a linha e deixar a lacuna.Você só precisa renumerar quando realmente alterar a ordem ou se tentar fazer uma inserção e não houver espaço apropriado para inserir.
Claro que dependendo da sua situação particular (por ex.quer você tenha as outras linhas já carregadas na memória ou não), pode ou não fazer sentido usar a abordagem de lacuna.
Apenas um pensamento considerando opção nº 1 versus nº 3:a opção de array espaçado (#3) não apenas adia o problema do array normal (#1)?Seja qual for o algoritmo que você escolher, ele está quebrado e você terá problemas com o número 3 mais tarde ou funciona e o número 1 também deve funcionar.
Se os objetos não forem fortemente codificados por outras tabelas e as listas forem curtas, excluir tudo no domínio e apenas reinserir a lista correta é o mais fácil.Mas isso não é prático se as listas forem grandes e você tiver muitas restrições para retardar a exclusão.Acho que seu primeiro método é realmente o mais limpo.Se você executá-lo em uma transação, pode ter certeza de que nada de estranho acontecerá enquanto você estiver no meio da atualização para estragar o pedido.
Fiz isso no meu último projeto, mas era para uma tabela que apenas ocasionalmente precisava ser ordenada especificamente e não era acessada com muita frequência.Acho que o array espaçado seria a melhor opção, pois reordenar seria mais barato no caso médio, envolvendo apenas uma alteração em um valor e uma consulta em dois).
Além disso, imagino que ORDER BY seria bastante otimizado pelos fornecedores de banco de dados, portanto, aproveitar essa função seria vantajoso para o desempenho, em oposição à implementação da lista vinculada.
Use um número de ponto flutuante para representar a posição de cada item:
Item 1 -> 0,0
Item 2 -> 1,0
Item 3 -> 2.0
Item 4 -> 3.0
Você pode colocar qualquer item entre quaisquer outros dois itens por simples bissecção:
Item 1 -> 0,0
Item 4 -> 0,5
Item 2 -> 1,0
Item 3 -> 2.0
(Item 4 movido entre os itens 1 e 2).
O processo de bissecção pode continuar quase indefinidamente devido à forma como os números de ponto flutuante são codificados em um sistema de computador.
Item 4 -> 0,5
Item 1 -> 0,75
Item 2 -> 1,0
Item 3 -> 2.0
(Mova o item 1 para a posição logo após o item 4)
Eu faria um número consecutivo, com um gatilho na mesa que “abre espaço” para uma prioridade caso ela já exista.
Eu tive esse problema também.Eu estava sob forte pressão de tempo (não estamos todos) e optei pela opção nº 1, e atualizei apenas as linhas que foram alteradas.
Se você trocar o item 1 pelo item 10, basta fazer duas atualizações para atualizar os números de pedido do item 1 e do item 10.Eu sei que é algoritmicamente simples e é O(n) pior caso, mas o pior caso é quando você tem uma permutação total da lista.Com que frequência isso vai acontecer?Isso é para você responder.
Tive o mesmo problema e provavelmente passei pelo menos uma semana me preocupando com a modelagem de dados adequada, mas acho que finalmente consegui.Usando o tipo de dados array no PostgreSQL, você pode armazenar a chave primária de cada item ordenado e atualizar esse array de acordo usando inserções ou exclusões quando seu pedido for alterado.Fazer referência a uma única linha permitirá mapear todos os seus objetos com base na ordem na coluna da matriz.
Ainda é uma solução um pouco instável, mas provavelmente funcionará melhor do que a opção nº 1, já que a opção 1 requer a atualização do número do pedido de todas as outras linhas ao solicitar alterações.
O Esquema #1 e o Esquema #3 têm a mesma complexidade em todas as operações, exceto INSERT escreve.Esquema #1 tem O(n) gravações INSERT e o Esquema #3 tem O(1) escritas INSERT.
Para todas as outras operações de banco de dados, a complexidade é a mesma.
O esquema nº 2 nem deveria ser considerado porque é DELETE requer O(n) leituras e gravações.Esquema #1 e Esquema #3 têm O(1) DELETE tanto para ler quanto para escrever.
Novo método
Se seus elementos tiverem um elemento pai distinto (ou seja,eles compartilham uma linha de chave estrangeira), então você pode tentar o seguinte ...
Django oferece uma solução independente de banco de dados para armazenar listas de inteiros dentro CharField().Uma desvantagem é que o comprimento máximo da string armazenada não pode ser maior que max_length, que depende do banco de dados.
Em termos de complexidade, isso daria ao Esquema #1 O(1) gravações para INSERT, porque as informações do pedido seriam armazenadas como um único campo na linha do elemento pai.
Outra desvantagem é que um JOIN à linha pai agora é necessário para atualizar a ordem.
