Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-04-02T12:19:53Z No. of bitstreams: 1 CiroMoraisMedeiros_DISSERT.pdf: 4866075 bytes, checksum: 12574ac5a6867ff73a1dc45a5ef78478 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-04-04T11:51:20Z (GMT) No. of bitstreams: 1 CiroMoraisMedeiros_DISSERT.pdf: 4866075 bytes, checksum: 12574ac5a6867ff73a1dc45a5ef78478 (MD5) / Made available in DSpace on 2018-04-04T11:51:20Z (GMT). No. of bitstreams: 1 CiroMoraisMedeiros_DISSERT.pdf: 4866075 bytes, checksum: 12574ac5a6867ff73a1dc45a5ef78478 (MD5) Previous issue date: 2018-02-23 / A internet possibilitou a cria??o de um imenso espa?o de dados global, que pode ser acessado na forma de p?ginas web. Entretanto, p?ginas web s?o ideais para apresentar conte?do para seres humanos, mas n?o para serem interpretadas por m?quinas. Al?m disso, se torna dif?cil relacionar as informa??es armazenadas nos bancos de dados por tr?s dessas p?ginas. Para contornar esses problemas foi desenvolvido o Linked Data, um conjunto de boas pr?ticas para relacionamento e publica??o de dados. O formato padr?o recomendado pelo Linked Data para armazenamento e publica??o de dados relacionados ? o Resource Description Framework (RDF). Este formato utiliza triplas na forma (sujeito, predicado, objeto) para estabelecer relacionamentos entre os dados. Um banco de dados de triplas pode ser facilmente visualizado como um grafo, de maneira que as consultas s?o feitas por meio da defini??o de caminhos no grafo. SPARQL, a linguagem padr?o para consultas em grafos RDF, possibilita a defini??o de caminhos utilizando express?es regulares. Entretanto, express?es regulares t?m expressividade reduzida, insuficiente para algumas consultas desej?veis. Para contornar este problema, alguns trabalhos propuseram a utiliza??o de gram?ticas livres-de-contexto para definir os caminhos. Desenvolvemos um algoritmo para avalia??o de consultas de caminhos livres-de-contexto em grafos inspirado em t?cnicas de parsing top-down. Dado um grafo e uma consulta definida com base em uma gram?tica livre-de-contexto, nosso algoritmo identifica pares de v?rtices ligados por caminhos que formam palavras pertencentes ? linguagem gerada pela gram?tica. Argumentamos que nosso algoritmo ? correto e demonstramos outras propriedades importantes. O algoritmo apresenta complexidade c?bica de tempo de execu??o no pior caso em termos do n?mero de v?rtices no grafo. Implementamos o algoritmo proposto e avaliamos seu desempenho com bancos de dados RDF e com grafos sint?ticos para confirmar sua efici?ncia. / The internet has enabled the creation of an immense global data space, that may be accessed in the form of web pages. However, web pages are ideal for presenting content to human beings, but not to be interpreted by machines. In addition, it becomes difficult to relate the information stored in the databases behind these pages. To overcome those problems, the Linked Data was developed as a set of good practices for relating and publishing data. The standard format recommended by Linked Data for storing and publishing related data is RDF. This format uses triples in the form (subject, predicate, object) to stabilish relationships between the data. A triplestore can be easily visualized as a graph, so queries are made by defining paths in the graph. SPARQL, the standard query language for RDF graphs, supports the definition of paths using regular expressions. However, regular expressions have reduced expressiveness, insufficient for some desirable queries. In order to overcome this problem, some studies have proposed the use of context-free grammars to define the paths. We present an algorithm for evaluating context-free path queries in graphs inspired by top-down parsing techniques. Given a graph and a query defined over a contextfree grammar, our algorithm identifies pairs of vertices linked by paths that form words of the language generated by the grammar. We argue that our algorithm is correct and demonstrate other important properties of it. It presents cubic worst-case runtime complexity in terms of the number of vertices in the graph. We implemented the proposed algorithm and evaluated its performance with RDF databases and synthetic graphs to confirm its efficiency.