LWI and Safari: A New Index Structure and Query Model for Graph Databases

• Main Authors: Srinath Srinivasa, Martin Maier
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2005
• Subjects: DML
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.7538; http://osl.iiitb.ac.in/~sri/pubs/COMAD2005_grace2.0.pdf

Graph databases are gaining importance in several emerging applications, especially molecular biology. In many existing approaches, such databases are regarded as a "schemaless " collection of labeled graphs. However, there are often user-defined schemes that help in limiting the search space while answering a query and to deliver meaningful results. Techniques based only on index structures do not exploit such situations. This paper presents our work on a graph database system called GRACE, where a Data Manipulation Language (DML) called Safari is proposed for graph databases and is closely integrated with structural indexes in the DBMS. Users may define schematic structures over a subset of graphs in the database and add them into the database as any other member graphs. The query model in turn can use such member graphs to define its search space in order to deliver more meaningful results. Queries can be composed, so that schemas defining search spaces can be generated dynamically. An augmenting index structure called labeled walk index (LWI) is also proposed that is extensively used for answering structural queries in Safari.