Please use this identifier to cite or link to this item:
Title: Rewriting queries using views over monadic database schemas
Authors: VAN DEN BUSSCHE, Jan 
Issue Date: 2001
Publisher: Elsevier
Source: Information Processing Letters, 79(3). p. 111-114
Abstract: In research in databases and AI, the problem of rewriting queries using views has received a lot of interest recently; we refer to the nice survey by Levy for background. In this short note, we offer two remarks on the computational complexity of this problem. First, we offer a most simple proof that the problem is NP-complete. We should specify immediately that we work with the contained rewriting variant of the notion of rewriting queries using views. For the equivalent rewriting variant, an NP-completeness proof was already published by Levy et al. Second, we restrict attention to database schemas with unary relations only. Such “monadic” database schemas have classically provided a special case where difficult problems become easy. For example, satisfiability of relational calculus sentences in general is undecidable, but is decidable if the database schema is monadic. We show that, over monadic database schemas, the problem of rewriting queries using views is efficiently solvable.
Document URI:
ISSN: 0020-0190
e-ISSN: 1872-6119
DOI: 10.1016/S0020-0190(00)00180-0
ISI #: 000169495200002
Category: A1
Type: Journal Contribution
Validations: ecoom 2002
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
rewriting.pdf121.78 kBAdobe PDFView/Open
Show full item record


checked on Sep 2, 2020

Page view(s)

checked on May 24, 2022


checked on May 24, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.