Relational Strategies for Processing Universally Quantified Queries to Large Data Bases

Abstract

Relational algebraic strategies are described for processing universally quantified queries. First, a new algorithm is developed to evaluate universally quantified conditional queries of the form [X: (y) W1 (x, y) - W2 (x, y)]. It decomposes the problems into two subproblems using set intersection, summary and Join operations within the frame work of relational algebra. Second, the partial multi-valued-dependency decomposition of a relation is introduced as an efficient representation schema to express a set of uniform intensional data of the form (x/t) P(x). The original relation is defined in terms of the decomposed relations as a relational algebraic equation. A relational algebraic expression corresponding to a query to the original relation is transformed to the one in terms of the decomposed relations using the above equation. Furthermore, the transformed algebraic expression is converted to a simple associative search expression to one of the decomposed relations by applying the rule-based formula manipulation or symbolic evaluation method.