Title: ROCKER: A Refinement Operator for Key Discovery,
Abstract: The Linked Data principles provide a decentral approach for publishing
structured data in the RDF format on the Web. In contrast to structured data
published in relational databases where a key is often provided explicitly,
finding a set of properties that allows identifying a resource uniquely is a
non-trivial task. Still, finding keys is of central importance for manifold
applications such as resource deduplication, link discovery, logical data
compression and data integration. In this paper, we address this research gap
by specifying a refinement operator, dubbed ROCKER, which we prove to be
finite, proper and non-redundant. We combine the theoretical characteristics of
this operator with two monotonicities of keys to obtain a time-efficient
approach for detecting keys, i.e., sets of properties that describe resources
uniquely. We then utilize a hash index to compute the discriminability score
efficiently. Therewith, we ensure that our approach can scale to very large
knowledge bases. Results show that ROCKER yields more accurate results, has a
comparable runtime, and consumes less memory w.r.t. existing state-of-the-art
techniques.