Publication
Journal of Computer and System Sciences
Paper

Querying logical databases

View publication

Abstract

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.

Date

01 Jan 1986

Publication

Journal of Computer and System Sciences

Authors

Topics

Share