?????: A unifying data model for graph databases - Leitura de Draft

Artigo draft a ser submetido ao GRADES workshop sobre a proposta de um modelo de dados que considera o 1G da Amazon e o DG do Millenium. 

directed labeled graphs with edge id == hiper relational, directed, attributed and labeled multi graphs

Comentários: 

Rename RDF* to RDF-Star

    https://github.com/w3c/rdf-star/issues/20

There is another drawback of reification. It is mentioned in the HINGE and StarE (KG Embeddings) proposals that reification also includes noise in the generated ML models [Rosso et al 2020], [Yu and Yang 2018]. Learning embeddings loss in hyper relational KGs is observed when not differentiating triples (asserted edges) referring to facts from triples associated with qualifiers (nested edges) as well as ignoring the interaction between multiple qualifiers for the same fact. The extra triples artificially introduced by reification approaches confuse the embeddings generation methods, preventing them from capture important structural properties of the original input graph.

"However, directed labelled graphs are sometimes too simple. While they elegantly represent binary relations, they are cumbersome when representing higher arity relations."

Consider that "higher arity relations" ends up referring to relations with an arity > 2, which forms a hypergraph and it is not the case of this model. Instead of, the expression "hyper relational data" should be used. As far as I know only MARS supports hyperedges (hypergraph).

"However, we can only represent one of the statements (without reification), as we can only have one distinct node per edge; if we add the qualifiers for both statements, then we would not know which start date pairs with which end date, for example."

That is, RDF-Star is not able to represent a multigraph.

"Here (O,γ ) is just an ordinary graph, where you can have edges on edges."

That is, (O,γ ) represents a hyper relational (multi)graph. Consider to add a statement defintion as S → O × O × O × P (O × O) where P denotes the power set.

kgtk graph data model (which is also node1, label, node2, edge id) could be included in section 3.2 and in Table 1.

Edge type/label: Yes
Node label: No
Label as node: No
Edge annotation: Yes
Node annotation: Yes
External annotation: No
Annotation name as node: No
Annotation value as node: No
Edge as node: Yes
Edge as nodes: Yes
Nested edge nodes: Yes
Graph as node: No

Add a line for "Edges connecting the same pairs of nodes" (multigraph) in table 1 and only RDF-Star doesn't support it.

"To the best of our knowledge, our work is the first to describe a query language, storage and indexing schemes, query planner – and ultimately a fully-fledged graph database engine – built specifically for this model." 

This paragraph is about GraphDB Millenium and not about the graph data model.

The graph query language (GQL) should support basic graph pattern (BGP) and complex graph patterns (CGP) that (i) retrieves edges with key-value pairs of their nested edges; (ii) retrieves edges filtering on key-value pairs of their nested edges; and (iii) joins edges based on key-value pairs of their nested edges. In terms of navigational graph patterns (NGP), it should support variable length property path that retrieves edges filtering on key-value pairs of their nested edges and that also navigates into nested edges.

BGP, CGP e NGP definitions from [Angles et al 2017]

Angles, R., Arenas, M., Barceló, P., Hogan, A., Reutter, J.L., & Vrgoc, D. (2017). Foundations of Modern Query Languages for Graph Databases. ACM Computing Surveys (CSUR), 50, 1 - 40.

Paolo Rosso, Dingqi Yang, and Philippe Cudré-Mauroux. 2020. Beyond Triplets: Hyper-Relational Knowledge Graph Embedding for Link Prediction. In Proceedings of The Web Conference 2020 (WWW '20). Association for Computing Machinery, New York, NY, USA, 1885–1896.

Donghan Yu and Yiming Yang. 2018. Improving Hyper-Relational Knowledge Graph Completion. ACM Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY. ACM, New York, NY, USA, 5 pages.

Maximilian Marx, Markus Krötzsch, and Veronika Thost. 2017.  Logic on MARS: ontologies for generalised property graphs. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI'17). AAAI Press, 1188–1194.

Patel-Schneider, P. F., & Martin, D. (2020). Wikidata on MARS. ArXiv Preprint ArXiv:2008.06599.

Artigo final

Renzo Angles, Aidan Hogan, Ora Lassila, Carlos Rojas, Daniel Schwabe, Pedro Szekely, and Domagoj Vrgoč. 2022. Multilayer graphs: a unified data model for graph databases. In Proceedings of the 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA '22). Association for Computing Machinery, New York, NY, USA, Article 11, 1–6. https://doi.org/10.1145/3534540.3534696

Specifically we propose multilayer graphs: an abstract graph model that extends directed labeled graphs with edge ids. ... What we propose here is much simpler: a concise data model for graphs.

While using reification is a valid solution, its main drawbacks are that: (i) it can easily become cumbersome and inefficient for querying; and (ii) it introduces semantics into graph data (requiring that an edge labeled replaces has a particular meaning for instance).
To circumvent this issue, a number of graph models have been proposed to capture higher-arity relations more concisely, including property graphs [ 8] and RDF* [12, 13 ]. However, both have limitations that render them incapable of modeling the statements shown in Figure 1 without resorting to reification [14].

Per the previous section, a key feature needed to model complex statements – such as multiple presidencies of a particular person – is the ability to refer to the entire statement repeatedly. More precisely, we need to be able to reference an edge as it if were a node (or possibly multiple nodes). A multilayer graph captures this feature through edge ids

Given that the multilayer graph model is intended to be an abstract data model, we do not define any further details on 𝑂 at this level, but a concrete data model based on multilayer graphs may choose to divide 𝑂 into different types of (possibly disjoint) terms – such as node ids, edge ids, edge labels, datatype values, IRIs, etc. – and restrict which terms can appear in which positions of 𝛾.

[termos, elementos, primitivos, construtos]

3.2 The layering

The layers in multilayer graphs result from the nested use of edge ids. Given a multilayer graph 𝐺 = (𝑂, 𝛾), the layer for an object 𝑜 ∈ 𝑂, denoted as layer(𝑜), is defined as follows. If 𝑜 is not an edge id (not in the codomain of 𝛾), then layer(𝑜) = 0.

[Cada statement está na camada 1, os qualificadores na camada 2, e o que for ligado a seguir nas demais camadas]

The notion of layering lies inherent in other graph models. In Wikidata, qualifiers can be seen as forming a layer 2 graph (per Figure 6). The properties (attribute–value pairs) in property graphs are akin to layer 2 metadata, though strictly speaking the values do not form nodes. In RDF*, quoted triples can be nested arbitrarily, allowing for arbitrary layers; again, however, RDF* does not directly support quoting the same triple multiple times.

3.5 Querying multilayer graphs

Graph query languages are typically founded on basic graph patterns [2 , 10 ]. We can define a basic graph pattern for multilayer graphs as a pair 𝑄 = (𝑋, 𝜉), where 𝑋 ⊆ Obj ∪ Var is a set of objects and variables, and 𝜉 : 𝑋 → 𝑋 × 𝑋 × 𝑋 . Given a multilayer graph 𝐺 = (𝑂, 𝛾), let 𝜇 : Var∩𝑋 → 𝑂 denote a mapping from the variables of 𝑋 to 𝑂. Then we define the evaluation 𝑄 (𝐺) = {𝜇 | 𝜇 (𝜉) ⊆ 𝛾 }, where 𝜇 (𝜉) is the image of 𝜉 under 𝜇. Path queries can be evaluated on the directed labeled graph that forms the codomain of 𝛾. Other relational features can be layered on top of these base queries to transform or combine sets of solution mappings [2]

[Caminhos podem navegar pelos qualificadores?]