{"action":"created","issue":{"url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/268","labels_url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/268/labels{/name}","comments_url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/268/comments","events_url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/268/events","html_url":"https://github.com/AmpersandTarski/ampersand/issues/268","id":125809627,"number":268,"title":"Possible optimisation in SQL-code","user":{"login":"stefjoosten","id":275768,"avatar_url":"https://avatars.githubusercontent.com/u/275768?v=3","gravatar_id":"","url":"https://api.github.com/users/stefjoosten","html_url":"https://github.com/stefjoosten","followers_url":"https://api.github.com/users/stefjoosten/followers","following_url":"https://api.github.com/users/stefjoosten/following{/other_user}","gists_url":"https://api.github.com/users/stefjoosten/gists{/gist_id}","starred_url":"https://api.github.com/users/stefjoosten/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefjoosten/subscriptions","organizations_url":"https://api.github.com/users/stefjoosten/orgs","repos_url":"https://api.github.com/users/stefjoosten/repos","events_url":"https://api.github.com/users/stefjoosten/events{/privacy}","received_events_url":"https://api.github.com/users/stefjoosten/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/AmpersandTarski/ampersand/labels/component:global","name":"component:global","color":"fef2c0"},{"url":"https://api.github.com/repos/AmpersandTarski/ampersand/labels/priority:low","name":"priority:low","color":"207de5"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2016-01-10T09:18:41Z","updated_at":"2016-01-11T06:44:14Z","closed_at":null,"body":"# Observation\r\nCurrently, the code generator generates SQL-code for Epsilon-expressions, as in:\r\n\r\n    select\r\n    distinct\r\n           t1.src as src, t1.tgt as tgt\r\n    from (/* case: (ECps es), with two or more elements in es.I{-Eps-}[Statement];template;I{-Eps-}[Template];head */\r\n          select\r\n          distinct\r\n                 fence0.src as src, fence3.tgt as tgt\r\n          from (/* epsilon Statement [Sequence*Statement] */\r\n                select\r\n                distinct\r\n                       \"Statement\" as src, \"Statement\" as tgt\r\n                from \"Sequence\"\r\n                where \"Statement\" IS NOT NULL)\r\n               as fence0,\r\n               (select\r\n                distinct\r\n                       \"Statement\" as src, \"tgt_template\" as tgt\r\n                from \"Sequence\"\r\n                where \"Statement\" IS NOT NULL AND \"tgt_template\" IS NOT NULL)\r\n               as fence1,\r\n               (/* epsilon Template [Template*Sequence] */\r\n                select\r\n                distinct\r\n                       \"Template\" as src, \"Template\" as tgt\r\n                from \"Sequence\"\r\n                where \"Template\" IS NOT NULL)\r\n               as fence2,\r\n               (select\r\n                distinct\r\n                       \"Sequence\" as src, \"tgt_head\" as tgt\r\n                from \"Sequence\"\r\n                where \"Sequence\" IS NOT NULL AND \"tgt_head\" IS NOT NULL)\r\n               as fence3\r\n          where fence0.tgt = fence1.src AND fence1.tgt = fence2.src AND fence2.tgt = fence3.src)\r\n         as t1\r\n         left\r\n         join (/* case: (ECps es), with two or more elements in es.head;I{-Eps-}[Prefix];bind;I{-Eps-}[Variable] */\r\n               select\r\n               distinct\r\n                      fence0.src as src, fence3.tgt as tgt\r\n               from (select\r\n                     distinct\r\n                            \"Sequence\" as src, \"tgt_head\" as tgt\r\n                     from \"Sequence\"\r\n                     where \"Sequence\" IS NOT NULL AND \"tgt_head\" IS NOT NULL)\r\n                    as fence0,\r\n                    (/* epsilon Prefix [Item*Prefix] */\r\n                     select\r\n                     distinct\r\n                            \"Prefix\" as src, \"Prefix\" as tgt\r\n                     from \"Item\"\r\n                     where \"Prefix\" IS NOT NULL)\r\n                    as fence1,\r\n                    (select\r\n                     distinct\r\n                            \"Prefix\" as src, \"tgt_bind\" as tgt\r\n                     from \"Item\"\r\n                     where \"Prefix\" IS NOT NULL AND \"tgt_bind\" IS NOT NULL)\r\n                    as fence2,\r\n                    (/* epsilon Variable [Variable*Item] */\r\n                     select\r\n                     distinct\r\n                            \"Variable\" as src, \"Variable\" as tgt\r\n                     from \"Item\"\r\n                     where \"Variable\" IS NOT NULL)\r\n                    as fence3\r\n               where fence0.tgt = fence1.src AND fence1.tgt = fence2.src AND fence2.tgt = fence3.src)\r\n              as t2\r\n         on t1.src = t2.src AND t1.tgt = t2.tgt\r\n    where t2.src IS NULL OR t2.tgt IS NULL\r\n\r\nThe code for epsilons can be avoided, which leads to almost half the size of this query:\r\n\r\n    select\r\n    distinct\r\n           t1.src as src, t1.tgt as tgt\r\n    from (/* case: (ECps es), with two or more elements in es.I{-Eps-}[Statement];template;I{-Eps-}[Template];head */\r\n          select\r\n          distinct\r\n                 fence1.src as src, fence3.tgt as tgt\r\n          from (select\r\n                distinct\r\n                       Statement as src, tgt_template as tgt\r\n                from Sequence\r\n                where Statement IS NOT NULL AND tgt_template IS NOT NULL)\r\n               as fence1,\r\n               (select\r\n                distinct\r\n                       Sequence as src, tgt_head as tgt\r\n                from Sequence\r\n                where Sequence IS NOT NULL AND tgt_head IS NOT NULL)\r\n               as fence3\r\n          where fence1.tgt = fence3.src)\r\n         as t1\r\n         left\r\n         join (/* case: (ECps es), with two or more elements in es.head;I{-Eps-}[Prefix];bind;I{-Eps-}[Variable] */\r\n               select\r\n               distinct\r\n                      fence0.src as src, fence2.tgt as tgt\r\n               from (select\r\n                     distinct\r\n                            Sequence as src, tgt_head as tgt\r\n                     from Sequence\r\n                     where Sequence IS NOT NULL AND tgt_head IS NOT NULL)\r\n                    as fence0,\r\n                    (select\r\n                     distinct\r\n                            Prefix as src, tgt_bind as tgt\r\n                     from Item\r\n                     where Prefix IS NOT NULL AND tgt_bind IS NOT NULL)\r\n                    as fence2\r\n               where fence0.tgt = fence2.src)\r\n              as t2\r\n         on t1.src = t2.src AND t1.tgt = t2.tgt\r\n    where t2.src IS NULL OR t2.tgt IS NULL\r\n\r\n# Analysis\r\nEpsilon expressions are introduced for type checking. They satisfy:\r\n\r\n    epsilon X [Y*Z] = I[X]\r\n\r\nThe typechecker introduces `epsilon X [Y*Z]` only if `X ISA Y` and `X ISA Z`.\r\nThe typechecker ensures that every expression in the F-structure is type correct, expecially that `r[A*B];s[C*D]` implies `B=C`. Removing epsilons means that this guarantee can no longer be given. However, without epsilons, the type checker still guarantees that expressions in the F-structure satisfy `r[A*B];s[C*D]` implies there is an `X` such that `X ISA B` and `X ISA C`. This is obvious if you consider that every `r[A*B];s[C*D]` comes (at worst) from `r[A*B];epsilon X [B*C];s[C*D]`.\r\n\r\nA consequence of this is that the SQL-generator can ignore epsilons, because semantically they are equivalent to `I[X]` and `I[X];r = r`."},"comment":{"url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/comments/170445175","html_url":"https://github.com/AmpersandTarski/ampersand/issues/268#issuecomment-170445175","issue_url":"https://api.github.com/repos/AmpersandTarski/ampersand/issues/268","id":170445175,"user":{"login":"stefjoosten","id":275768,"avatar_url":"https://avatars.githubusercontent.com/u/275768?v=3","gravatar_id":"","url":"https://api.github.com/users/stefjoosten","html_url":"https://github.com/stefjoosten","followers_url":"https://api.github.com/users/stefjoosten/followers","following_url":"https://api.github.com/users/stefjoosten/following{/other_user}","gists_url":"https://api.github.com/users/stefjoosten/gists{/gist_id}","starred_url":"https://api.github.com/users/stefjoosten/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stefjoosten/subscriptions","organizations_url":"https://api.github.com/users/stefjoosten/orgs","repos_url":"https://api.github.com/users/stefjoosten/repos","events_url":"https://api.github.com/users/stefjoosten/events{/privacy}","received_events_url":"https://api.github.com/users/stefjoosten/received_events","type":"User","site_admin":false},"created_at":"2016-01-11T06:44:14Z","updated_at":"2016-01-11T06:44:14Z","body":"@WolframKahl Wolfram, do you mind if I clean up the part of our discussion about `B*C` versus `B=C`? In that way, this ticket becomes more understandable for future readers, who might find this interesting."}}