We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems

Formal Metadata

Title
The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date2019
LanguageEnglish

Content Metadata

Subject Area
Genre
Abstract
Query containment is the fundamental problem of deciding, given two database queries, if the result of the first query is always contained in the result of the second query. For a number of established query classes, an instance of this problem can be decided by computing a set of models of the first query, and then evaluating the second query on each of the models. We formalize this phenomenon by introducing the selfish models property; this property gives an avenue for establishing both the decidability of and complexity upper bounds for containment problems. Using this property, we show how existing results can be uniformly derived, and we present two significant novel positive results for first-order query containment problems, exhibiting complexity upper bounds for containment problems that were not previously known to be decidable.