A mechanism to evaluate context-free queries inspired in LR(1) parsers over graph databases
Fred de Castro Santos · 2018
A World Wide Web e uma colecao de informacoes sempre crescente. Esta informacao e distribuida entre documentos diferentes, disponibilizados atraves do HTTP. Mesmo que essa informacao seja acessivel aos usuarios na forma de artigos de noticias, transmissoes de audio, imagens e videos, os agentes de software geralmente nao podem classifica-la. A falta de informacoes semânticas sobre esses documentos em um formato legivel por maquina geralmente faz com que a analise seja imprecisa. Um numero significativo de entidades adotaram Linked Data como uma forma de adicionar informacoes semânticas aos seus dados, e nao apenas publica-lo na Web. O resultado e uma colecao global de dados, chamada Web of Data, que forma um grafo global, composto por declaracoes no formato RDF [22] de diversas fontes, cobrindo todos os tipos de topicos. Para encontrar informacoes especificas nesses grafos, as consultas sao realizadas comecando em um sujeito e analisando seus predicados nas instrucoes RDF. Esses predicados sao as conexoes entre o sujeito e o objeto, e um conjunto de trilhas forma um caminho de informacao. O uso de HTTP como mecanismo padrao de acesso a dados e RDF como modelo de dados padrao simplifica o acesso a dados, o que nos motiva a pesquisar alternativas na forma como esses dados sao buscados. Uma vez que a maioria das linguagens de consulta de banco de dados de grafo estao na classe de Linguagens Regulares, nos propomos seguir um caminho diferente e tentar usar uma classe de gramatica menos restritiva, chamada Gramatica Livre de Contexto Deterministica, para aumentar a expressividade das consultas no banco de dados em grafo. Mais especificamente, aplicando o metodo de analise LR(1) para encontrar caminhos em um banco de dados de grafo RDF. O principal objetivo deste trabalho e prover meios para se permitir a utilizacao de tecnicas de reconhecimento de gramaticas 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, eficiencia e escalabilidade nestas consultas do que o que existe atualmente. Para atingir este objetivo, nos implementamos um algoritmo baseado nas tecnicas de reconhecimento LR(1), usando o GSS [30] ao inves de uma pilha, e permitimos ao usuario fazer consultas com uma gramatica livre de contexto (LR1). Tambem analisamos a complexidade do nosso algoritmo e executamos alguns experimentos, comparando nossa solucao com as outras propostas na literatura, mostrando que a nossa pode ter melhor desempenho em alguns cenarios.