I am working on the problem of distributed database query planning. Existing work [1] uses dynamic programming to search the potential query plan space and find the one with minimal cost. However, I am interested in an additional value (e.g. security risk) of a query plan, and would like to minimize this value also.

My current idea is to first minimize the cost goal to a certain extent, and then minimize the second goal. More specifically, we can let the user specify a Delta value, and then the dynamic programming algorithm can find a set of near optimal candidates whose costs fall in [optimal cost, optimal cost + Delta]. Then, we can minimize the second goal in this set.

My question is, is there any algorithmic work that offers similar capabilities? Or is there any method to modify a dynamic programming algorithm so that it can consider two goals simultaneously? Other relevant information will also be appreciated. Thank you!


[1] Kossmann, Donald, and Konrad Stocker. "Iterative dynamic programming: a new class of query optimization algorithms." ACM Transactions on Database Systems (TODS) 25.1 (2000): 43-82.

  • 1
    $\begingroup$ I don't know what is dependency of your goals to each other but if they are independent, then usually it's possible to do dynamic programming. e.g if for each of them you have to keep two dimensional table, when it comes to intersection of them you have to store a data in a 3-dimensional table. If you give an exact definition for your problem, it's easier for us to help you. $\endgroup$ – Saeed Aug 22 '14 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.