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
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Paul J. Steinhardt, P. Chaudhari
Journal of Computational Physics