Querying Graph Databases: An Overview

Graph Data Structure

Graphs are vey powerful modeling tool. They are used to model complicated structures and schemaless data. In graph data structures, vertices and edges represent the entities and the relationships between them respectively. The attributes associated with these entities and relationships are called labels. A graph database D is defined as a collection of member graphs D = {g₁,g₂, ..., g_n} where each member graph database member g_i is denoted as (V, E, L_v,L_e,F_v,F_e) where V is the set of vertices; E ⊆ V * V is the set of edges joining two distinct vertices; L_v is the set of vertex labels; L_e is the set of edge labels; F_V is a function V → L_v that assigns labels to vertices and F_e is a function E → L_e that assigns labels to edges. In general, graph data structures can be classified according to the direction of their edges into two main classes:

• •

  Directed-labeled graphs: such as XML, RDF and traffic networks.

• •

  Undirected-labeled graphs: such as social networks and chemical compounds.

In principle, there are two main types of graph databases. The first type consists of few numbers of very large graphs such as the Web graph and social networks (non-transactional graph databases). The second type consists of a large set of small graphs such as chemical compounds and biological pathways (transactional graph databases). The main focus of this chapter is on giving an overview of the efficient indexing and querying mechanisms on the second type of graph databases.