Rewriting Ontological Queries into Small Nonrecursive Datalog Programs

Details Rewriting Ontological Queries into Small Nonrecursive Datalog Programs Rewriting Ontological Queries into Small Nonrecursive Datalog Programs

2011-06-19

arxiv.org/abs/1106.3767v3

Computer Science

Artificial Intelligence

A shorter version is presented at the 24th International Workshop on Description Logics, DL 2011, Barcelona, Spain, July 13-16

Scientific paper

We consider the setting of ontological database access, where an Abox is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a Tbox T formulated in DL-Lite or Linear Datalog+/-. It is well-known that (T,q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog? or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of T and q. This gives rise to the interesting question of whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate (T,q) into a polynomially sized equivalent nonrecursive Datalog program P.

Affiliated with

Also associated with

No associations

Rating

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rewriting Ontological Queries into Small Nonrecursive Datalog Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rewriting Ontological Queries into Small Nonrecursive Datalog Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-723331