Transitive Closure

[stefjoosten]

Problem

The postfix operators * and + (the Kleene closures) don't work yet in Ampersand, even though the need for them occurs frequently when specifying information systems in Ampersand. We have found ways around it, which work only if the transitive closure grows monotonically in time. For a proper solution, we need to implement the transitive closure inside the language, such that it works for transitive closures that not only grow but can shrink as well.

Proposal

I think this is worth a graduate assignment. We already have some papers to attack this problem

1. Dong, G., Libkin, L., Su, J., & Wong, L. (1999). Maintaining Transitive Closure of Graphs in SQL. International Journal of Information Technology, 51 (1), 46-78.

Goal

The goal is to implement the Kleene operators in the Ampersand language, so the language also comprises Kleene algebras.

Impediments

There may be obstacles of formal nature that stand in the way of practical implementation. In such cases, partial implementation will suffice as long as it enhances the language, albeit partially.