Partitioning OWL Knowledge Bases for Parallel Reasoning

Partitioning OWL Knowledge Bases for Parallel Reasoning

Abstract—The ability to reason over large scale data andreturn responsive query results is widely seen as a critical stepto achieving the Semantic Web vision. We describe an approachfor partitioning OWL Lite datasets and then propose a strategyfor parallel reasoning about concept instances and role instanceson each partition. The partitions are designed such that eachcan be reasoned on independently to find answers to each querysubgoal, and when the results are unioned together, a complete setof results are found for that subgoal. Our partitioning approachhas a polynomial worst case time complexity in the size of theknowledge base. In our current implementation, we partitionsemantic web datasets and execute reasoning tasks on partitioneddata in parallel on independent machines. We implement amaster-slave architecture that distributes a given query to theslave processes on different machines. All slaves run in parallel,each performing sound and complete reasoning to execute eachsubgoal of its query on its own set of partitions. As a final step,master joins the results computed by the slaves. We study theimpact of our parallel reasoning approach on query performanceand show some promising results on LUBM data.