¿Cómo representaría una colección de tabla hash en un esquema de base de datos?

Question

Si intentaba crear un objeto de dominio en un esquema de base de datos, y en su código dicho objeto de dominio tiene un miembro de tabla hash / lista, así:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

Un diccionario es solo una tabla hash / lista de teclas de objeto de asignación de teclas de valor, se me ocurrieron varias formas de hacer esto, creando varias tablas de unión o técnicas de carga, pero todas apestan en términos de obtener ese O (1) tiempo de acceso que obtiene en una tabla hash.

¿Cómo representaría el SpaceQuadrant, SpaceCoordinate y Space Object en un esquema de base de datos? Una descripción simple del código de esquema sería agradable, es decir.

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

pero cualquier pensamiento sería bueno también, ¡gracias por leer!

Más información:

Gracias por las excelentes respuestas, ya que solo las he leído, y quiero tomarme un tiempo para pensar en cada una antes de responder.

Si crees que hay una mejor manera de definir estas clases, entonces muéstrame un ejemplo, cualquier idioma con el que te sientas cómodo es genial

Answer 1

Primero, el soporte dedicado para datos geo-ubicados existe en muchas bases de datos: se pueden usar diferentes algoritmos (por ejemplo, existe una versión espacial de un B-Tree), y probablemente existirá soporte para búsquedas de proximidad.

Dado que tiene una tabla hash diferente para cada SpaceQuadrant, necesitaría algo como (editado de la publicación de S.Lott):

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

Este es un (SpaceCoordinate, Quadrant) - > Diccionario SpaceObjectId .

=====

Ahora, sobre su preocupación por el rendimiento de O (1), hay muchas razones por las que se aborda de manera incorrecta.

Puede usar en muchas bases de datos un índice hash para tablas basadas en memoria, como alguien le dijo. Pero si necesita almacenamiento persistente, necesitaría actualizar dos tablas (la memoria y la persistente) en lugar de una (si no hay soporte integrado para esto). Para descubrir si vale la pena, necesitaría comparar los datos reales (con los tamaños de datos reales).

Además, forzar una tabla en la memoria puede tener peores implicaciones.

Si alguna vez se intercambia algo, estás muerto: si hubieras usado un B-Tree (es decir, un índice normal basado en disco), sus algoritmos habrían minimizado la E / S necesaria. De lo contrario, todos los DBMS usarían tablas hash y confiarían en el intercambio, en lugar de B-Trees. Puede intentar anticipar si cabe en la memoria, pero ...

Además, los árboles B no son O (1) pero son O (log_512 (N)), o cosas por el estilo (sé que se derrumba a O (log N), pero dame cuenta de esto). Necesitaría (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB para que sea 4, y si tiene tantos datos necesitaría un gran servidor de hierro de todos modos para que quepa en la memoria. Entonces, es casi O (1), y los factores constantes son lo que realmente importa.
¿Alguna vez escuchó sobre algoritmos de baja complejidad asintótica y factor de gran constante, que serían más rápidos que los simples solo en tamaños de datos poco prácticos?

Finalmente, creo que los autores de DB son más inteligentes que tú y yo. Especialmente dada la naturaleza declarativa de SQL, la optimización manual de esta manera no va a pagar. Si un índice cabe en la memoria, supongo que podrían optar por crear y usar una versión de tabla hash del índice del disco, según sea necesario, si valiera la pena. Investigue sus documentos para eso.

Pero la conclusión es que la optimización prematura es mala, especialmente cuando es de este tipo (optimizaciones extrañas que estamos pensando por nuestra cuenta, a diferencia de las optimizaciones SQL estándar), y con un lenguaje declarativo.

Answer 2

Las relaciones no son tablas hash; son conjuntos.

No organizaría la base de datos utilizando las coordenadas como clave. ¿Qué pasa si un objeto cambia de ubicación? En cambio, probablemente trataría las coordenadas como atributos de un objeto.

Además, supongo que hay un número fijo de dimensiones, por ejemplo, tres. Si es así, puede almacenar estos atributos de un objeto en columnas fijas:

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

En su clase orientada a objetos, no está claro por qué sus objetos están en un diccionario. Menciona el acceso a ellos en el tiempo O (1), pero ¿por qué lo hace por coordenadas?

Si está usando eso para optimizar la búsqueda de objetos que están cerca de un cierto punto (la nave espacial del jugador, por ejemplo), también podría incorporar a su consulta SQL que llena este SpaceQuadrant un cálculo de la distancia de cada objeto desde ese punto dado y ordena los resultados por distancia.

No sé lo suficiente sobre su programa para saber si estas sugerencias son relevantes. ¿Pero al menos te hacen pensar en diferentes formas de organizar los datos?

Answer 3

En el caso más simple, el diccionario tiene una clave que se correlacionaría con la clave primaria de una tabla, de modo que cuando especifique los valores de la clave, pueda encontrar inmediatamente los datos coincidentes a través de una simple búsqueda.

En este caso, necesitaría una tabla SpaceQuadrant con cualquier atributo general (de un solo valor) que describa o caracterice un cuadrante espacial. La tabla SpaceQuadrant tendría una clave primaria, posiblemente una ID generada, posiblemente un valor natural. La tabla hash consistiría entonces en una tabla con el valor de la clave primaria para hacer referencia cruzada al SpaceQuadrant, con la posición (un SpaceCoordinate) y los atributos del cuadrante y la coordenada.

Ahora, si tiene un DBMS extensible, puede definir un tipo definido por el usuario para SpaceCoordinate; en su defecto, puede usar un trío de columnas (x, y, z or r, theta, rho, por ejemplo) para representar la posición (SpaceCoordinate).

En términos generales, la estructura que describo es bastante similar a la de Bill Karwin; La diferencia clave (juego de palabras no intencionado hasta después de haber releído el mensaje) es que está perfectamente bien en mi libro tener la posición como parte de la clave principal de la tabla de coordenadas si está seguro de que es la mejor manera de organizar eso. También puede tener una columna de ID de objeto que sea una clave candidata alternativa. Alternativamente, si los objetos tienen una existencia independiente del cuadrante espacial en el que se encuentran en este momento (o pueden existir en múltiples posiciones, porque no son puntos sino estaciones espaciales o algo así), entonces podría tener el SpaceObject en un Mesa separada. Lo mejor depende de la información que no tenemos disponible para nosotros.

Debe tener en cuenta las limitaciones del uso de SpaceCoordinate como parte de la clave principal:

• no hay dos objetos que puedan ocupar la misma posición (eso se llama colisión en una tabla hash, así como en un espacio 3D),
• si la posición cambia, entonces debe actualizar los datos clave, que es más costoso que una actualización de datos no clave,
• las búsquedas de proximidad serán difíciles: las búsquedas exactas son bastante fáciles.

Lo mismo se aplica a su diccionario en la memoria; si cambia las coordenadas, debe eliminar el registro de la ubicación anterior y colocarlo en la nueva ubicación en el diccionario (o el idioma debe hacerlo por usted detrás de escena).

Answer 4

Un diccionario es una tabla. El hash es una cuestión de qué tipo de índice se usa. La mayoría de los RDBMS suponen que las tablas son grandes y densamente empaquetadas, por lo que un índice hash no es apropiado.

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

Sus objetos Space tienen referencias FK al Cuadrante en el que se encuentran.

Dependiendo de su RDBMS, es posible que pueda encontrar un índice basado en hash que le brinde el rendimiento que espera. Por ejemplo, MySQL, el uso del motor de almacenamiento HEAP admite índices HASH.