  Numerous fundamental database and reasoning problems are known to be NP-hard
in general but tractable on instances where the underlying hypergraph structure
is $\beta$-acyclic. Despite the importance of many of these problems, there has
been little success in generalizing these results beyond acyclicity.
  In this paper, we take on this challenge and propose nest-set width, a novel
generalization of hypergraph $\beta$-acyclicity. We demonstrate that nest-set
width has desirable properties and algorithmic significance. In particular,
evaluation of boolean conjunctive queries with negation is tractable for
classes with bounded nest-set width. Furthermore, propositional satisfiability
is fixed-parameter tractable when parameterized by nest-set width.
