Title: Join ordering for constraint handling rules
Authors: De Koninck, Leslie ×
Sneyers, Jon #
Issue Date: 2007
Publisher: U.Porto
Host Document: Proceedings of the Fourth Workshop on Constraint Handling Rules pages:107-121
Conference: Workshop on Constraint Handling Rules edition:4 location:Porto, Portugal date:September 8, 2007
Abstract: Join ordering is the problem of finding cost optimal execution plans for matching multi-headed rules. In the context of Constraint Handling Rules, this topic has received limited attention so far, even though it is of great importance for efficient CHR execution. We present a formal cost model for joins and investigate the possibility of join optimization at runtime. We propose some heuristic approximations of the parameters of this cost model, for both the static and dynamic case. We discuss an O(n log n) optimization algorithm for the special case of acyclic join graphs. However, in general, join order optimization is an NP-complete problem. Finally, we identify some classes of cyclic join graphs that can be reduced to acyclic ones.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
paper.pdf Published 188KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.