Processing unions of conjunctive queries with negation under limited access patterns

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We study the problem of answering queries over sources with limited access patterns. The problem is to decide whether a given query Q is feasible, i.e., equivalent to an executable query Q' that observes the limited access patterns given by the sources. We characterize the complexity of deciding feasibility for the classes CQ (conjunctive queries with negation) and UCQ (unions of CQ queries): Testing feasibility is just as hard as testing containment and therefore P2-complete. We also provide a uniform treatment for CQ, UCQ, CQ and UCQ by devising a single algorithm which is optimal for each of these classes. In addition, we show how one can often avoid the worst-case complexity by certain approximations: At compile-time, even if a query Q is not feasible, we can find efficiently the minimal executable query containing Q. For query answering at runtime, we devise an algorithm which may report complete answers even in the case of infeasible plans and which can indicate to the user the degree of completeness for certain incomplete answers.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsElisa Bertino, Stavros Christodoulakis, Manolis Koubarakis, Dimitris Plexousakis, Vassilis Christophides, Klemens Bohm, Elena Ferrari
PublisherSpringer-Verlag Berlin Heidelberg
Pages422-440
Number of pages19
ISBN (Electronic)9783540212003
DOIs
StatePublished - 2004
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2992
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Processing unions of conjunctive queries with negation under limited access patterns'. Together they form a unique fingerprint.

Cite this