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

Abstract

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
Top

Preliminaries

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 978-1-61350-053-8.ch004.m01 where each member graph database member 978-1-61350-053-8.ch004.m02 is denoted as 978-1-61350-053-8.ch004.m03 where V is the set of vertices; 978-1-61350-053-8.ch004.m04 is the set of edges joining two distinct vertices; 978-1-61350-053-8.ch004.m05 is the set of vertex labels; 978-1-61350-053-8.ch004.m06 is the set of edge labels; 978-1-61350-053-8.ch004.m07 is a function 978-1-61350-053-8.ch004.m08 that assigns labels to vertices and 978-1-61350-053-8.ch004.m09 is a function 978-1-61350-053-8.ch004.m10 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:
Reset