  Although RDF graphs have schema information associated with them, in practice
it is very common to find cases in which data do not fully conform to their
schema. A prominent example of this is DBpedia, which is RDF data extracted
from Wikipedia, a publicly editable source of information. In such situations,
it becomes interesting to study the structural properties of the actual data,
because the schema gives an incomplete description of the organization of a
dataset. In this paper we have approached the study of the structuredness of an
RDF graph in a principled way: we propose a framework for specifying
structuredness functions, which gauge the degree to which an RDF graph conforms
to a schema. In particular, we first define a formal language for specifying
structuredness functions with expressions we call rules. This language allows a
user or a database administrator to state a rule to which an RDF graph may
fully or partially conform. Then we consider the issue of discovering a
refinement of a sort (type) by partitioning the dataset into subsets whose
structuredness is over a specified threshold. In particular, we prove that the
natural decision problem associated to this refinement problem is NP-complete,
and we provide a natural translation of this problem into Integer Linear
Programming (ILP). Finally, we test this ILP solution with two real world
datasets, DBpedia Persons and WordNet Nouns, and 4 different and intuitive
rules, which gauge the structuredness in different ways. The rules give
meaningful refinements of the datasets, showing that our language can be a
powerful tool for understanding the structure of RDF data.
