Querying logical databases
We study here the complexity of evaluating queries in logical databases. We focus on Reither's model of closed-world databases with unknown values. We show that in this setting query evaluation is harder than query evaluation for physical databases. For example, while 1st-order queries over physical databases can be evaluated in logarithmic space, evaluation of 1st-order queries in the studied model is co-NP-complete. We describe an approximation algorithm for query evaluation that enables one to implement a logical database on the top of a standard database management system.
complexity of evaluating queries in logical databases
closed-world databases with unknown values
scientific article; zbMATH DE number 4016237