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!
|
| Resumo: | 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. |
|---|