A short survey on the state of the art in matching and unification problems

Abstract
1. Motivations There is a wide variety of areas where matching and unification problems arise: (1.1) Databases The user of a (relational) database [22] may logically AND the properties she wants to retrieve or else she may be interested in the NATURAL JOIN [17] of two stored relations. In neither case, she would appreciate if she constantly had to take into account that AND is an associative and commutative operation, or that NATURAL JOIN obeys an associative axiom, which may distribute over some other operation [68].