  We propose joinwidth, a new complexity parameter for the Constraint
Satisfaction Problem (CSP). The definition of joinwidth is based on the
arrangement of basic operations on relations (joins, projections, and pruning),
which inherently reflects the steps required to solve the instance. We use
joinwidth to obtain polynomial-time algorithms (if a corresponding
decomposition is provided in the input) as well as fixed-parameter algorithms
(if no such decomposition is provided) for solving the CSP.
  Joinwidth is a hybrid parameter, as it takes both the graphical structure as
well as the constraint relations that appear in the instance into account. It
has, therefore, the potential to capture larger classes of tractable instances
than purely structural parameters like hypertree width and the more general
fractional hypertree width (fhtw). Indeed, we show that any class of instances
of bounded fhtw also has bounded joinwidth, and that there exist classes of
instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth
properly generalizes bounded fhtw.
  We further show that bounded joinwidth also properly generalizes several
other known hybrid restrictions, such as fhtw with degree constraints and
functional dependencies. In this sense, bounded joinwidth can be seen as a
unifying principle that explains the tractability of several seemingly
unrelated classes of CSP instances.
