The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. In particular, we need methods that are effective for the general case, such as non-linear programs, as well as for specialized cases, such as left-recursive linear programs. In this paper, we propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown method, is based on the fact that each chain query can be associated with a context-free language, and that a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular factorized left-linear program. The proposed method generalizes and unifies previous techniques such as the ‘counting’ and ‘right-, left-, mixed-linear’ methods. It succeeds in reducing many non-linear programs to query-equivalent linear ones.

Grammars and Automata to Optimize Chain Logic Queries

GRECO, Sergio;Saccà D.;
1999-01-01

Abstract

The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. In particular, we need methods that are effective for the general case, such as non-linear programs, as well as for specialized cases, such as left-recursive linear programs. In this paper, we propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown method, is based on the fact that each chain query can be associated with a context-free language, and that a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular factorized left-linear program. The proposed method generalizes and unifies previous techniques such as the ‘counting’ and ‘right-, left-, mixed-linear’ methods. It succeeds in reducing many non-linear programs to query-equivalent linear ones.
Datalog; Chain queries; Query optimization
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/150160
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact