2016/03/31 by Gianluigi Greco, Greco, Gianluigi, Francesco Scarcello +1
Computer Science · #Advanced Database Systems and Queries #Constraint Satisfaction and Optimization #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1603.09617
Structural decomposition methods have been developed for identifying\ntractable classes of instances of fundamental problems in databases, such as\nconjunctive queries and query containment, of the constraint satisfaction\nproblem in artificial intelligence, or more generally of the homomorphism\nproblem over relational structures. Most structural decomposition methods can\nbe characterized through hypergraph games that are variations of the Robber and\nCops graph game that characterizes the notion of treewidth. In particular,\ndecomposition trees somehow correspond to monotone winning strategies, where\nthe escape space of the robber on the hypergraph is shrunk monotonically by the\ncops. In fact, unlike the treewidth case, there are hypergraphs where monotonic\nstrategies do not exist, while the robber can be captured by means of more\ncomplex non-monotonic strategies. However, these powerful strategies do not\ncorrespond in general to valid decompositions. The paper provides a general way\nto exploit the power of non-monotonic strategies, by allowing a "disciplined"\nform of non-monotonicity, characteristic of cops playing in a greedy way. It is\nshown that deciding the existence of a (non-monotone) greedy winning strategy\n(and compute one, if any) is tractable. Moreover, despite their\nnon-monotonicity, such strategies always induce valid decomposition trees,\nwhich can be computed efficiently based on them. As a consequence, greedy\nstrategies allow us to define new islands of tractability for the considered\nproblems properly including all previously known classes of tractable\ninstances.\n