Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/713

Title: Rewriting queries using views over monadic database schemas
Issue Date: 2001
Publisher: Elsevier
Citation: 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.
URI: http://hdl.handle.net/1942/713
DOI: 10.1016/S0020-0190(00)00180-0
ISI #: 000169495200002
ISSN: 0020-0190
Category: A1
Type: Journal Contribution
Validation: ecoom, 2002
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
N/A121.78 kBAdobe PDF

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