An Overview of Graph Indexing and Querying Techniques

Graph Data Structure

Graphs are very powerful modeling tool. They are used to model complicated structures and schemeless 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 where each member graph database member is denoted as where V is the set of vertices; is the set of edges joining two distinct vertices; is the set of vertex labels; is the set of edge labels; is a function that assigns labels to vertices and is a function 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.