Querying Graph Databases: An Overview

Querying Graph Databases: An Overview

Sherif Sakr (University of New South Wales, Sydney, Australia) and Ghazi Al-Naymat (University of New South Wales, Sydney, Australia)
DOI: 10.4018/978-1-60960-475-2.ch013
OnDemand PDF Download:
No Current Special Offers


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. This chapter provides an overview of different techniques for indexing and querying graph databases. An overview of several proposals of graph query language is also given. Finally, the chapter provides 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 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 = {g1,g2, ..., gn} where each member graph database member gi is denoted as (V, E, Lv,Le,Fv,Fe) where V is the set of vertices; E ⊆ V * V is the set of edges joining two distinct vertices; Lv is the set of vertex labels; Le is the set of edge labels; FV is a function V → Lv that assigns labels to vertices and Fe is a function E → Le 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: