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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24969 |
| Date | 23 February 2018 |
| Creators | Medeiros, Ciro Morais |
| Contributors | 82500304434, Oliveira, Marcel Vinicius Medeiros, 02386943488, Medeiros, S?rgio Queiroz de, 00984989404, Bigonha, Mariza Andrade da Silva, 59191058600, Costa, Umberto Souza da, Musicante, Martin Alejandro |
| Publisher | PROGRAMA DE P?S-GRADUA??O EM SISTEMAS E COMPUTA??O, UFRN, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.1784 seconds