Towards well-behaved schema evolution

We study the problem of schema evolution in the RDF data model. RDF and the RDFS schema language are W3C standards for exibly modeling and sharing data on the web. Although schema evolution has been intensively studied in the database and knowledge-representation communities, only recently has progress been made on the study of RDFS schema evolution. Indeed, the exible nature of RDF poses novel challenges. In particular, since the data model does not strictly distinguish data from metadata, schema evolution is intimately related to data updates. A major issue encountered during RDFS database updates is a certain type of "nondeterminism" exhibited during schema evolution. In current solutions, such nondeterminism is handled by extra-logical rules or heuristics. Is it possible to characterize the class of RDFS updates which are well-behaved, that is, with a well-defined semantics avoiding ad-hoc solutions? In this paper, we present our first steps in a project to formally reason about such issues in RDF schema evolution. Specifically, we introduce an effective notion of determinism in RDF schema evolution, formally characterize a large class of well-behaved updates on RDFS graphs with respect to this definition, and show that computing such updates is tractable via a polynomial-time algorithm