A mechanism to evaluate context-free queries inspired in LR(1) parsers over graph databases

Abstract

The World Wide Web is an always increasing collection of information. This information is spread among different documents, which are made available by using the HTTP. Even though this information is accessible to users in the form of news articles, audio broadcasts, images and videos, software agents often cannot classify it. The lack of semantic information about these documents in a machine-readable format usually makes the analysis inaccurate. A significant number of entities have adopted Linked Data as a way to add semantic information to their data, not just publishing it on the Web. The result is a global data collection, called the Web of Data, which forms a global graph, consisting of RDF [22] statements from numerous sources, covering all sorts of topics. To find specific information in this graph, queries are performed starting at a subject and analyzing their predicates in the RDF statements. These predicates are the connections between the subject and object, and a set of traces forms an information path. The use of HTTP as a standardized data access mechanism and RDF as a standard data model simplifies the data access, but accessing heterogeneous data on distinct locations may have an increased time complexity and current query languages have a reduced query expressiveness, which motivates us to research alternatives in how this data is queried. This reduced expressiveness happens because most query languages belong to the class of Regular Languages. The main goal of this work is to use LR(1) context-free grammar processing techniques to search for context-free paths over RDF graph databases, providing, as result, a tool which allows better expressiveness, efficiency and scalability in such queries than what is proposed today. To achieve that, we implemented an algorithm based on the LR(1) parsing technique that uses the GSS [30] structure instead of a stack, and give means for the user to input queries with an LR(1) context-free grammar. Also, we analyze our algorithm’s complexity and make some experiments, comparing our solution to other proposals present in the literature and show that ours can have better performance in given scenarios.