Theoretical questions in Databases

This tag should be used for theoretical questions related to Databases (roughly falling under arXiv's cs.DB - Databases).

The question must satisfy the usual scope requirements for cstheory as explained in the FAQ.