Practical Query Answering over HI(DL-LiteR) Knoledge Bases
M. Lenzerini, L. Lepore, and A. Poggi. Informal Proceedings of the 27th International Workshop on Description Logics, page 608-619. (2014)
Abstract
The language Hi(DL-LiteR) is obtained from DL-LiteR by adding
meta-modeling features, and is equipped with a query language that is able to
express higher-order queries. We investigate the problem of answering a particular
class of such queries, called instance higher-order queries posed over
Hi(DL-LiteR) knowledge bases (KBs). The only existing algorithm for this problem
is based on the idea of reducing the evaluation of a higher-order query Q
over a Hi(DL-LiteR) KB to the evaluation of a union of first-order queries over
a DL-LiteR KB, built from Q by instantiating all metavariables in all possible
ways. Even though of polynomial time complexity with respect to the size of the
KB, this algorithm turns out to be inefficient in practice. In this paper we present a
new algorithm, called Smart Binding Planner (SBP), that compiles Q into a program,
that issues a sequence of first-order conjunctive queries, where each query
has the goal of providing the bindings for meta-variables of the next ones, and the
last one completes the process by computing the answers to Q. We also illustrate
some experiments showing that, in practice, SBP is significantly more efficient
than the previous approach.
%0 Conference Paper
%1 lenzerini2014practical
%A Lenzerini, Maurizio
%A Lepore, Lorenzo
%A Poggi, Antonella
%B Informal Proceedings of the 27th International Workshop on Description Logics
%D 2014
%K Higher-Order-Logic OBDA optique-project
%P 608-619
%T Practical Query Answering over HI(DL-LiteR) Knoledge Bases
%X The language Hi(DL-LiteR) is obtained from DL-LiteR by adding
meta-modeling features, and is equipped with a query language that is able to
express higher-order queries. We investigate the problem of answering a particular
class of such queries, called instance higher-order queries posed over
Hi(DL-LiteR) knowledge bases (KBs). The only existing algorithm for this problem
is based on the idea of reducing the evaluation of a higher-order query Q
over a Hi(DL-LiteR) KB to the evaluation of a union of first-order queries over
a DL-LiteR KB, built from Q by instantiating all metavariables in all possible
ways. Even though of polynomial time complexity with respect to the size of the
KB, this algorithm turns out to be inefficient in practice. In this paper we present a
new algorithm, called Smart Binding Planner (SBP), that compiles Q into a program,
that issues a sequence of first-order conjunctive queries, where each query
has the goal of providing the bindings for meta-variables of the next ones, and the
last one completes the process by computing the answers to Q. We also illustrate
some experiments showing that, in practice, SBP is significantly more efficient
than the previous approach.
@inproceedings{lenzerini2014practical,
abstract = {The language Hi(DL-LiteR) is obtained from DL-LiteR by adding
meta-modeling features, and is equipped with a query language that is able to
express higher-order queries. We investigate the problem of answering a particular
class of such queries, called instance higher-order queries posed over
Hi(DL-LiteR) knowledge bases (KBs). The only existing algorithm for this problem
is based on the idea of reducing the evaluation of a higher-order query Q
over a Hi(DL-LiteR) KB to the evaluation of a union of first-order queries over
a DL-LiteR KB, built from Q by instantiating all metavariables in all possible
ways. Even though of polynomial time complexity with respect to the size of the
KB, this algorithm turns out to be inefficient in practice. In this paper we present a
new algorithm, called Smart Binding Planner (SBP), that compiles Q into a program,
that issues a sequence of first-order conjunctive queries, where each query
has the goal of providing the bindings for meta-variables of the next ones, and the
last one completes the process by computing the answers to Q. We also illustrate
some experiments showing that, in practice, SBP is significantly more efficient
than the previous approach.},
added-at = {2014-10-15T14:50:12.000+0200},
audience = {academic},
author = {Lenzerini, Maurizio and Lepore, Lorenzo and Poggi, Antonella},
biburl = {https://www.bibsonomy.org/bibtex/2a22b1374b5d412240d30666bf9a9a7a4/savo.fabio},
booktitle = {Informal Proceedings of the 27th International Workshop on Description Logics},
interhash = {b43268173507c92b2cffb6f68613563c},
intrahash = {a22b1374b5d412240d30666bf9a9a7a4},
keywords = {Higher-Order-Logic OBDA optique-project},
openaccess = {Yes},
pages = {608-619},
partneroptique = {UNIROMA1},
timestamp = {2016-12-01T17:36:35.000+0100},
title = {Practical Query Answering over HI(DL-LiteR) Knoledge Bases},
wpoptique = {WP4},
year = 2014,
yearoptique = {Y2}
}