Existing structural tractability results for ORDER BY queries are extended to the general framework of tree projections, which encompasses all known polynomial-time decomposition methods, and to more general kinds of ranking criteria. Tractability results are also established for MAX (and MIN) queries, where one is interested just in the best answer, and for the more general TOP-K queries, where the best K ones have to be returned-note that, whenever one is interested in (possibly) exponentially-many answers, tractability means that the desired solutions can be computed with polynomial delay.
Structural tractability of order by queries
Greco, Gianluigi;Scarcello, Francesco
2013-01-01
Abstract
Existing structural tractability results for ORDER BY queries are extended to the general framework of tree projections, which encompasses all known polynomial-time decomposition methods, and to more general kinds of ranking criteria. Tractability results are also established for MAX (and MIN) queries, where one is interested just in the best answer, and for the more general TOP-K queries, where the best K ones have to be returned-note that, whenever one is interested in (possibly) exponentially-many answers, tractability means that the desired solutions can be computed with polynomial delay.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.
