Représenter la commande dans une base de données relationnelle
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une collection d'objets dans une base de données.Images dans une galerie photo, produits dans un catalogue, chapitres d'un livre, etc.Chaque objet est représenté sous forme de ligne.Je veux pouvoir ordonner arbitrairement ces images, en stockant cet ordre dans la base de données afin que lorsque j'afficherai les objets, ils soient dans le bon ordre.
Par exemple, disons que j'écris un livre et que chaque chapitre est un objet.J'écris mon livre et je mets les chapitres dans l'ordre suivant :
Introduction, accessibilité, forme vs.Fonction, erreurs, cohérence, conclusion, index
Il va dans l'éditeur et revient avec l'ordre suggéré suivant :
Introduction, Forme, Fonction, Accessibilité, Cohérence, Erreurs, Conclusion, Index
Comment puis-je stocker cette commande dans la base de données de manière robuste et efficace ?
J'ai eu les idées suivantes, mais aucune ne me plaît :
Tableau.Chaque ligne a un identifiant de commande, lorsque la commande est modifiée (via une suppression suivie d'une insertion), les identifiants de commande sont mis à jour.Cela rend la récupération facile, puisqu'il s'agit simplement
ORDER BY, mais il semble facile à casser.// 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=addedIDListe chaînée.Chaque ligne a une colonne pour l'identifiant de la ligne suivante dans l'ordre.La traversée semble coûteuse ici, bien qu'il puisse être possible d'utiliser
ORDER BYauquel je ne pense pas.Tableau espacé.Définissez le orderingID (tel qu'utilisé dans #1) pour qu'il soit grand, de sorte que le premier objet soit 100, le second soit 200, etc.Ensuite, lorsqu'une insertion se produit, il vous suffit de la placer à
(objectBefore + objectAfter)/2.Bien sûr, cela devra être rééquilibré de temps en temps, afin que les choses ne soient pas trop rapprochées (même avec des flottants, vous finirez par rencontrer des erreurs d'arrondi).
Aucun de ceux-ci ne me semble particulièrement élégant.Quelqu'un a-t-il une meilleure façon de procéder ?
La solution 9
Depuis que j'ai surtout rencontré cela avec Django, j'ai trouvé cette solution pour être le plus réalisable.Il semble qu’il n’y ait pas de « bonne façon » de procéder dans une base de données relationnelle.
Autres conseils
Une autre alternative serait (si votre SGBDR le prend en charge) d'utiliser des colonnes de type tableau.Bien que cela enfreigne les règles de normalisation, cela peut être utile dans des situations comme celle-ci.Une base de données que je connais et qui contient des tableaux est PostgreSQL.
Le mixin actes_as_list dans Rails gère cela essentiellement de la manière que vous avez décrite au point 1.Il recherche une colonne INTEGER appelée position (dont vous pouvez bien sûr remplacer le nom) et l'utilise pour effectuer un ORDER BY.Lorsque vous souhaitez réorganiser les choses, vous mettez à jour les positions.Il m'a très bien servi à chaque fois que je l'ai utilisé.
En remarque, vous pouvez supprimer le besoin de toujours repositionner les INSERTS/DELETES en utilisant une numérotation clairsemée - un peu comme la base à l'époque...vous pouvez numéroter vos positions 10, 20, 30, etc.et si vous devez insérer quelque chose entre 10 et 20, insérez-le simplement avec une position de 15.De même, lors de la suppression, vous pouvez simplement supprimer la ligne et laisser l'espace.Vous n'avez besoin de renuméroter que lorsque vous modifiez réellement l'ordre ou si vous essayez de faire une insertion et qu'il n'y a pas d'espace approprié dans lequel insérer.
Bien sûr, en fonction de votre situation particulière (par ex.que les autres lignes soient déjà chargées en mémoire ou non), il peut être judicieux ou non d'utiliser l'approche par écart.
Juste une pensée, considérant option n°1 contre n°3:l'option de tableau espacé (#3) ne fait-elle pas que reporter le problème du tableau normal (#1) ?Quel que soit l'algorithme que vous choisissez, soit il est défectueux et vous rencontrerez des problèmes avec le n°3 plus tard, soit il fonctionne, et le n°1 devrait alors fonctionner tout aussi bien.
Si les objets ne sont pas fortement saisis par d'autres tables et que les listes sont courtes, il est plus simple de tout supprimer dans le domaine et de simplement réinsérer la liste correcte.Mais ce n'est pas pratique si les listes sont volumineuses et que vous avez beaucoup de contraintes pour ralentir la suppression.Je pense que votre première méthode est vraiment la plus propre.Si vous l'exécutez dans une transaction, vous pouvez être sûr que rien d'étrange ne se produit pendant que vous êtes au milieu de la mise à jour pour gâcher la commande.
Je l'ai fait dans mon dernier projet, mais c'était pour une table qui ne devait être commandée spécifiquement qu'occasionnellement et qui n'était pas consultée trop souvent.Je pense que le tableau espacé serait la meilleure option, car sa réorganisation serait la moins chère dans le cas moyen, impliquant simplement une modification d'une valeur et une requête sur deux).
De plus, j'imagine que ORDER BY serait assez fortement optimisé par les fournisseurs de bases de données, donc tirer parti de cette fonction serait avantageux pour les performances par opposition à l'implémentation de listes chaînées.
Utilisez un nombre à virgule flottante pour représenter la position de chaque élément :
Article 1 -> 0,0
Article 2 -> 1.0
Article 3 -> 2.0
Article 4 -> 3.0
Vous pouvez placer n'importe quel élément entre deux autres éléments par simple bissection :
Article 1 -> 0,0
Article 4 -> 0,5
Article 2 -> 1.0
Article 3 -> 2.0
(Déplacement de l'élément 4 entre les éléments 1 et 2).
Le processus de bissection peut se poursuivre presque indéfiniment en raison de la manière dont les nombres à virgule flottante sont codés dans un système informatique.
Article 4 -> 0,5
Article 1 -> 0,75
Article 2 -> 1.0
Article 3 -> 2.0
(Déplacez l'élément 1 vers la position juste après l'élément 4)
Je ferais un numéro consécutif, avec un déclencheur sur la table qui "fait de la place" à une priorité si elle existe déjà.
J'ai également eu ce problème.J'étais sous une forte pression de temps (n'est-ce pas nous tous) et j'ai opté pour l'option n°1 et j'ai uniquement mis à jour les lignes qui changeaient.
Si vous échangez l'article 1 avec l'article 10, effectuez simplement deux mises à jour pour mettre à jour les numéros de commande de l'article 1 et de l'article 10.Je sais que c'est algorithmiquement simple, et c'est le pire des cas O(n), mais ce pire cas est celui où vous avez une permutation totale de la liste.À quelle fréquence cela va-t-il arriver ?C'est à vous de répondre.
J'ai eu le même problème et j'ai probablement passé au moins une semaine à me préoccuper de la modélisation appropriée des données, mais je pense que je l'ai enfin compris.En utilisant le type de données tableau dans PostgreSQL, vous pouvez stocker la clé primaire de chaque élément commandé et mettre à jour ce tableau en conséquence en utilisant des insertions ou des suppressions lorsque votre commande change.Le référencement d'une seule ligne vous permettra de mapper tous vos objets en fonction de l'ordre dans la colonne du tableau.
C'est encore une solution un peu instable, mais elle fonctionnera probablement mieux que l'option n°1, car l'option 1 nécessite de mettre à jour le numéro d'ordre de toutes les autres lignes lors de l'ordre des modifications.
Le schéma n°1 et le schéma n°3 ont la même complexité dans chaque opération, sauf INSERT écrit.Le schéma n°1 comporte des écritures O(n) INSERT et le schéma n°3 comporte des écritures O(1) INSERT.
Pour toutes les autres opérations de base de données, la complexité est la même.
Le schéma n°2 ne devrait même pas être envisagé car il DELETE nécessite des lectures et des écritures O(n).Le schéma n°1 et le schéma n°3 ont O(1) DELETE pour la lecture et l'écriture.
Nouvelle méthode
Si vos éléments ont un élément parent distinct (c'est-à-direils partagent une ligne de clé étrangère), alors vous pouvez essayer ce qui suit...
Django propose une solution indépendante de la base de données pour stocker des listes d'entiers dans CharField().Un inconvénient est que la longueur maximale de la chaîne stockée ne peut pas être supérieure à max_length, qui dépend de la base de données.
En termes de complexité, cela donnerait au schéma n°1 des écritures O(1) pour INSERT, car les informations de commande seraient stockées dans un seul champ dans la ligne de l'élément parent.
Un autre inconvénient est qu'un JOIN à la ligne parent est désormais nécessaire pour mettre à jour la commande.
