Query-oriented Relaxation for Cardinality Assurance
Manasi Vartak · Digital WPI · 2009
Although a large number of queries have cardinality constraints, database engines have minimal support for cardinality assurance. Inability to meet cardinality constraints requires a user to undertake a cumbersome trial-and-error refinement process. A possible solution to this problem is query relaxation. However, attaining exact query cardinality is a NP-Hard problem. In this work we present QRelX, a novel algorithm for cardinality assurance that relaxes queries efficiently while minimizing relaxation of result queries. For this purpose, QRelX uses a combination of query space transformation, layer-based traversal and incremental cardinality estimation. Preliminary experiments indicate that QRelX is more efficient than traditional algorithms and it successfully minimizes relaxation.