On existential interpretability of structures

摘要

We introduce and study the notion of 9–interpretabilityof constructive algebraic structures. It is shown that any finite partiallyordered set is embeddable into the semilattice this interpretability generates;we also prove the existence of universal computable structures.As an application of this concept, we consider the transformations ofabstract databases and their queries in case when one data structure is9–interpretable in another one.