On Expressing Stratified Datalog.
Tiziana Catarci, Isabel F. Cruz · 1994
1 Introduction Tiziana Catarci Isabel F. Cruz On Expressing Stratified Datalog [email protected] [email protected] ongate x; y; z in x ; in y ; gate x; y; z : ongate x; y; z ongate a; b; x ; gate x; y; z ; ongate c; d; y : Dipartimento di Informatica e Sistemistica Universit`a di Roma "La Sapienza" Via Salaria 113, I-00198 Roma, Italy Department of Computer Science Brown University Providence, RI 02912-1910, USA Research partially supported by EEC under the Esprit Project 6398 VENUS. Partial support given by ONR Contract N00014-91-J-4052, ARPA Order 8225. These two classes are however incomparable (see for example [Kan90]). 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. ...