Representar pedidos en una base de datos relacional
https://stackoverflow.com/questions/21388
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo una colección de objetos en una base de datos.Imágenes de una galería de fotos, productos de un catálogo, capítulos de un libro, etc.Cada objeto se representa como una fila.Quiero poder ordenar arbitrariamente estas imágenes, almacenando ese orden en la base de datos para que cuando muestre los objetos, estén en el orden correcto.
Por ejemplo, digamos que estoy escribiendo un libro y cada capítulo es un objeto.Escribo mi libro y pongo los capítulos en el siguiente orden:
Introducción, Accesibilidad, Forma vs.Función, errores, coherencia, conclusión, índice
Va al editor y regresa con el siguiente orden sugerido:
Introducción, forma, función, accesibilidad, coherencia, errores, conclusión, índice
¿Cómo puedo almacenar este pedido en la base de datos de una manera sólida y eficiente?
He tenido las siguientes ideas, pero no estoy entusiasmado con ninguna de ellas:
Formación.Cada fila tiene un ID de pedido; cuando se cambia el pedido (mediante una eliminación seguida de una inserción), los ID de pedido se actualizan.Esto facilita la recuperación, ya que es solo
ORDER BY, pero parece fácil de romper.// 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 enlazada.Cada fila tiene una columna para la identificación de la siguiente fila en el orden.El recorrido parece costoso aquí, aunque de alguna manera puede usarse
ORDER BYque no estoy pensando.Matriz espaciada.Establezca el ID de pedido (como se usa en el punto 1) para que sea grande, de modo que el primer objeto sea 100, el segundo sea 200, etc.Luego, cuando ocurre una inserción, simplemente la colocas en
(objectBefore + objectAfter)/2.Por supuesto, esto debería reequilibrarse ocasionalmente, para que no tenga las cosas demasiado juntas (incluso con flotadores, eventualmente se encontraría con errores de redondeo).
Ninguno de estos me parece particularmente elegante.¿Alguien tiene una mejor manera de hacerlo?
Solución 9
Como me encontré con esto principalmente con Django, encontré esta solución ser el más viable.Parece que no existe una "forma correcta" de hacer esto en una base de datos relacional.
Otros consejos
Otra alternativa sería (si su RDBMS lo admite) utilizar columnas de tipo matriz.Si bien esto infringe las reglas de normalización, puede resultar útil en situaciones como esta.Una base de datos que conozco que tiene matrices es PostgreSQL.
El mixin acts_as_list en Rails maneja esto básicamente de la forma que se describió en el n.° 1.Busca una columna INTEGER llamada posición (de la cual puede anular el nombre, por supuesto) y la usa para hacer un ORDER BY.Cuando quieras reordenar cosas, actualizas las posiciones.Me ha servido muy bien cada vez que lo he usado.
Como nota al margen, puede eliminar la necesidad de reposicionar siempre las INSERCIONES/ELIMINACIONES mediante el uso de numeración dispersa, algo así como lo básico en el pasado...puedes numerar tus posiciones 10, 20, 30, etc.y si necesita insertar algo entre 10 y 20, simplemente insértelo con una posición de 15.Del mismo modo, al eliminar, puede simplemente eliminar la fila y dejar el espacio.Solo necesita volver a numerar cuando realmente cambia el orden o si intenta insertar y no hay un espacio apropiado para insertar.
Por supuesto, dependiendo de su situación particular (p. ej.ya sea que tenga las otras filas ya cargadas en la memoria o no), puede que tenga sentido o no utilizar el enfoque de espacio.
Sólo un pensamiento considerando opción n.° 1 frente a n.° 3:¿La opción de matriz espaciada (n.° 3) no pospone solo el problema de la matriz normal (n.° 1)?Cualquiera que sea el algoritmo que elijas, o está roto y tendrás problemas con el número 3 más adelante, o funciona, y luego el número 1 debería funcionar igual de bien.
Si los objetos no están fuertemente codificados por otras tablas y las listas son cortas, lo más fácil es eliminar todo lo que hay en el dominio y simplemente volver a insertar la lista correcta.Pero eso no es práctico si las listas son grandes y tienes muchas restricciones para ralentizar la eliminación.Creo que tu primer método es realmente el más limpio.Si lo ejecuta en una transacción, puede estar seguro de que no sucede nada extraño mientras está en medio de la actualización que pueda arruinar el pedido.
Hice esto en mi último proyecto, pero fue para una mesa que solo ocasionalmente necesitaba ser ordenada específicamente y a la que no se accedía con demasiada frecuencia.Creo que la matriz espaciada sería la mejor opción, porque reordenar sería más barato en el caso promedio, ya que solo implica un cambio en un valor y una consulta en dos).
Además, me imagino que los proveedores de bases de datos optimizarían bastante ORDER BY, por lo que aprovechar esa función sería ventajoso para el rendimiento en comparación con la implementación de la lista vinculada.
Utilice un número de punto flotante para representar la posición de cada elemento:
Elemento 1 -> 0,0
Artículo 2 -> 1.0
Artículo 3 -> 2.0
Artículo 4 -> 3.0
Puede colocar cualquier elemento entre otros dos elementos mediante una simple bisección:
Elemento 1 -> 0,0
Ítem 4 -> 0,5
Artículo 2 -> 1.0
Artículo 3 -> 2.0
(Se movió el punto 4 entre los puntos 1 y 2).
El proceso de bisección puede continuar casi indefinidamente debido a la forma en que se codifican los números de coma flotante en un sistema informático.
Ítem 4 -> 0,5
Artículo 1 -> 0,75
Artículo 2 -> 1.0
Artículo 3 -> 2.0
(Mueva el elemento 1 a la posición justo después del elemento 4)
Haría un número consecutivo, con un disparador en la mesa que "hace espacio" para una prioridad si ya existe.
Yo tuve este problema también.Estaba bajo una gran presión de tiempo (¿no lo estamos todos?) y elegí la opción n.° 1, y solo actualicé las filas que cambiaron.
Si intercambia el artículo 1 con el artículo 10, simplemente haga dos actualizaciones para actualizar los números de pedido del artículo 1 y del artículo 10.Sé que es algorítmicamente simple y que es el peor de los casos O(n), pero el peor de los casos es cuando tienes una permutación total de la lista.¿Con qué frecuencia sucederá eso?Eso lo tienes que responder tú.
Tuve el mismo problema y probablemente pasé al menos una semana preocupándome por el modelado de datos adecuado, pero creo que finalmente lo logré.Usando el tipo de datos de matriz en PostgreSQL, puede almacenar la clave principal de cada elemento ordenado y actualizar esa matriz en consecuencia mediante inserciones o eliminaciones cuando cambie su pedido.Hacer referencia a una sola fila le permitirá asignar todos sus objetos según el orden en la columna de la matriz.
Todavía es una solución un poco entrecortada, pero probablemente funcionará mejor que la opción n.° 1, ya que la opción 1 requiere actualizar el número de pedido de todas las demás filas al ordenar los cambios.
El esquema #1 y el esquema #3 tienen la misma complejidad en todas las operaciones excepto INSERT escribe.El esquema n.º 1 tiene escrituras O(n) INSERT y el esquema #3 tiene escrituras O(1) en INSERT.
Para todas las demás operaciones de base de datos, la complejidad es la misma.
El esquema #2 ni siquiera debería ser considerado porque su DELETE requiere O(n) lecturas y escrituras.El esquema n.º 1 y el esquema n.º 3 tienen O(1) DELETE tanto para lectura como para escritura.
Nuevo método
Si sus elementos tienen un elemento principal distinto (es decir,comparten una fila de clave externa), entonces puedes probar lo siguiente...
Django ofrece una solución independiente de la base de datos para almacenar listas de números enteros dentro CharField().Un inconveniente es que la longitud máxima de la cadena almacenada no puede ser mayor que max_length, que depende de la base de datos.
En términos de complejidad, esto le daría al Esquema #1 O(1) escrituras para INSERT, porque la información de pedido se almacenaría como un único campo en la fila del elemento principal.
Otro inconveniente es que un JOIN a la fila principal ahora es necesario para actualizar el pedido.
