Querying logical databases
Moshe Y. Vardi · 1985
We study here the complexity of evaluating queries in logical databases.We focus on Reiter's model of closed-world databases with unknown values.We show that in this setting query evalualion is harder than query evaluation for physical databases.For example, while lstorder queries over physical databases can be evaluated in logarithmic space, evaluation of lst-order queries in the studied model is co-NP-complete.We describe an approximation algorithm for query evaluation that enables one to implemenl a logical databases on the top of a standard database management system.