A carregar...
Publicação
Replicated Data Types for Graph Databases
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.87 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
Nowadays graph databases have seen an increase in popularity in applications with highly
interconnected data like networks such as social networks, biological, or transportation.
Such applications can be implemented on a spectrum of graph data models, from labelled
graphs to property graphs. Graph databases allow for flexibility in schema enforcement,
offering schema-flexible and even schema-free approaches.
Graph databases are used by large-scale applications that require low latency and
high availability for millions of users across the world. Nowadays, the usual approach
to achieve these latency and availability demands is to resort to data replication across
multiple data centers and rely on a weak consistency model. The use of weak consistency
introduces scenarios where concurrent updates may lead the replicas’ states to diverge.
Replicated data types (CRDTs) implement a deterministic resolution of such conflicts,
ensuring state convergence among all replicas. Even though CRDTs guarantee conver-
gence, the final state may be invalid if convergence rules do not consider data invariants.
For example, implementing a property graph CRDT, requires more complex data types
in the state, since nodes and edges have sets of key-value pairs with properties, these are
considered invariants and create the possibility of invalid states. Also, a property graph
can be bound to a schema, and if so it becomes a graph invariant that is to be maintained.
With this work, we intend to develop specialized graph CRDTs in Datalog (Soufflé)
for multiple graph models and multiple conflict policies as Datalog offers a high level of
abstraction, monotonicity and safety.
Hoje em dia, as bases de dados de grafos têm visto um aumento de popularidade em aplicações com dados altamente interligados, como redes sociais, biológicas ou de transportes. Tais aplicações podem ser implementadas num espectro de modelos de dados grafos, desde grafos etiquetados a grafos de propriedades. As bases de dados grafos permitem flexibilidade na aplicação de esquemas, oferecendo abordagens flexíveis e até mesmo sem esquemas. As bases de dados grafos são utilizadas por aplicações de grande escala que requerem baixa latência e alta disponibilidade para milhões de utilizadores em todo o mundo. Atualmente, a abordagem habitual para alcançar estas exigências de latência e disponibi- lidade é recorrer à replicação de dados em múltiplos centros de dados e contar com um modelo de fraca consistência. A utilização de consistência fraca introduz cenários em que atualizações simultâneas podem levar os estados das réplicas a divergir. Os tipos de dados replicados (CRDT) implementam uma resolução determinista de tais conflitos, assegurando a convergência de estados entre todas as réplicas. Embora os CRDTs garantam a convergência, o estado final pode ser inválido se as regras de convergência não considerarem invariantes de dados. Por exemplo, implementar um gráfico de propriedade CRDT, requer tipos de dados mais complexos no estado, uma vez que os nós e as arestas têm conjuntos de pares de valores-chave com propriedades, estes são considerados invariantes e criam a possibilidade de estados inválidos. Além disso, um gráfico de propriedade pode ser ligado a um esquema, e se assim for, torna-se um invariante do gráfico que deve ser mantido. Com este trabalho, pretendemos desenvolver CRDTs grafos especializados em Datalog (Soufflé) para múltiplos modelos grafos e múltiplas políticas de conflito já que o Datalog oferece um elevado nível de abstração, monotonicidade e segurança.
Hoje em dia, as bases de dados de grafos têm visto um aumento de popularidade em aplicações com dados altamente interligados, como redes sociais, biológicas ou de transportes. Tais aplicações podem ser implementadas num espectro de modelos de dados grafos, desde grafos etiquetados a grafos de propriedades. As bases de dados grafos permitem flexibilidade na aplicação de esquemas, oferecendo abordagens flexíveis e até mesmo sem esquemas. As bases de dados grafos são utilizadas por aplicações de grande escala que requerem baixa latência e alta disponibilidade para milhões de utilizadores em todo o mundo. Atualmente, a abordagem habitual para alcançar estas exigências de latência e disponibi- lidade é recorrer à replicação de dados em múltiplos centros de dados e contar com um modelo de fraca consistência. A utilização de consistência fraca introduz cenários em que atualizações simultâneas podem levar os estados das réplicas a divergir. Os tipos de dados replicados (CRDT) implementam uma resolução determinista de tais conflitos, assegurando a convergência de estados entre todas as réplicas. Embora os CRDTs garantam a convergência, o estado final pode ser inválido se as regras de convergência não considerarem invariantes de dados. Por exemplo, implementar um gráfico de propriedade CRDT, requer tipos de dados mais complexos no estado, uma vez que os nós e as arestas têm conjuntos de pares de valores-chave com propriedades, estes são considerados invariantes e criam a possibilidade de estados inválidos. Além disso, um gráfico de propriedade pode ser ligado a um esquema, e se assim for, torna-se um invariante do gráfico que deve ser mantido. Com este trabalho, pretendemos desenvolver CRDTs grafos especializados em Datalog (Soufflé) para múltiplos modelos grafos e múltiplas políticas de conflito já que o Datalog oferece um elevado nível de abstração, monotonicidade e segurança.
Descrição
Palavras-chave
CRDT Graph databases Weak Consistency Invariants Graph database Schemas Graph database models