Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/713
Full metadata record
DC FieldValueLanguage
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2005-04-12T08:15:19Z-
dc.date.available2005-04-12T08:15:19Z-
dc.date.issued2001-
dc.identifier.citationInformation Processing Letters, 79(3). p. 111-114-
dc.identifier.issn0020-0190-
dc.identifier.urihttp://hdl.handle.net/1942/713-
dc.description.abstractIn 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.-
dc.format.extent124703 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherElsevier-
dc.titleRewriting queries using views over monadic database schemas-
dc.typeJournal Contribution-
dc.identifier.epage114-
dc.identifier.issue3-
dc.identifier.spage111-
dc.identifier.volume79-
local.bibliographicCitation.jcatA1-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1016/S0020-0190(00)00180-0-
dc.identifier.isi000169495200002-
item.fulltextWith Fulltext-
item.validationecoom 2002-
item.contributorVAN DEN BUSSCHE, Jan-
item.fullcitationVAN DEN BUSSCHE, Jan (2001) Rewriting queries using views over monadic database schemas. In: Information Processing Letters, 79(3). p. 111-114.-
item.accessRightsOpen Access-
crisitem.journal.issn0020-0190-
crisitem.journal.eissn1872-6119-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
rewriting.pdf121.78 kBAdobe PDFView/Open
Show simple item record

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

Page view(s)

40
checked on Jul 1, 2022

Download(s)

162
checked on Jul 1, 2022

Google ScholarTM

Check

Altmetric


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