COMAD 2005 START ConferenceManager    

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

Srinath Srinivasa, Martin Maier, Mandar R. Mutalikdesai, Gowrishankar K. A., Gopinath P. S.

Presented at 11th International Conference on Management of Data (COMAD 2005) (COMAD 2005), Goa, India, January 6-8, 2005


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 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.

START Conference Manager (V2.47.4)