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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/24970 |
| Date | 23 February 2018 |
| Creators | Santos, Fred de Castro |
| Contributors | 72031220500, Oliveira, Marcel Vinicius Medeiros, 02386943488, Bigonha, Mariza Andrade da Silva, 59191058600, Medeiros, S?rgio Queiroz de, 00984989404, Musicante, Martin Alejandro, Costa, Umberto Souza da |
| Publisher | PROGRAMA DE P?S-GRADUA??O EM SISTEMAS E COMPUTA??O, UFRN, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| 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.0026 seconds