Graph databases ppt

best free graph database and database languages ppt
OliviaCutts Profile Pic
OliviaCutts,France,Teacher
Published Date:01-08-2017
Your Website URL(Optional)
Comment
Semantic Data Management in Graph Databases -Tutorial at ESWC 2014- Maria-Esther Edna Maribel Cosmin Vidal Ruckhaus Acosta Basca Alejandro Flores USB 1  Graphs … Relationships among artists in Last.fm hp://sixdegrees.hu/last.fm/   Network of Friends in a High School Network structure of music genres and Network structure of Patent Citations their stylistic origin hp://www.infosysblogs.com/web2/2013/07/   2 hp://www.infosysblogs.com/web2/2013/01/network_structure_of_music_gen.html  Tasks to be Solved … Patterns of connections between people to understand functioning of society. Topological properties of graphs can be used to identify patterns that reveal phenomena, anomalies and potentially lead to a discovery. A significant increase of graph data in the form of social & biological information. 3  Tasks to be Solved … (2) In-degree Degree Out-Degree   Hubs The importance of the information relies on the relations more or equal than on the entities. 4   hp://www.infosysblogs.com/web2/2013/01/network_structure_of_music_gen.html  Basic Graph Operations Basic Graph operations that need to be efficiently performed:   Graph traversal.   Measuring path length.   Finding the most interesting central node.   Graph Invariants. 5  NoSQL-based Approaches These approaches can handle unstructured, unpredictable or messy data. Wide-column Document Key-value Graph stores Stores stores Databases BigTable Semi-structured Graph-based Berkeley DB model of oriented data Data Google MongoDB Cassandra 6  Agenda Morning Session 1 Basic Concepts & Background (60 min) 2 The Graph Data Management Paradigm ( 35 min.) Coffee Break (30 min.) Existing Graph Database Engines (75 min.) 3 4 Questions & Discussion (15 min.) Lunch Break (90 min.) 7  Agenda Afternoon Session 1 RDF-Based Engines (45 min) 2 Empirical Evaluation & Hands-On Description( 45 min.) Coffee Break (30 min.) Hands-On (75 min.) 3 4 Questions & Discussion (15 min.) 8  Abstract Data Type Graph G=(V, E, ,L) is a graph:   V is a finite set of nodes or vertices, e.g. V=Term, forOffice, Organization,…   E is a set of edges representing binary relationship between elements in V, e.g. E=(forOffice,Term) (forOffice,Organization),(Office,Organization)…   is a set of labels, e.g., =domain, range, sc, type, …   L is a function: V x V  , e.g., L=((forOffice,Term),domain), ((forOffice,Organization),range)… 10  Abstract Data Type Multi-Graph G=(V, E, ,L) is a multi-graph:   V is a finite set of nodes or vertices, e.g. V=Term, forOffice, Organization,…   E is a set of edges representing binary relationship between elements in V, e.g. E=(forOffice,Term) (forOffice,Organization),(Office,Organization)…   is a set of labels, e.g., =domain, range, sc, type, …   L is a function: V x V  PowerSet( ), e.g., L=((forOffice,Term),domain), ((forOffice,Organization),range), ((_id0,AZ),forOffice, forOrganization)… 11  Basic Operations Given a graph G, the following are operations over G:   AddNode(G,x): adds node x to the graph G.   DeleteNode(G,x): deletes the node x from graph G.   Adjacent(G,x,y): tests if there is an edge from x to y.   Neighbors(G,x): nodes y s.t. there is a node from x to y.   AdjacentEdges(G,x,y): set of labels of edges from x to y.   Add(G,x,y,l): adds an edge between x and y with label l.   Delete(G,x,y,l): deletes an edge between x and y with label l.   Reach(G,x,y): tests if there a path from x to y.   Path(G,x,y): a (shortest) path from x to y.   2-hop(G,x): set of nodes y s.t. there is a path of length 2 from x to y, or from y to x.   n-hop(G,x): set of nodes y s.t. there is a path of length n from x to y, or from y to x. 12  Implementation of Graphs Sakr and Pardede 2012 Compressed Adjacency Incidence Incidence Adjacency Adjacency List List Matrix Matrix Matrix Vertices and edges For each node a list Bidimensional Bidimensional Differential are stored as records of neighbors. representation of representation of encoding or objects. graph. graph. between two consecutive nodes If the graph is Each vertex stores Rows represent directed, incident edges. Vertices. Rows represent adjacency list of i Source Vertices. contains only the outgoing nodes of Each edge stores i. Columns incident nodes. represent edges Columns represent Destination Vertices. Cheaper for obtaining the An entry of 1 neighbors of a represents that node. Each entry with 1 the Source represents that Vertex is incident there is an edge to the Edge. from the source Not suitable for node to the checking if there destination node. is an edge between two nodes. 13  Adjacency List L3 L2 V1 V2 V3 V1 L1 V2 (V1,L2) (V3,L3) V3 V4 V4 (V1,L1) Properties:   Storage: O(V+E+L)   Adjacent(G,x,y): O(E)   Neighbors(G,x): O(E)   AdjacentEdges(G,x,y): O(E)   Add(G,x,y,l): O(E)   Delete(G,x,y,l): O(E) 14  Implementation of Graphs Sakr and Pardede 2012 Compressed Adjacency Incidence Adjacency Incidence Adjacency List List Matrix Matrix   Matrix   Vertices and edges For each node a list Bidimensional Differential are stored as records Bi-dimensional of neighbors. representation of encoding of objects. representation graph. between two of graph. consecutive nodes If the graph is Each vertex stores directed, incident edges. Rows Rows represent adjacency list of i represent Source Vertices. contains only the Vertices. outgoing nodes of Each edge stores i. incident nodes. Columns Columns represent represent Destination Vertices. edges Cheaper for obtaining the neighbors of a node. Each entry with 1 An entry of 1 represents represents that that the Source Vertex is there is an edge incident to the Edge. from the source Not suitable for node to the checking if there destination node. is an edge between two nodes. 15  Incidence List L3 L2 V1 V2 V3 V1 (destination,L2) (destination,L1) L1 V2 (source,L2) (source,L3) V3 (destination,L3) V4 V4 (source,L1) Properties: L1 (V4,V1)   Storage: O(V+E+L)   Adjacent(G,x,y): O(E) L2 (V2,V1)   Neighbors(G,x): O(E) L3 (V2,V3)   AdjacentEdges(G,x,y): O(E)   Add(G,x,y,l): O(E)   Delete(G,x,y,l): O(E) 16  Implementation of Graphs Sakr and Pardede 2012 Compressed Adjacency Incidence Adjacency Incidence Adjacency List List Matrix Matrix   Matrix   Vertices and edges For each node a list Bidimensional Differential are stored as records Bi-dimensional of neighbors. graph encoding of objects. representation representation. between two of graph. consecutive nodes If the graph is Each vertex stores directed, incident edges. Rows Rows represent adjacency list of i represent source vertices. contains only the Vertices. outgoing nodes of Each edge stores i. incident nodes. Columns Columns represent represent destination vertices. edges Cheaper for obtaining the neighbors of a Each non-null node. An entry of 1 represents entry represents that the Source Vertex is that there is an incident to the Edge. edge from the Not suitable for source node to checking if there the destination is an edge node. between two nodes. 17  Adjacency Matrix L3 L2 V1 V2 V3 V4 V1 V2 V3 V1 L1 L2 L3 V2 V3 V4 L1 V4 Properties: 2   Storage: O(V )   Adjacent(G,x,y): O(1)   Neighbors(G,x): O(V)   AdjacentEdges(G,x,y): O(E)   Add(G,x,y,l): O(E)   Delete(G,x,y,l): O(E) 18  Implementation of Graphs Sakr and Pardede 2012 Compressed Adjacency Incidence Adjacency Incidence Adjacency List List Matrix Matrix   Matrix   Vertices and edges For each node a list Bidimensional Differential are stored as records Bidimensional of neighbors. graph encoding of objects. graph representation. between two representation. consecutive nodes If the graph is Each vertex stores directed, incident edges. Rows Rows represent adjacency list of i represent source vertices. contains only the vertices. outgoing nodes of Each edge stores i. incident nodes. Columns Columns represent represent destination vertices. edges Cheaper for obtaining the neighbors of a Each non-null node. A non-null entry represents entry represents that the source vertex is that there is an incident to the edge. edge from the Not suitable for source node to checking if there the destination is an edge node. between two nodes. 19  Incidence Matrix L3 L2 V1 V2 V3 L1 L3 L2 destination destination V1 L1 source source V2 destination V3 V4 source V4 Properties:   Storage: O(VxE)   Adjacent(G,x,y): O(E)   Neighbors(G,x): O(VxE)   AdjacentEdges(G,x,y): O(E)   Add(G,x,y,l): O(V)   Delete(G,x,y,l): O(V) 20  Implementation of Graphs Sakr and Pardede 2012 Compressed Adjacency Incidence Adjacency Incidence Adjacency List List Matrix Matrix   Matrix   Vertices and edges For each node a list Bidimensional Differential are stored as records Bidimensional of neighbors. graph encoding of objects. graph representation. between two representation. consecutive nodes If the graph is Each vertex stores directed, incident edges. Rows Rows represent adjacency list of i represent source vertices. contains only the Vertices. outgoing nodes of Each edge stores i. incident nodes. Columns Columns represent represent destination vertices. edges Cheaper for obtaining the neighbors of a Each non-null node. A non-null entry represents entry represents that the source vertex is that there is an incident to the Edge. edge from the Not suitable for source node to checking if there the destination is an edge node. between two nodes. 21  

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.