This research examines certain definability and decidability problems for finite models, motivated by the theory of relational databases. Among them are problems of existence of recursive characterizations for specific classes of queries (formulas), such as, safe, monotone, or distributive queries. In addition, this project investigates the expressive power of different logical languages for finite models, particularly in the absence of linear order. Among the targeted languages are those of first order logic, different fixpoint logics, implicit definability, and of fragments of infinitary logics. The main goal here is to expand numerous definability results for ordered models to wider classes of models, for example, finitely axiomatizable classes of rigid models.
