An Overview of Graph Indexing and Querying Techniques

An Overview of Graph Indexing and Querying Techniques

Sherif Sakr (University of New South Wales, Australia) and Ghazi Al-Naymat (University of Tabuk, Saudi Arabia)
Copyright: © 2012 |Pages: 18
DOI: 10.4018/978-1-61350-053-8.ch004
OnDemand PDF Download:


Recently, there has been a lot of interest in the application of graphs in different domains. Graphs have been widely used for data modeling in different application domains such as: chemical compounds, protein networks, social networks and Semantic Web. Given a query graph, the task of retrieving related graphs as a result of the query from a large graph database is a key issue in any graph-based application. This has raised a crucial need for efficient graph indexing and querying techniques. In this chapter, we provide an overview of different techniques for indexing and querying graph databases. An overview of several proposals of graph query language is also given. Finally, we provide a set of guidelines for future research directions.
Chapter Preview


In this section, we introduce the basic terminologies used in this chapter and give the formal definition of graph querying problems.

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.

Complete Chapter List

Search this Book: