Querying logical databases
type: Item
instance of: scholarly article
title: Querying logical databases
zbMATH Open document ID: 0625.68079
DOI: 10.1016/0022-0000(86)90016-4
author: Moshe Y. Vardi
published in: Journal of Computer and System Sciences
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 4016237
zbMATH Keywords: relational databases
zbMATH Keywords: complexity of evaluating queries in logical databases
zbMATH Keywords: closed-world databases with unknown values
zbMATH Keywords: approximation algorithm
zbMATH Keywords: database management
MaRDI profile type: Publication
full work available at URL: 0022-0000(86)90016-4
OpenAlex ID: W2032728598
cites work: Structure and complexity of relational queries
cites work: Q4198056
cites work: Null values in a relational data base
cites work: In memoriam Witold Lipski, jun. (1949--1985)
cites work: The Semantics of Predicate Logic as a Programming Language
cites work: A logic for default reasoning
cites work: The polynomial-time hierarchy
description: scientific article; zbMATH DE number 4016237