INTERSECTION GRAPHS OF K-ACYCLIC FAMILIES OF SUBTREES AND RELATIONAL DATABASE QUERY-PROCESSING

A graph G is called k-neighborhood chordal if for every vertex set A, such that \A\ less than or equal to k and G(A) connected, the graph U- v epsilon A G(Gamma upsilon) is chordal. A family of subtrees of a gra ph is called k-acyclic if the union of any k subtrees is acyclic. A gr aph is 1-neighborhood chordal iff it is an intersection graph of a Hel ly 2-acyclic family of subtrees (Gavril, 1987). In the present paper w e prove that a graph is an intersection graph of a k-acyclic, k greate r than or equal to 3, family of subtrees of a graph iff it is (k-1)-ne ighborhood chordal iff it is 1-neighborhood chordal and when k greater than or equal to 4 it contains no holes with k or less vertices. We p resent a polynomial time algorithm to find the biggest such k and to c onstruct the corresponding family of subtrees. As an application, we u se (k-1)-neighborhood chordal graphs for a relaxation of the acyclicit y requirement on versions of universal relations in relational databas es, which still allows queries with at most k-1 attributes to be answe red by an efficient SPJ program. (C) 1998 Elsevier Science B.V.