Como você representar uma coleção hashtable em um esquema de banco de dados?

https://stackoverflow.com/questions/449202

19-08-2019
|

Pergunta

Se você estava tentando criar um objeto de domínio em um esquema de banco de dados, e em seu código afirmou objeto de domínio tem um membro hashtable / list, assim:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

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

Um dicionário é apenas a hashtable / Lista chaves de mapeamento objeto para teclas de valor, eu vim acima com várias maneiras de fazer isso, criando várias tabelas de junção ou técnicas de carga, mas eles todo o tipo de chupar em termos de conseguir que O (1) tempo de acesso que você entrar em um hashtable.

Como você representar o SpaceQuadrant, SpaceCoordinate e objeto espacial em um esquema de banco de dados? A descrição do código de esquema simples seria bom, ie.

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

mas qualquer pensamento em tudo seria bom, bem, obrigado pela leitura!

Mais informações:

Obrigado pelas grandes respostas, já, eu só desnatado-los, e eu quero levar algum tempo pensando sobre cada um antes de eu responder.

Se você acha que há uma maneira melhor para definir essas classes, em seguida, por todos os meios mostrar-me um exemplo, qualquer linguagem de seu confortável com é legal

Solução

Primeiro, suporte dedicado para os dados geo-localizados existe em muitas bases de dados -. Diferentes algoritmos podem ser utilizados (uma versão espacial de um B-Tree existe, por exemplo), e suporte para pesquisas de proximidade, provavelmente existirá

Uma vez que você tem uma tabela hash diferente para cada SpaceQuadrant, você precisa de algo como (editado a partir de pós de S. Lott):

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

Este é um dicionário (SpaceCoordinate, Quadrant) -> SpaceObjectId.

=====

Agora, sobre o seu O (1) preocupação de desempenho, há um monte de razões pelas quais ele é injustamente tratados.

Você pode usar em muitos da DB um índice hash para tabelas baseadas em memória, como alguém disse. Mas se você precisar de armazenamento persistente, você precisa atualizar duas tabelas (a memória uma e um persistente) em vez de um (se não houver suporte embutido para isso). Para descobrir se que vale a pena, você precisaria de referência sobre os dados reais (com tamanhos de dados reais).

Além disso, forçando uma tabela na memória pode ter implicações piores.

Se algo nunca é trocado, você está morto - se você tivesse usado um (ou seja, índice baseado em disco normal) B-Tree, seus algoritmos teria minimizado o necessário I / O. Caso contrário, todos os DBMS do usaria tabelas hash e confiar em troca, em vez de B-Trees. Você pode tentar antecipar se você vai caber na memória, mas ...

