masterThesis
A mechanism to evaluate context-free queries inspired in LR(1) parsers over graph databases
Fecha
2018-02-23Registro en:
SANTOS, Fred de Castro. A mechanism to evaluate context-free queries inspired in LR(1) parsers over graph databases. 2018. 85f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2018.
Autor
Santos, Fred de Castro
Resumen
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.