  We present a theoretical study of a problem arising in database query
optimization, which we call as The Common Prefix Problem. We present a
$(1-o(1))$ factor approximation algorithm for this problem, when the underlying
graph is a binary tree. We then use a result of Feige and Kogan to show that
even on stars, the problem is hard to approximate.

Data Structures and Algorithms;Computational Complexity