The main consequence of Lemma is that we can limit ourselves in the analysis of subalgebras in MC to these subalgebras which contain the empty relation Moreover since a network of constraints represents the relations in an implicit way when an edge of a network is not labelled we should interpret it as representing the universal relation  Therefore  the universal relation should be a member of the subalgebras to which we are interested in  We call algebras which contain both the empty and the universal relations expressive algebras expressive subalgebras  we denominate M i where i varies between There are to In Tables expressive subalgebras of MC
of Appendix A  the are listed Lemma 3 Given a subset A of MC-4, A is an expressive subalgebra iff A is one of the subalgebras Mi with i between 0 and 101 .

## Proof

Consider a subset A of MC We test the closure of A by a LISP program which computes the closure by composition intersection and converse of a subset of MC
and test the presence of empty and universal relation in A by the obvious membership test  The LISP
procedure TRANSITIVE CLOSURE is listed in Online Appendix     which accompanies this article The test succeeds for the subalgebras Mi with i between and and fails for all 16 _
the other subsets of MC The claim is therefore proved
□
The following technical lemma shows that some of the subalgebras individuated above are NP hard  There are    subalgebras of the which are intractable by Lemma The algebras are presented in Table of Appendix A The proof of Lemma is a trivial consequence of the proof of Theorem Lemma 4 Given a subalgebra A of MC-4, if A contains the relations CNO and {CGPP,
CGPP-1 } then MSAT A is NP-hard.

In the next three subsections we show that three maximal tractable subclasses of MC can be found  so that the only intractable algebras are the     listed in Table    of Appendix A

## 4.1  The Cg -Complete Subalgebra M 72

When proving that the class R 5 8 is tractable  Jonsson and Drakengren oserved that any subalgebra of RCC   containing only relations including EQ is tractable  This result applies also to MC with respect to the relation CG and also to the relations CNO
{CGPP, CGPP-1} {CG, CNO} {CG, CGPP, CGPP-1}
The only relevant cases are CG  CNO and {CGPP, CGPP- 1 }  since the other two cases are included in two of the former three  An algebra formed by relations which all contain CG and by the relation   is tractable because we can obtain an inconsistency iff we explicitly have an edge labelled by    in the network  Deciding the consistency is therefore an O n² problem