Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability
We deal with three problems related to graph path queries. Most current graph query languages support regular path queries. However, some applications such as source-code analysis and genetics require context-free path queries. Context-free path queries use context-free languages. There is no sta...
Na minha lista:
Autor principal: | |
---|---|
Outros Autores: | |
Formato: | doctoralThesis |
Idioma: | pt_BR |
Publicado em: |
Universidade Federal do Rio Grande do Norte
|
Assuntos: | |
Endereço do item: | https://repositorio.ufrn.br/handle/123456789/50056 |
Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
id |
ri-123456789-50056 |
---|---|
record_format |
dspace |
spelling |
ri-123456789-500562022-12-08T22:50:37Z Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability Medeiros, Ciro Morais Musicante, Martin Alejandro http://lattes.cnpq.br/0837783758558004 https://orcid.org/0000-0001-5589-3895 http://lattes.cnpq.br/6034405930958244 Halfeld-Ferrari, Mirian Hara, Carmem Satie Goldbarg, Elizabeth Ferreira Gouvea http://lattes.cnpq.br/2888641121265608 Computação Context-free languages Graph path queries Graph minimization CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO We deal with three problems related to graph path queries. Most current graph query languages support regular path queries. However, some applications such as source-code analysis and genetics require context-free path queries. Context-free path queries use context-free languages. There is no standard notation for context-free languages simpler than context-free grammars. The evaluation of a context-free path query is more complex than a regular path query. Moreover, in some applications, it is desired to have the minimum graph that preserves answers to a given path query. To address each of those problems, we: (1) develop an alternative notation for expressing context-free languages; (2) design, implement and experiment with a context-free path query evaluation algorithm; and (3) formalize the formal-language-constrained graph minimization problem, for which we design solutions for the cases where the formal language is regular or context-free. Nós tratamos três problemas relacionados a consultas de caminhos em grafos. A maioria das linguagens de consulta em grafos atuais suporta consultas de caminhos regulares. No entanto, algumas aplicações, como análise de código-fonte e genética, exigem consultas de caminhos livres-de-contexto. As consultas de caminhos livres-de-contexto usam linguagens livres-de-contexto. Não existe uma notação padrão para linguagens livres-de-contexto mais simples do que gramáticas livres-de-contexto. A avaliação de uma consulta de caminhos livres-de-contexto é mais complexa do que a de uma consulta de caminhos regulares. Além disso, em algumas aplicações, deseja-se ter o grafo mínimo que preserve as respostas para uma determinada consulta de caminhos. Para resolver cada um desses problemas, nós: (1) desenvolvemos uma notação alternativa para expressar linguagens livres-de-contexto; (2) projetamos, implementamos e experimentamos um algoritmo de avaliação de consulta de caminhos livres-de-contexto; e (3) formalizamos o problema da minimização de grafos restrita a uma linguagem formal, para o qual desenvolvemos soluções para os casos em que a linguagem formal é regular ou livre-de-contexto. 2022-12-08T22:50:05Z 2022-12-08T22:50:05Z 2022-08-30 doctoralThesis MEDEIROS, Ciro Morais. Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability. Orientador: Martin Alejandro Musicante. 2022. 99f. Tese (Doutorado em Ciência da Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2022. https://repositorio.ufrn.br/handle/123456789/50056 pt_BR Acesso Aberto application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO |
institution |
Repositório Institucional |
collection |
RI - UFRN |
language |
pt_BR |
topic |
Computação Context-free languages Graph path queries Graph minimization CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
spellingShingle |
Computação Context-free languages Graph path queries Graph minimization CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO Medeiros, Ciro Morais Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
description |
We deal with three problems related to graph path queries. Most current graph query
languages support regular path queries. However, some applications such as source-code
analysis and genetics require context-free path queries. Context-free path queries use
context-free languages. There is no standard notation for context-free languages simpler
than context-free grammars. The evaluation of a context-free path query is more complex
than a regular path query. Moreover, in some applications, it is desired to have the
minimum graph that preserves answers to a given path query. To address each of those problems, we: (1) develop an alternative notation for expressing context-free languages; (2) design, implement and experiment with a context-free path query evaluation algorithm; and (3) formalize the formal-language-constrained graph
minimization problem, for which we design solutions for the cases where the formal
language is regular or context-free. |
author2 |
Musicante, Martin Alejandro |
author_facet |
Musicante, Martin Alejandro Medeiros, Ciro Morais |
format |
doctoralThesis |
author |
Medeiros, Ciro Morais |
author_sort |
Medeiros, Ciro Morais |
title |
Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
title_short |
Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
title_full |
Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
title_fullStr |
Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
title_full_unstemmed |
Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
title_sort |
improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability |
publisher |
Universidade Federal do Rio Grande do Norte |
publishDate |
2022 |
url |
https://repositorio.ufrn.br/handle/123456789/50056 |
work_keys_str_mv |
AT medeirosciromorais improvementsongraphpathqueriesexpressionevaluationandminimumweightsatisfiability |
_version_ |
1773959538154668032 |