Pushing constraint selections

AbstractBottom-up evaluation of a program-query pair in a constraint query language often computes only ground facts. Constraints do not contribute to answers, but are used only to prune derivations. The Magic Templates evaluation cannot utilize all the constraint information present in such program-query pairs while computing only ground facts. In general, constraint facts are computed, making the resulting evaluation more expensive.We describe an optimization that propagates constraints occuring in the program and the query, such that the rewritten program fully utilizes the constraint information present in the original program. Only constraint-relevant facts are computed, and if the evaluation of the original program computed only ground facts, so does the evaluation of the rewritten program. Our procedure can be combined with the Magic Templates transformation to propagate query binding information in addition to the constraint information. We show that it is always better to defer the application of Magic Templates