Evaluation of RDF queries via equivalence

Performance and scalability are two issues that are becoming increasingly pressing as the resource description framework (RDF) datamodel is applied to real-world applications. Because neither vertical nor flat structures of RDF storage can handle frequent schema updates and meanwhile avoid possible long-chain joins, there is no clear winner between the two typical structures. In this paper, we propose an alternative open user schema. The open user schema consists of flat tables automatically extracted from RDF query streams. A query is divided into two parts and conquered on the flat tables in the open user schema and on the vertical table stored in a backend storage. At the core of this divide and conquer architecture with open user schema, an efficient isomorphic decision algorithm is introduced to guide a query to related flat tables in the open user schema. Our proposal in essence departs from existing methods in that it can accommodate schema updates without possible long-chain joins. We implement our approach and provide empirical evaluations to demonstrate both the efficiency and effectiveness of our approach in evaluating complex RDF queries.