The so-called Schengen compensatory measures such as the Schengen Information System (SIS) or the European Dactylographic System (Eurodac) have been the centre of much attention. However, the research on these security measures has focused almost solely on their effect on liberty, human rights and the like. Not much attention has been given to the actual effectiveness of the security remedies taken in the EU to compensate for the abolition of border controls, despite effectiveness being an obvious source of legitimacy in the realm of security. This article takes a first step in the direction of correcting this neglect and develops the foundations for an analytical framework focusing on effectiveness and legitimacy. The framework is illustrated through a minor analysis of the legal and institutional setup of SIS and Eurodac as examples pointing to sources of ineffectiveness in the very setup of the databases.