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 quantit'ied conditional queries of the form [Y: (VYJW1(1,?>~ 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 uni f orm intensional data of the form (Vf;1)p(t). 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.