An algorithmic approach for handling cyclic and noncyclic linear recursive queries in horn databases
Ching-Shyan Wu · 1988
A unifying method to efficiently process the linear recursive queries in both acyclic and cyclic databases is presented. Our approach is based on the cycle merging and graph traversing technique. The cycle merging makes the level information manageable. The data relevant to the query constant are split into several connected graphs. Each graph has a start vertex, called an origin, and is separately processed. Each vertex in a graph is associated with a set called self recurrence sequence (SRS) to represent the possible occurrences of levels from the vertex to itself. The set obtained by merging the SRSs of vertices on a path from the origin to a vertex v is called a path recurrence sequence (PRS). The union of the PRSs is the recurrence sequence (RS) of v and represents all possible levels of v w.r.t. the origin. The answers can be determined by checking the emptiness of intersection of pairs of RSs: one for a bridge vertex b in the LHS relation and the other for a vertex c in the RHS relation. If non-empty then c is an answer otherwise not. Another way to decide answers is by directly enumerating the RSs of b during the traversing of graphs in the RHS. This eliminates the need to compute RSs in the RHS graphs. The intersection method performs in time bound of O(n e) and the enumeration method performs almost in O(e), where e is the total number of accessed tuples in the both side relations and n is the total number of vertices. SRSs can be computed before the query and the maintenance of SRSs is not always required for each data change unless the change breaks/produces some cycle affecting the SRS of some vertex. Another advantage is that our method can be implemented for parallel execution.