Maximal tractable fragments of the region connection calculus: A complete analysis

We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with ′H₈, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.