Maximal object+: An acyclic semantic structure on the universal relation model

摘要

The universal relation model allows us to find the results on a virtual relation that joins all the relations in a relational database if the user specifies only selection and projection conditions. It automatically finds actual relations in which the selection and projection conditions are performed and possible join paths among the relations using the database schema. When there are cycles in the database schema graph, however, the universal relation model may lose some results since it adds an unintentional condition to the interpretation of a query. Here, the unintentional condition is an equality condition that intersects multiple query interpretations by different join paths, and thus, it returns only part of the results that the user intends. This paper proposes a new semantic structure, maximal object+, that completely removes cycles in a universal relation. A maximal object+ is a largest acyclic connected component in the database schema graph where the entire set of relations in the component has the lossless join property. Here, the important point is that a maximal object+ allows only the lossless join property indicated by functional dependencies excluding the lossless join property indicated by only multivalued dependencies. To show the advantage of a maximal object+, we compare the effectiveness of the query processing method based on maximal object+ with that of the existing query processing method based on the maximal object by performing experiments on the synthetic and real datasets. As a result, we show that our method significantly outperforms the one based on the maximal object in terms of mean recall when a cycle exists in a maximal object while maintaining comparable efficiency. Specifically, our method improves the mean recall by up to 8.15 times for the dataset whose schema involves cycles.