Querying Graph Databases

摘要

Graph data is an emerging mdoel for representing a variety of database contexts ranging from object-oriented databases to hypertext data. Also many of the recursive queries that arise in relational databases are, in practice, graph traversals. In this paepr we present a language for searching graph-like databases. The language permits us to express paths in a graph by means of extended regular expressions. The proposed extension is based on the introduction of constructs which permits us i) to define a partial order on the paths used to search the graph and, consequently, on the answers of queries, and ii) to cut off, nondeterministically, tuples with low priority. We present an algebra for partially ordered relations and an algorithm for the computation of path queries. Finally, we present applications to hypertext databases such as the Web.