LWI and Safari: A New Index Structure and Query Model for Graph Databases "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."
Has three data structures attribute-value index (AVI), graph location index (GLI) and label-walk index (LWI). AVI is an inverted index that stores gid values of graphs matching pecific attribute and value pairs. GLI indexes every graph entered into the system. LWI is used for structure based searches.
The AVI is string only. They claim that it's general purpose enough to do any labelled graph application.
Part of COMAD 2005.