This special issue contains four selected papers presented at the International Conference on Database Theory (ICDT 2010), which was held jointly with the International Conference on Extending Database Technology (EDBT 2010) on 22-26 March 2010 in Lausanne, Switzerland.

ICDT is one of the major forums for the presentation of research on all aspects of theoretical aspects within databases.

4 of the 20 papers presented at the conference were invited to submit an extended version to this special issue. The paper "Composition with Target Constraints" by Marcelo Arenas, Ronald Fagin and Alan Nash was also selected for the ICDT Best Paper Award.

The papers "Answering Non-Monotonic Queries in Relational Data Exchange" by Andr Hernich, and "Forward-XPath and extended register automata on data-trees" by Diego Figueira were also selected for the ICDT Best Student Papers Award.

The submissions for the special issue underwent a new and thorough reviewing and revision process, in accordance with the usual standards of LMCS. We thank the authors and the reviewers for all their hard work producing the contents of this issue.