Y.Y. Li, K.S. Leung, et al.
J Combin Optim
We study here the complexity of evaluating quaries 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. © 1986.
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996