A Bottom-Up Algorithm for Answering Context-Free Path Queries in Graph Databases

Many computing applications require processing of data that are directly collected from the Internet. In this context, the use of the Resource Description Framework (RDF) has became a common feature. The query and analysis of RDF data is paramount to explore the full potential of the data available on the Web. Query languages for RDF graph databases rely on the use of regular expressions to identify paths over the data. Some interesting queries, such as same-generation queries, cannot be expressed by regular expressions. We are interested in extending the expressiveness of queries over graph databases by using paths defined by context-free grammars. We introduce a new query algorithm to process context-free path queries over graph databases. Our approach is inspired by the LR(1) parsing techniques. A prototype was implemented and experiments were conducted to validate and compare the results of our algorithm with those obtained by similar approaches.