Rappresentare l'ordinamento in un database relazionale
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho una raccolta di oggetti in un database.Immagini in una galleria fotografica, prodotti in un catalogo, capitoli di un libro, ecc.Ogni oggetto è rappresentato come una riga.Voglio essere in grado di ordinare arbitrariamente queste immagini, memorizzando tale ordinamento nel database in modo che quando visualizzo gli oggetti, saranno nell'ordine giusto.
Ad esempio, diciamo che sto scrivendo un libro e ogni capitolo è un oggetto.Scrivo il mio libro e metto i capitoli nel seguente ordine:
Introduzione, accessibilità, forma vs.Funzione, errori, coerenza, conclusione, indice
Va all'editor e ritorna con il seguente ordine suggerito:
Introduzione, Forma, Funzione, Accessibilità, Coerenza, Errori, Conclusione, Indice
Come posso archiviare questo ordinamento nel database in modo robusto ed efficiente?
Ho avuto le seguenti idee, ma non ne sono entusiasta nessuna:
Vettore.Ogni riga ha un ID ordine, quando l'ordine viene modificato (tramite una rimozione seguita da un inserimento), gli ID ordine vengono aggiornati.Ciò semplifica il recupero, poiché è solo
ORDER BY, ma sembra facile da rompere.// 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 collegata.Ogni riga ha una colonna per l'ID della riga successiva nell'ordinamento.L'attraversamento sembra costoso qui, anche se potrebbe in qualche modo essere utilizzato
ORDER BYa cui non sto pensando.Array distanziato.Imposta orderingID (come utilizzato in #1) su un valore grande, quindi il primo oggetto è 100, il secondo è 200, ecc.Quindi, quando avviene un inserimento, lo posizioni semplicemente in
(objectBefore + objectAfter)/2.Naturalmente, questo dovrebbe essere ribilanciato di tanto in tanto, in modo da non avere cose troppo vicine tra loro (anche con i float, alla fine potresti incorrere in errori di arrotondamento).
Nessuno di questi mi sembra particolarmente elegante.Qualcuno ha un modo migliore per farlo?
Soluzione 9
Dato che mi sono imbattuto principalmente in questo con Django, ho trovato questa soluzione essere il più praticabile.Sembra che non esista un "modo giusto" per farlo in un database relazionale.
Altri suggerimenti
Un'altra alternativa sarebbe (se il tuo RDBMS lo supporta) utilizzare colonne di tipo array.Sebbene ciò infranga le regole di normalizzazione, può essere utile in situazioni come questa.Un database che conosco che ha array è PostgreSQL.
Il mixin act_as_list in Rails gestisce tutto ciò fondamentalmente nel modo descritto al punto 1.Cerca una colonna INTEGER chiamata posizione (di cui puoi ovviamente sovrascrivere il nome) e la usa per eseguire un ORDER BY.Quando vuoi riordinare le cose aggiorni le posizioni.Mi è servito bene ogni volta che l'ho usato.
Come nota a margine, puoi eliminare la necessità di eseguire sempre il riposizionamento su INSERTI/ELIMINA utilizzando una numerazione sparsa - un po' come quella di base in passato...puoi numerare le tue posizioni 10, 20, 30, ecc.e se devi inserire qualcosa tra 10 e 20, inseriscilo semplicemente con la posizione 15.Allo stesso modo durante l'eliminazione puoi semplicemente eliminare la riga e lasciare lo spazio vuoto.È necessario eseguire la rinumerazione solo quando si modifica effettivamente l'ordine o se si tenta di eseguire un inserimento e non è presente uno spazio appropriato in cui inserirlo.
Naturalmente a seconda della situazione specifica (ad es.indipendentemente dal fatto che le altre righe siano già caricate in memoria o meno) potrebbe avere senso o meno utilizzare l'approccio gap.
Solo un pensiero in considerazione opzione n. 1 contro n. 3:l'opzione dell'array distanziato (n. 3) non rimanda solo il problema dell'array normale (n. 1)?Qualunque algoritmo tu scelga, o è rotto e in seguito incontrerai problemi con il punto 3, oppure funziona, e quindi il numero 1 dovrebbe funzionare altrettanto bene.
Se gli oggetti non sono fortemente codificati da altre tabelle e gli elenchi sono brevi, eliminare tutto nel dominio e reinserire semplicemente l'elenco corretto è la soluzione più semplice.Ma ciò non è pratico se gli elenchi sono grandi e ci sono molti vincoli per rallentare l'eliminazione.Penso che il tuo primo metodo sia davvero il più pulito.Se lo esegui in una transazione puoi essere sicuro che non accada nulla di strano mentre sei nel mezzo dell'aggiornamento che possa rovinare l'ordine.
L'ho fatto nel mio ultimo progetto, ma era per un tavolo che solo occasionalmente necessitava di essere ordinato specificamente e a cui non si accedeva troppo spesso.Penso che l'array spaziato sarebbe l'opzione migliore, perché il riordino sarebbe nel caso medio più economico, implicando solo una modifica su un valore e una query su due).
Inoltre, immagino che ORDER BY sarebbe piuttosto ottimizzato dai fornitori di database, quindi sfruttare tale funzione sarebbe vantaggioso per le prestazioni rispetto all'implementazione dell'elenco collegato.
Utilizza un numero in virgola mobile per rappresentare la posizione di ciascun elemento:
Elemento 1 -> 0.0
Elemento 2 -> 1.0
Punto 3 -> 2.0
Punto 4 -> 3.0
Puoi posizionare qualsiasi oggetto tra altri due elementi mediante una semplice bisezione:
Elemento 1 -> 0.0
Punto 4 -> 0.5
Elemento 2 -> 1.0
Punto 3 -> 2.0
(Articolo 4 spostato tra gli elementi 1 e 2).
Il processo di bisezione può continuare quasi indefinitamente a causa del modo in cui i numeri in virgola mobile sono codificati in un sistema informatico.
Punto 4 -> 0.5
Voce 1 -> 0,75
Elemento 2 -> 1.0
Punto 3 -> 2.0
(Sposta l'elemento 1 nella posizione subito dopo l'elemento 4)
Farei un numero consecutivo, con un trigger sulla tabella che "fa spazio" a una priorità se esiste già.
Anch'io ho avuto questo problema.Ero sotto forte pressione di tempo (non lo siamo tutti) e ho scelto l'opzione n. 1 e ho aggiornato solo le righe che erano cambiate.
Se scambi l'articolo 1 con l'articolo 10, esegui semplicemente due aggiornamenti per aggiornare i numeri d'ordine dell'articolo 1 e dell'articolo 10.So che è algoritmicamente semplice ed è il caso peggiore O(n), ma il caso peggiore è quando si ha una permutazione totale dell'elenco.Quanto spesso accadrà?Sta a te rispondere.
Ho avuto lo stesso problema e probabilmente ho passato almeno una settimana a preoccuparmi della corretta modellazione dei dati, ma penso di averlo finalmente risolto.Utilizzando il tipo di dati array in PostgreSQL, puoi memorizzare la chiave primaria di ciascun articolo ordinato e aggiornare l'array di conseguenza utilizzando inserimenti o eliminazioni quando l'ordine cambia.Fare riferimento a una singola riga ti consentirà di mappare tutti i tuoi oggetti in base all'ordine nella colonna dell'array.
È ancora una soluzione un po' discontinua, ma probabilmente funzionerà meglio dell'opzione n. 1, poiché l'opzione 1 richiede l'aggiornamento del numero d'ordine di tutte le altre righe quando si ordinano le modifiche.
Lo schema n. 1 e lo schema n. 3 hanno la stessa complessità in tutte le operazioni tranne INSERT scrive.Lo schema n. 1 prevede la scrittura di O(n). INSERT e lo Schema n. 3 ha O(1) scritto INSERT.
Per ogni altra operazione del database, la complessità è la stessa.
Lo schema n. 2 non dovrebbe nemmeno essere preso in considerazione perché è così DELETE richiede che O(n) legga e scriva.Lo schema n. 1 e lo schema n. 3 hanno O(1) DELETE sia per leggere che per scrivere.
Nuovo metodo
Se i tuoi elementi hanno un elemento genitore distinto (ad es.condividono una riga di chiave esterna), quindi puoi provare quanto segue...
Django offre una soluzione indipendente dal database per archiviare elenchi di numeri interi all'interno CharField().Uno svantaggio è che la lunghezza massima della stringa memorizzata non può essere maggiore di max_length, che dipende dal DB.
In termini di complessità, ciò fornirebbe lo Schema n. 1 per cui O(1) scrive INSERT, perché le informazioni sull'ordinamento verrebbero archiviate come un singolo campo nella riga dell'elemento genitore.
Un altro svantaggio è che a JOIN alla riga madre è ora necessario aggiornare l'ordinamento.
