Performance analysis of algorithms to reason about

Abstract. Keys are fundamental for database management, indepen-dently of the particular data model used. In particular, several notions of XML keys have been proposed over the last decade, and their expres-siveness and computational properties have been analyzed in theory. In practice, however, expressive notions of XML keys with good reasoning capabilities have been widely ignored. In this paper we present an efficient implementation of an algorithm that decides the implication problem for a tractable and expressive class of XML keys. We also evaluate the per-formance of the proposed algorithm, demonstrating that reasoning about expressive notions of XML keys can be done efficiently in practice and scales well. Our work indicates that XML keys as those studied here have great potential for diverse areas such as schema design, query optimiza-tion, storage and updates, data exchange and integration. To exemplify this potential, we use the algorithm to calculate non-redundant covers for sets of XML keys, and show that these covers can significantly re-duce the number of XML keys against which XML documents must be validated. This can result in enormous time savings.