Leo Liberti, James Ostrowski
Journal of Global Optimization
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.
Leo Liberti, James Ostrowski
Journal of Global Optimization
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Jianke Yang, Robin Walters, et al.
ICML 2023
Da-Ke He, Ashish Jagmohan, et al.
ISIT 2007