IITDBGroup / gprom

GProM is a middleware that adds support for provenance to database backends.
http://www.cs.iit.edu/%7edbgroup/research/gprom.php
Apache License 2.0
8 stars 5 forks source link

treeify does not create copies of subtrees when a binary operator references the same child twice #71

Closed lordpretzel closed 11 months ago

lordpretzel commented 3 years ago

This creates problems with provenance rewrites, because treeify will use one copy twice and then during rewrite the same subtree will be rewritten twice.

PROVENANCE OF (WITH x AS (SELECT a FROM r) SELECT g.a FROM x g, x h WHERE g.a < h.a);

is turned into

INFO(translator_oracle.c:145) result of translation overview is

ProvenanceComputation (a: DT_INT, prov_r_a: DT_INT, prov_r_b: DT_INT, prov_r_1_a: DT_INT, prov_r_1_b: DT_INT) [0x7fc7f1509b4e]()
  Projection [a ] (a: DT_INT) [0x7fc7f150ac5e](0x7fc7f1509b4e)
    Selection [(a < a1)] (a: DT_INT, a1: DT_INT) [0x7fc7f150aa01](0x7fc7f150ac5e)
      CrossProduct [] (a: DT_INT, a1: DT_INT) [0x7fc7f150a7e8](0x7fc7f150aa01)
        @0
        @0

-----------------------
@0
Projection [a ] (a: DT_INT) [0x7fc7f1509e7d](0x7fc7f150a7e8, 0x7fc7f150a7e8)
  TableAccess [r] (a: DT_INT, b: DT_INT) [0x7fc7f1509c9b](0x7fc7f1509e7d)

and then treefied into

ProvenanceComputation (a: DT_INT, prov_r_a: DT_INT, prov_r_b: DT_INT, prov_r_1_a: DT_INT, prov_r_1_b: DT_INT) [0x7fc7f13083dc]()
  Projection [a ] (a: DT_INT) [0x7fc7f13087b1](0x7fc7f13083dc)
    Selection [(a < a1)] (a: DT_INT, a1: DT_INT) [0x7fc7f1308bbf](0x7fc7f13087b1)
      CrossProduct [] (a: DT_INT, a1: DT_INT) [0x7fc7f1308cbb](0x7fc7f1308bbf)
        Projection [a ] (a: DT_INT) [0x7fc7f130b581](0x7fc7f1308cbb)
          TableAccess [r] (a: DT_INT, b: DT_INT) [0x7fc7f130b89e](0x7fc7f130b581)
        Projection [a ] (a: DT_INT) [0x7fc7f130b581](0x7fc7f1308cbb)
          TableAccess [r] (a: DT_INT, b: DT_INT) [0x7fc7f130b89e](0x7fc7f130b581)

Note that the subtrees rooted at 0x7fc7f130b581 are the same