Além disso, B-árvores não são O (1), mas eles são O (log_512 (N)), ou coisas assim (eu sei que recolhe a O (log N), mas me dar sobre isso). Você precisa de (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB para que isso seja 4, e se você tem tantos dados que você precisa de um servidor de ferro grande de qualquer maneira para que para caber na memória. Então, é quase O (1), e os fatores constantes são o que realmente importa.
Já ouviu falar sobre low-assintótica-complexidade, algoritmos de fator de grande constante, que seria mais rápido do que as simples apenas em tamanhos de dados impraticável?

Finalmente, penso DB autores são mais espertos do que eu e você. Especialmente tendo em conta a natureza declarativa de SQL, mão-otimizá-lo desta forma não vai pagar. Se um se encaixa índice na memória, eu acho que eles poderiam optar por construir e usar uma versão hashtable do índice do disco, conforme necessário, se valeu a pena. Investigar seus documentos para isso.

Mas a linha inferior é que, otimização prematura é mau, especialmente quando é desse tipo (otimizações estranhas nós estamos pensando sobre o nosso próprio, em oposição como otimizações SQL padrão), e com uma linguagem declarativa.

Outras dicas

Relações não são tabelas de hash; eles são conjuntos.

Eu não iria organizar o banco de dados usando as coordenadas como a chave. E se um objeto muda localização? Em vez disso, gostaria de coordenadas provavelmente tratar como atributos de um objeto.

Além disso, presumo existe um número fixo de dimensões, por exemplo, três. Se assim for, então você pode armazenar esses atributos de um objeto em colunas fixas:

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

Na sua classe orientada a objeto, não é claro por que os objetos estão em um dicionário. Você menciona acessá-los em O (1) tempo, mas por que você faz isso por coordenar?

Se você estiver usando isso para otimizar encontrar objetos que estão perto de um certo ponto (nave espacial do jogador, por exemplo), você também pode construir em sua consulta SQL que preenche este SpaceQuadrant um cálculo da distância de cada objeto de que determinado ponto e classificar os resultados por distância.

Eu não sei o suficiente sobre o seu programa para saber se estas sugestões são relevantes. Mas eles são, pelo menos, fazer você pensar em diferentes formas de organizar os dados?

No caso mais simples, o dicionário tem uma chave que mapeiam para a chave primária de uma tabela -. Modo que quando você especificar os valores da chave, você pode encontrar imediatamente os dados correspondentes por meio de uma pesquisa simples

Neste caso, você precisaria de um SpaceQuadrant mesa com nenhum gerais atributos (de valor único) que descrevem ou caracterizam um quadrante espaço. A tabela SpaceQuadrant teria uma chave primária, possivelmente um ID gerado, possivelmente, um valor natural. A tabela de dispersão, então, consiste de uma tabela com o valor da chave primária para referência cruzada a SpaceQuadrant, com a posição (um SpaceCoordinate) e os atributos do quadrante e coordenar.

Agora, se você tem um DBMS extensíveis, você pode definir um tipo definido pelo usuário para o SpaceCoordinate; se assim não for, é possível utilizar um trio de colunas - x, y, z ou r, theta, Rho, por exemplo -. para representar a posição (SpaceCoordinate)

Em termos gerais, a estrutura que eu estou descrevendo é bastante semelhante ao Bill Karwin de; a chave (pun não destinados até depois que eu estava relendo a mensagem) diferença é que é perfeitamente OK no meu livro para ter a posição como parte da chave primária da tabela de sub-ordenada se você tem certeza que é a melhor maneira de organizar isto. Você também pode ter uma coluna de identificação objeto que é uma chave candidata alternativa. Alternativamente, se os objetos têm uma existência independente do quadrante espaço que estejam em no momento (ou pode existir em várias posições - porque eles não são pontos, mas são estações espaciais ou algo assim), então você pode ter a SpaceObject em um mesa separada. O que é melhor depende de informações que não temos à nossa disposição.

Você deve estar ciente das limitações do uso de um SpaceCoordinate como parte da chave primária:

há dois objetos podem ocupar a mesma posição (isso é chamado de uma colisão em uma tabela hash, bem como no espaço 3D),
Se as mudanças de posição, então você tem que atualizar os dados-chave, que é mais caro do que uma atualização se a dados sem chave,
pesquisas de proximidade vai ser difícil -. Pesquisas exatas são fáceis o suficiente

O mesmo é verdadeiro de seu dicionário na memória; se você mudar as coordenadas, você tem que remover o registro do local antigo e colocá-lo no novo local no dicionário (ou a língua tem que fazer isso para você nos bastidores).

Um dicionário é uma mesa. O hash é uma questão de que tipo de índice é usado. A maioria dos RDBMS assumir que as tabelas são grandes e densamente, fazendo um índice hash não é apropriado.

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
}

Seus objetos espaciais têm referências FK para o quadrante em que eles estão localizados.

Dependendo de suas RDBMS, você pode ser capaz de encontrar um índice baseado em hash que obtém o desempenho que você está esperando. Por exemplo MySQL, usando os índices suportes de motor HASH armazenamento MONTÃO.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow