Datalog extension for nested relations

The nested relational model allows relations that are not in first normal form. This paper gives an extension of Datalog rules for nested relations. In our approach, nested Datalog is a natural extension of Datalog introduced for the relational data model. A nested Datalog program has a hierarchical structure of rules and subprograms to manipulate relation values of nested relations. We introduce a new category of predicate symbols, the variable predicate symbols to refer to tuples of subrelations. The notion of soundness, safety and consistency is defined to avoid undesirable nested Datalog programs. The evaluation of nested Datalog is given in terms of the nested relational algebra. Finally, we relate the expressive power of nonrecursive nested Datalog to the power of nested relational algebra and safe nested tuple relational calculus.