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.

[stefjoosten]

@WolframKahl Do you have any comments or suggestions on this issue? Warnings maybe?

I can imagine that recursive rules can solve the problem partially. However, in interfaces, we have terms. So there we cannot avoid the Kleene operators if we want to use them.

[hanjoosten]

I think a graduate student could do this in a day, after spending the time on to learn about the specifics on Ampersand and its implementation of the generation of SQL, in particular SQL.hs Also, this issue is a double of https://github.com/AmpersandTarski/Ampersand/issues/137