Optimization of Bound Disjunctive Queries with Constraints

Details Optimization of Bound Disjunctive Queries with Constraints Optimization of Bound Disjunctive Queries with Constraints

2004-06-07

arxiv.org/abs/cs/0406013v1

Computer Science

Logic in Computer Science

35 pages

Scientific paper

"To Appear in Theory and Practice of Logic Programming (TPLP)" This paper presents a technique for the optimization of bound queries over disjunctive deductive databases with constraints. The proposed approach is an extension of the well-known Magic-Set technique and is well-suited for being integrated in current bottom-up (stable) model inference engines. More specifically, it is based on the exploitation of binding propagation techniques which reduce the size of the data relevant to answer the query and, consequently, reduces both the complexity of computing a single model and the number of models to be considered. The motivation of this work stems from the observation that traditional binding propagation optimization techniques for bottom-up model generator systems, simulating the goal driven evaluation of top-down engines, are only suitable for positive (disjunctive) queries, while hard problems are expressed using unstratified negation. The main contribution of the paper consists in the extension of a previous technique, defined for positive disjunctive queries, to queries containing both disjunctive heads and constraints (a simple and expressive form of unstratified negation). As the usual way of expressing declaratively hard problems is based on the guess-and-check technique, where the guess part is expressed by means of disjunctive rules and the check part is expressed by means of constraints, the technique proposed here is highly relevant for the optimization of queries expressing hard problems. The value of the technique has been proved by several experiments.

Affiliated with

Also associated with

No associations

Rating

Optimization of Bound Disjunctive Queries with Constraints 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 Optimization of Bound Disjunctive Queries with Constraints, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of Bound Disjunctive Queries with Constraints will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-594572