  Matching Dependencies (MDs) are a relatively recent proposal for declarative
entity resolution. They are rules that specify, on the basis of similarities
satisfied by values in a database, what values should be considered duplicates,
and have to be matched. On the basis of a chase-like procedure for MD
enforcement, we can obtain clean (duplicate-free) instances; actually possibly
several of them. The resolved answers to queries are those that are invariant
under the resulting class of resolved instances. Previous work identified
certain classes of queries and sets of MDs for which resolved query answering
is tractable. Special emphasis was placed on cyclic sets of MDs. In this work
we further investigate the complexity of this problem, identifying intractable
cases, and exploring the frontier between tractability and intractability. We
concentrate mostly on acyclic sets of MDs. For a special case we obtain a
dichotomy result relative to NP-hardness.
