Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-04-02T12:19:53Z No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-04-04T12:11:32Z (GMT) No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) / Made available in DSpace on 2018-04-04T12:11:32Z (GMT). No. of bitstreams: 1 FredDeCastroSantos_DISSERT.pdf: 1904530 bytes, checksum: 379e23c6c92c47609a52da136aeeb02e (MD5) Previous issue date: 2018-02-23 / A World Wide Web ? uma cole??o de informa??es sempre crescente. Esta informa??o ? distribu?da entre documentos diferentes, disponibilizados atrav?s do HTTP. Mesmo que essa informa??o seja acess?vel aos usu?rios na forma de artigos de not?cias, transmiss?es de ?udio, imagens e v?deos, os agentes de software geralmente n?o podem classific?-la. A falta de informa??es sem?nticas sobre esses documentos em um formato leg?vel por m?quina geralmente faz com que a an?lise seja imprecisa. Um n?mero significativo de entidades adotaram Linked Data como uma forma de adicionar informa??es sem?nticas aos seus dados, e n?o apenas public?-lo na Web. O resultado ? uma cole??o global de dados, chamada Web of Data, que forma um grafo global, composto por declara??es no formato RDF [22] de diversas fontes, cobrindo todos os tipos de t?picos. Para encontrar informa??es espec?ficas nesses grafos, as consultas s?o realizadas come?ando em um sujeito e analisando seus predicados nas instru??es RDF. Esses predicados s?o as conex?es entre o sujeito e o objeto, e um conjunto de trilhas forma um caminho de informa??o. O uso de HTTP como mecanismo padr?o de acesso a dados e RDF como modelo de dados padr?o simplifica o acesso a dados, o que nos motiva a pesquisar alternativas na forma como esses dados s?o buscados. Uma vez que a maioria das linguagens de consulta de banco de dados de grafo est?o na classe de Linguagens Regulares, n?s propomos seguir um caminho diferente e tentar usar uma classe de gram?tica menos restritiva, chamada Gram?tica Livre de Contexto Determin?stica, para aumentar a expressividade das consultas no banco de dados em grafo. Mais especificamente, aplicando o m?todo de an?lise LR(1) para encontrar caminhos em um banco de dados de grafo RDF. O principal objetivo deste trabalho ? prover meios para se permitir a utiliza??o de t?cnicas de reconhecimento de gram?ticas livres de contexto LR(1) para fazer consultas por caminhos formados pelas etiquetas das arestas em um banco de dados RDF. Fornecendo, como um resultado, uma ferramenta que se permita atingir melhor expressividade, efici?ncia e escalabilidade nestas consultas do que o que existe atualmente. Para atingir este objetivo, n?s implementamos um algoritmo baseado nas t?cnicas de reconhecimento LR(1), usando o GSS [30] ao inv?s de uma pilha, e permitimos ao usu?rio fazer consultas com uma gram?tica livre de contexto (LR1). Tamb?m analisamos a complexidade do nosso algoritmo e executamos alguns experimentos, comparando nossa solu??o com as outras propostas na literatura, mostrando que a nossa pode ter melhor desempenho em alguns cen?rios. / 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.