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

Formale Metadaten

Titel
The Selfish Models Property: Bounding the Complexity of Query Containment and Entailment Problems
Serientitel
Anzahl der Teile
155
Autor
Lizenz
CC-Namensnennung 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr2019
SpracheEnglisch

Inhaltliche Metadaten

Fachgebiet
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.