W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
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.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence