Come rappresenteresti una raccolta hashtable in uno schema di database?

Question

Se stavi provando a creare un oggetto dominio in uno schema di database e nel tuo codice tale oggetto dominio avesse un membro hashtable / list, in questo modo:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

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

Un dizionario è solo un hashtable / list che associa le chiavi dell'oggetto alle chiavi del valore, ho escogitato diversi modi per farlo, creando varie tabelle di join o tecniche di caricamento, ma tutti fanno schifo in termini di ottenimento di questo O (1) tempo di accesso ottenuto in una tabella hash.

Come rappresenteresti SpaceQuadrant, SpaceCoordinate e Space Object in uno schema di database? Una semplice descrizione del codice dello schema sarebbe utile, vale a dire.

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

ma qualsiasi pensiero sarebbe bello, grazie per la lettura!

Ulteriori informazioni:

Grazie per le ottime risposte, le ho già scremate e voglio prendere un po 'di tempo a pensare a ciascuna prima di rispondere.

Se pensi che ci sia un modo migliore per definire queste classi, allora mostrami un esempio, qualsiasi lingua con cui ti senti a tuo agio è interessante

Answer 1

In primo luogo, in molti database esiste un supporto dedicato per i dati geo-localizzati - è possibile utilizzare algoritmi diversi (ad esempio esiste una versione spaziale di un B-Tree) e probabilmente esisterà il supporto per le ricerche di prossimità.

Dato che hai una tabella hash diversa per ogni SpaceQuadrant, avresti bisogno di qualcosa di simile (modificato dal post di S.Lott):

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

Questo è un (SpaceCoordinate, Quadrant) - > SpaceObjectId dizionario.

=====

Ora, riguardo alla tua preoccupazione per le prestazioni di O (1), ci sono molte ragioni per cui è indirizzata erroneamente.

È possibile utilizzare in molti DB un indice hash per le tabelle basate sulla memoria, come qualcuno ti ha detto. Ma se hai bisogno di memoria persistente, dovresti aggiornare due tabelle (quella di memoria e quella persistente) invece di una (se non è disponibile un supporto integrato per questo). Per scoprire se vale la pena, devi fare un benchmark sui dati effettivi (con dimensioni effettive dei dati).

Inoltre, forzare una tabella in memoria può avere conseguenze peggiori.

Se qualcosa viene scambiato, sei morto - se avessi usato un B-Tree (cioè un normale indice basato su disco), i suoi algoritmi avrebbero minimizzato l'I / O necessario. Altrimenti, tutti i DBMS utilizzerebbero le tabelle hash e farebbero affidamento sullo scambio, anziché su B-Trees. Puoi provare ad anticipare se ti adatterai alla memoria, ma ...

Inoltre, gli alberi B non sono O (1) ma sono O (log_512 (N)), o cose del genere (so che collassa su O (log N), ma mi porti su questo). Avresti bisogno di (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB per essere 4, e se avessi così tanti dati avresti comunque bisogno di un grosso server di ferro per farlo stare nella memoria. Quindi, è quasi O (1), e i fattori costanti sono ciò che conta davvero.
Hai mai sentito parlare di algoritmi a bassa complessità asintotica, a fattore costante elevato, che sarebbero più veloci di quelli semplici con dimensioni dei dati poco pratiche?

Infine, penso che gli autori di DB siano più intelligenti di me e di te. Soprattutto data la natura dichiarativa di SQL, l'ottimizzazione manuale in questo modo non pagherà. Se un indice si adatta alla memoria, suppongo che potrebbero scegliere di creare e utilizzare una versione hashtable dell'indice del disco, se necessario, se ne valesse la pena. Esamina i tuoi documenti per questo.

Ma la linea di fondo è che l'ottimizzazione prematura è malvagia, specialmente quando è di questo tipo (strane ottimizzazioni che stiamo pensando da sole, al contrario delle ottimizzazioni SQL standard) e con un linguaggio dichiarativo.

Answer 2

Le relazioni non sono tabelle hash; sono insiemi.

Non organizzerei il database usando le coordinate come chiave. Cosa succede se un oggetto cambia posizione? Invece, probabilmente tratterei le coordinate come attributi di un oggetto.

Suppongo inoltre che ci sia un numero fisso di dimensioni, ad esempio tre. In tal caso, puoi archiviare questi attributi di un oggetto in colonne fisse:

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)
);

