A call to regularity
Moshe Y. Vardi · 2003
From the mid 1980s to the mid 1990s, with the active involvement of Paris C. Kanellakis, a major theme in database theory was the study of Datalog, the language of logic programs without function symbols. Unfortunately, most decision problems involving Datalog turned out to be undecidable. Furthermore, well-behaved fragments of Datalog turned out to be rather restrictive and unnatural. Surprisingly, a natural and quite general fragment of Datalog did emerge in the mid 1990s, in the context of semistructured data. This fragment is the class of regular queries, whose basic element is that of regular path queries. In this talk I describe the class of regular queries and its well-behavedness in the context of view-based query processing.