On Expressing Stratified Datalog

We consider the broad class of stratified Datalog queries (which includes both linear and non-linear queries) and propose an extended closure operator that expresses such queries when added to the relational algebra. We show that there exists a canonical form for stratified Datalog queries, and that suitable hypergraphs can be used to express them. We anticipate the use of such hypergraphs in identifying special classes of stratified Datalog queries and in devising efficient algorithms for these classes, and outline the use of the visual representation of hypergraphs in a user interface for querying databases. 1 Introduction The study of query languages that are more expressive than first order query languages has been the subject of much research, since the early results in [AU79] concerning the inability of first order queries to express the transitive closure of a binary relation. An important part of this work has been developed in the realm of database logic programs, usually als..