Nella tua classe orientata agli oggetti, non è chiaro perché i tuoi oggetti siano in un dizionario. Hai detto di accedervi in ??O (1) volta, ma perché lo fai coordinando?

Se lo stai usando per ottimizzare la ricerca di oggetti che si trovano vicino a un certo punto (l'astronave del giocatore, per esempio), potresti anche incorporare nella tua query SQL che popola questo SpaceQuadrant un calcolo della distanza di ogni oggetto da quel determinato punto e ordina i risultati per distanza.

Non so abbastanza del tuo programma per sapere se questi suggerimenti sono pertinenti. Ma ti stanno almeno facendo pensare a modi diversi di organizzare i dati?

Answer 3

Nel caso più semplice, il dizionario ha una chiave che mapperebbe alla chiave primaria di una tabella - in modo che quando si specificano i valori della chiave, è possibile trovare immediatamente i dati corrispondenti tramite una semplice ricerca.

In questo caso, avresti bisogno di una tabella SpaceQuadrant con qualsiasi attributo generale (a valore singolo) che descriva o caratterizzi un quadrante dello spazio. La tabella SpaceQuadrant avrebbe una chiave primaria, possibilmente un ID generato, forse un valore naturale. L'hashtable consisterebbe quindi in una tabella con il valore della chiave primaria per il riferimento incrociato di SpaceQuadrant, con la posizione (SpaceCoordinate) e gli attributi del quadrante e delle coordinate.

Ora, se si dispone di un DBMS estensibile, è possibile definire un tipo definito dall'utente per SpaceCoordinate; in caso contrario, puoi utilizzare un trio di colonne - x, y, z o r, theta, rho, ad esempio - per rappresentare la posizione (SpaceCoordinate).

In termini generali, la struttura che sto descrivendo è abbastanza simile a quella di Bill Karwin; la differenza chiave (gioco di parole non inteso fino a quando non stavo rileggendo il messaggio) è che è perfettamente OK nel mio libro avere la posizione come parte della chiave primaria della tabella delle sottoordinate se sei sicuro che sia il modo migliore per organizzare esso. Potresti anche avere una colonna ID oggetto che è una chiave candidata alternativa. In alternativa, se gli oggetti hanno un'esistenza indipendente dal quadrante spaziale in cui si trovano in quel momento (o possono esistere in più posizioni - perché non sono punti ma sono stazioni spaziali o qualcosa del genere), allora potresti avere lo SpaceObject in un tavolo separato. La cosa migliore dipende dalle informazioni che non abbiamo a nostra disposizione.

Dovresti essere consapevole delle limitazioni dell'uso di SpaceCoordinate come parte della chiave primaria:

• non ci sono due oggetti che possono occupare la stessa posizione (che si chiama collisione in una tabella hash, così come nello spazio 3D),
• se la posizione cambia, è necessario aggiornare i dati chiave, che è più costoso di un aggiornamento di dati non chiave,
• le ricerche di prossimità saranno difficili - le ricerche esatte sono abbastanza facili.

Lo stesso vale per il tuo dizionario in memoria; se cambi le coordinate, devi rimuovere il record dalla vecchia posizione e posizionarlo nella nuova posizione nel dizionario (o la lingua deve farlo per te dietro le quinte).

Answer 4

Un dizionario è una tabella. L'hash è una domanda sul tipo di indice utilizzato. La maggior parte dei RDBMS presuppone che le tabelle siano grandi e densamente impacchettate, rendendo un indice con hash non appropriato

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
}

I tuoi oggetti Space hanno riferimenti FK al quadrante in cui si trovano.

A seconda del tuo RDBMS, potresti essere in grado di trovare un indice basato sull'hash che ti dia le prestazioni che speri. Ad esempio MySQL, l'utilizzo del motore di archiviazione HEAP supporta gli indici HASH.