In supervised learning the links are explicitly given as the probability is smoothened and thus all links would have a non zero probability of occurrence.
Boolean satisfyability is known as empty complete-- because given a set of boolean constraints its hard to get variable which satisfies these conditions.
In general 1 sat is east to solve, 2 sat is polynomial and 3 sat is empty complete.
A major issue with data integration is that many different people make different database schemas to store the same data(ie across web, businesses etc..). Sometimes the schemas map one to one to each other, but more often they map in a non-trivial manner and may not even store all the same information.