Querying logical databases (Q579967)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Querying logical databases |
scientific article |
Statements
Querying logical databases (English)
0 references
1986
0 references
We study here the complexity of evaluating queries 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.
0 references
relational databases
0 references
complexity of evaluating queries in logical databases
0 references
closed-world databases with unknown values
0 references
approximation algorithm
0 references
database management
0 references
