Skip to content. | Skip to navigation

Informatik 5
Information Systems
Prof. Dr. M. Jarke
Sections
Personal tools
You are here: Home Staff M.Eng. Rihan Hai Correctness check with existing literatures Input plain SO tgds and results

Input plain SO tgds and results

In this page we provide the detailed results of 14 plain SO tgds from existing literature, including the input plain SO tgds, their source literature and our output results. The examples from the paper are also added. The single mode of our mapping generators (nested tgd generator, plain SO tgd generator) is used, which allows the user to customize an input plain SO tgd or nested tgd. In addition, we show another 13 examples. They are enumerated examples for illustrating certain technical details most omitted in the paper, e.g., consistency check, insert a new middle level part (similar to inserting a root), which were relatively simple and not the main focus of the paper.

This page only contains results of our rewriting algorithm, for examples of applying nested tgd generator, see Apply the nested tgd generator

For a better understanding we unify the naming of variables/relations in the examples: 
*x_i represents universal variables; 
?y_i represents existential variables; 
S_i represents source relations; 
T_i represents target relations; 
?f_i represents existentially quantified function symbols.
  •  Example input plain SO tgds from existing literatures. 
1.  Input plain SO tgd:
?f1(),?f2() *x1,*x2,*x3 
[S1(x1) --> T1(f1(x1))] ^ 
[S1(x1)^S2(x1,x2) --> T2(f1(x1),f2(x1,x2))] ^ 
[S1(x1)^S2(x1,x2)^S3(x1,x2,x3) --> T3(f1(x1),f2(x1,x2),x3)]
Source: Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability Example in Sec3.2  

 

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x1 S1(x1) --> ?y1 [T1(y1) ^

*x2 S2(x1,x2) --> ?y2 [T2(y1,y2) ^

*x3 S3(x1,x2,x3) --> [T3(y1,y2,x3)]]  ]

 

 2.  Input plain SO tgd:

?f1(x1),?f2(x1,x3,x4) *x1,*x2,*x3,*x4 

[S1(x1) --> ] ^ 

[S1(x1)^S2(x2) --> T2(f1(x1),x2)] ^

[S1(x1)^S3(x1,x3) --> T3(f1(x1),x3)] ^ 

[S1(x1)^S3(x1,x3)^S4(x3,x4) --> T4(f2(x1,x3,x4),x4)]

Source:Nested dependencies: structure and reasoning star example on p179

Original nested tgd:

*x1 S1(x1) --> ?y1 ^ 

*x2 S2(x2) --> [T2(y1,x2)] ^ 

*x3 S3(x1,x3) --> [T3(y1,x3) ^ 

*x4 S4(x3,x4) --> ?y2 [T4(y2,x4)]]

Original  Skolemized nested tgd

?f1(x1),?f2(x1,x3,x4) 

*x1 S1(x1) --> 

*x2 S2(x2) --> [T2(f1(x1),x2) 

*x3 S3(x1,x3) --> [T3(f1(x1),x3) 

*x4 S4(x3,x4) --> [T4(f2(x1,x3,x4),x4) ] ] ]

 

Output:

*x1 S1(x1) --> ?y1 ^

*x2 S2(x2) --> [T2(y1,x2)] ^

*x3 S3(x1,x3) --> [T3(y1,x3) ^

*x4 S4(x3,x4) --> ?y2 [T4(y2,x4)]]  

 

3.  Input plain SO TGD:

?f1() *x1,*x2 [S1(x2)^S2(x1,x2) --> T1(x1,f1(x2))]

Source: Function Symbols in Tuple-Generating Dependencies: Expressive Power and Computability

 Example on page 66

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x2 S1(x2) --> ?y1 ^

*x1 S2(x1,x2) --> [T1(x1,y1)]  

 

4.  Input plain SO TGD:

?f1(),?f2() *x1,*x2,*x3 [S1(x1,x2)^S2(x3) --> T1(f1(x3,x1,x2),f2(x3),x1)]

Source: Nested dependencies: structure and reasoning Example 4.15

  

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x3 S2(x3) --> ?y2 ^

*x1,*x2 S1(x1,x2) --> ?y1 [T1(y1,y2,x1)]  

 

 

5.  Input plain SO tgd: 

?f1() *x1,*x2 [S1(x1,x2) --> T1(f1(x1),f1(x2))]

Source: Nested dependencies: structure and reasoning Example on Page 176 (proof on P184)

Output:

Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: 

Not consistent, same skolem function with different arguments

 

6.  Input plain SO tgd:  

?f1(),?f2() *x1,*x2,*x3 [S1(x1,x2) ^ S2(x3) --> T1(f1(x3,x1),f1(x3,x2),f2(x3))]

Source: Nested dependencies: structure and reasoning Example 4.14 on P184

 

Output:

Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: 

Not consistent, same skolem function with different arguments

 

 7.  Input PSO TGD:

?f1() *x1,*x2  

[S1(x1,x2) --> T1(x1,f1(x1,x2))] ^

[S1(x1,x2) --> T2(f1(x1,x2),x2)] ^

[S2(x1,x2) --> T1(x1,f1(x1,x2))]  

 Source: The language of plain SO-tgds: Composition, inversion and structural properties Example on page 767

 

Output:

The rewrite process is successful.

Original plain SO tgd has 1 solution(s) available.

-----------------------------------------------------------------

Solution:1

No.1:

Current solution has 2 nested tgds.

Nested tgd No.1:

*x1,*x2 S1(x1,x2) --> ?y1 [T1(x1,y1)^T2(y1,x2)   ]

Nested tgd No.2:

*x1,*x2 S2(x1,x2) --> [T1(x1,y1)   ]

 

 

8.  Input PSO TGD: 

?f1() *x1,*x2  [S1(x1,x2) --> T1(x1,x2,f1(x1,x2))]  

Source: The iBench integration metadata generator Primitive Add in Fig.4 on page 112

 Output: 

The rewrite process is successful.

The equivalent nested tgds is:

*x1,*x2 S1(x1,x2) --> ?y1 [T1(x1,x2,y1)   ] 

 

9.  Input PSO TGD: 

?f1() *x1,*x2  [S1(x1,x2) --> T1(f1(x1,x2),x1)^T2(f1(x1,x2),x2)]  

Source: The iBench integration metadata generator Primitive VH in Fig.4 on page 112

 Output: 

The rewrite process is successful.

The equivalent nested tgds is:

*x1,*x2 S1(x1,x2) --> ?y1 [T1(y1,x1)^T2(y1,x2)   ]

 

 

 

 

10.  Input PSO TGD:

?f1() *x1,*x2,*x3 [S1(x1,x2,x3) --> T1(f1(x1,x2),x3)]

 Source: Value invention in data exchange EX. 1 on page 159

 

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x1,*x2 ?y1 

*x3 S1(x1,x2,x3) --> [T1(y1,x3)   ]

 

11.  Input PSO TGD:

?f1(),?f2() *x1,*x2 [S1(x1,x2) --> T1(f1(x1),f2(x1,x2),x2)]

Source: Value invention in data exchange Example 3.1 on page 161

 

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x1 ?y1 

*x2 ?y2 

S1(x1,x2) --> [T1(y1,y2,x2)   ]

 

 

 

 

12.  Input PSO TGD:

?f1(),?f2() *x1,*x2,*x3 [S1(x1,x2,x3) --> T1(x1,f1(x1),f2(x1,x2))]

 Source: Value invention in data exchange EX. 2 on page 159

 

Output:

The rewrite process is successful.

The equivalent nested tgds is:

*x1 ?y1 

*x2 ?y2 

*x3 S1(x1,x2,x3) --> [T1(x1,y1,y2)   ]

 

13.  Input PSO TGD:

?f1(),?f2() *x1,*x2 [S1(x1,x2) --> T1(x1,f1(x1),f2(x2))]

Source: Value invention in data exchange EX. 3 on page 159

 

Output:

Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: 

Cannot rewrite to a FO sentence, the Skolem functions not linear

 

Note for this and below example  are not rewritable if we don't consider function dependency.

 

14.  Input PSO TGD:

?f1(),?f2() *x1,*x2,*x3,*x4 [S1(x1,x2,x3,x4) --> T1(x2,f1(x1,x2,x3),f2(x3,x4))]

Source: Value invention in data exchange EX. 4 on page 159

 

Output:

Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: 

Cannot rewrite to a FO sentence, the Skolem functions not linear
  
 
******************************************************************
******************************************************************
  • Examples used in the paper 
 15. Input plain SO tgd:
?f1(),?f2(),?f3(),?f4() *x1 
[S1(x1) --> T1(x1,f1(x1))] ^ 
[S1(x1)^S2(x2) --> T2(x1,f1(x1),f2(x1,x2))] ^ 
[S1(x1)^S3(x3) --> T3(x3,f1(x1),f3(x1,x3))] ^ 
[S4(x4) --> T4(x4,f4(x4))]
Source: running example in our paper (Fig.5a, page1533) 
Output:
The rewrite process is successful.
Original plain SO tgd has 1 solution(s) available.
-----------------------------------------------------------------
Solution:1
No.1:
Current solution has 2 nested tgds.
Nested tgd No.1:
*x1 S1(x1) --> ?y1 [T1(x1,y1) ^
*x2 S2(x2) --> ?y2 [T2(x1,y1,y2)] ^
*x3 S3(x3) --> ?y3 [T3(x3,y1,y3)]  ]
 
Nested tgd No.2:
*x4 S4(x4) --> [T4(x4,y4)   ]
 
 
 
 
16. Input plain SO tgd:
 
 ?f1(),?f2() 
*x1,*x2,*x3,*x4  [S1(x1) --> T1(x1,f1(x1))] ^
[S1(x1)^S2(x1,x2) --> T2(x2,f1(x1))] ^
[S3(x3)^S4(x3,x4) --> T3(x3,f2(x3,x4))]  

Source: Example 3.1 in our paper (page1529)  Note: there is some mistake in the Example 3.4, please use this result as the correct version.
******************************************************************
The rewrite process is successful.
Original plain SO tgd has 1 solution(s) available.
-----------------------------------------------------------------
Solution:1
No.1:
Current solution has 2 nested tgds.
Nested tgd No.1:
*x1 S1(x1) --> ?y1 [T1(x1,y1) ^
*x2 S2(x1,x2) --> [T2(x2,y1)]  ]
 
Nested tgd No.2:
*x3,*x4 S3(x3)^S4(x3,x4) --> ?y2 [T3(x3,y2)   ]
******************************************************************
 
 
 
17. Input plain SO tgd:
 ?f1(),?f2() 
*x1  [S1(x1) --> T1(x1,f1(x1))] ^
[S1(x1)^S2(x1,x2) --> T2(x2,f1(x1))] ^
[S2(x1,x2)^S3(x1,x3) --> T3(x3,f2(x1,x2,x3))] ^
[S1(x1)^S3(x1,x3) --> T4(x1,x3)]  
 
Source: example  our paper (Fig.3a, page1532) 
 
The rewrite process is successful.
Original plain SO tgd has 2 solution(s) available.
-----------------------------------------------------------------
Solution:1
No.1:
Current solution has 2 nested tgds.
Nested tgd No.1:
*x1 S1(x1) --> ?y1 [T1(x1,y1) ^
*x2 S2(x1,x2) --> [T2(x2,y1)] ^
*x3 S3(x1,x3) --> [T4(x1,x3)]  ]
 
Nested tgd No.2:
*x1,*x2,*x3 S2(x1,x2)^S3(x1,x3) --> ?y2 [T3(x3,y2)   ]
-----------------------------------------------------------------
Solution:2
No.2:
Current solution has 2 nested tgds.
Nested tgd No.1:
*x1,*x3 S3(x1,x3) --> ^
*x2 S2(x1,x2) --> ?y2 [T3(x3,y2)] ^
S1(x1) --> [T4(x1,x3)]  
 
 
Nested tgd No.2:
*x1 S1(x1) --> ?y1 [T1(x1,y1) ^
*x2 S2(x1,x2) --> [T2(x2,y1)]  ]
 
******************************************************************
 
 
 
 
******************************************************************
******************************************************************

  • Examples used in the paper and some tests during the development of the algorithms.
    • Consistency Tests

18.   Input plain SO tgd: 

?f1() *x1 [S1(x1) --> T1(x1,f1(x1,x1))]

 

Output:

Result: Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: Not consistent, contain skolem function with repeated arguments

19. Input plain SO tgd:

?f1(),?f2() *x1,*x2,*x3,*x4 
[S1(x1,x2)^S2(x2,x3) --> T1(x1,f1(x1,x1))] ^ 
[S1(x1,x2)^S3(x2,x4) --> T2(x2,f1(x1,x1))] ^ 
[S2(x2,x3)^S3(x2,x4) --> T3(x3,f2(x2,x3,x4))]
 
 
Output:
The input plain SO tgd is not consistent, and cannot be rewritten. 
 

       
       
       
       
      Due to space restriction we cannot include all implementation details in the paper. We have implemented a more sophisticated method to build an empty RH root, which corresponds to the Algorithm 1, line 15 for building an empty root. 
      We use an example adapted from above example, which doesn't have empty RH.

       

      20. Input plain SO tgd:
      ?f1(),?f2() *x1,*x2,*x3,*x4 
      [S1(x1)^S2(x2) --> T2(f1(x1),x2)] ^ 
      [S1(x1)^S3(x1,x3) --> T3(f1(x1),x3)] ^ 
      [S1(x1)^S3(x1,x3)^S4(x3,x4) --> T4(f2(x1,x3,x4),x4)]
      source:Nested dependencies: structure and reasoning star example on p179 (see above Example 2)
       
      Without the empty root detection in Alg.1 Nest (), it gives a wrong output:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1,*x2 S1(x1)^S2(x2) --> ?y1 [T2(y1,x2)^
      *x3 S3(x1,x3) --> [T3(y1,x3)^
      *x4 S4(x3,x4) --> ?y2 [T4(y2,x4)   ] ] ]
       
      With the empty root detection, the correct output is as below:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1 S1(x1) --> ?y1 ^
      *x2 S2(x2) --> [T2(y1,x2)] ^
      *x3 S3(x1,x3) --> [T3(y1,x3) ^
      *x4 S4(x3,x4) --> ?y2 [T4(y2,x4)]]  
       
      Besides an empty RH root level, our approach can also create a  new part by detecting the Skolem functions.
      The new part has empty RH. Below are two examples of create such a new part in the middle or bottom of the result nested tgd.
       
      21. Input plain SO tgd:
      ?f1(x1),?f2(x1,x2),?f3(x1,x3),?f4(x1,x3,x4,x5) *x1,*x2,*x3,*x4,*x5 
      [S1(x1) --> T1(x1,f1(x1))] ^ 
      [S1(x1)^S2(x2) --> T2(x2,f2(x1,x2))] ^ 
      [S1(x1)^S3(x1,x3) --> ] ^ 
      [S1(x1)^S3(x1,x3)^S4(x4,x5) --> T4(x3,x4,f3(x1,x3),f4(x1,x3,x4,x5))]

      Original Nested tgd
      *x1 S1(x1) --> ?y1 
      [T1(x1,y1) ^ *x2 S2(x2) --> ?y2 
      [T2(x2,y2)] ^ *x3 S3(x1,x3) --> ?y3 ^ 
      *x4,*x5 S4(x4,x5) --> ?y4 [T4(x3,x4,y3,y4)] ]
      Skolemized nested tgd
      ?f1(x1),?f2(x1,x2),?f3(x1,x3),?f4(x1,x3,x4,x5) 
      *x1 S1(x1) --> [T1(x1,f1(x1)) 
      *x2 S2(x2) --> [T2(x2,f2(x1,x2)) 
      *x3 S3(x1,x3) --> 
      *x4,*x5 S4(x4,x5) --> [T4(x3,x4,f3(x1,x3),f4(x1,x3,x4,x5)) ] ] ]
       

       
      Output:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x2) --> ?y2 [T2(x2,y2)] ^
      *x3 S3(x1,x3) --> ?y3 ^
      *x4,*x5 S4(x4,x5) --> ?y4 [T4(x3,x4,y3,y4)]  ]
       
       The new nested tgd is same with the original nested tgd
       
       
      22. Input plain SO tgd (example of inserting a level in the bottom):
      ?f1(x1),?f2(x1,x2),?f3(x1,x3,x4),?f4(x1,x2,x5) *x1,*x2,*x3,*x4,*x5 
      [S1(x1) --> T1(x1,f1(x1))] ^ 
      [S1(x1)^S2(x2) --> T2(x2,f2(x1,x2))] ^ 
      [S1(x1)^S3(x3,x4) --> T3(x3,x4,f3(x1,x3,x4))] ^ 
      [S1(x1)^S2(x2)^S4(x1,x5) --> ]

       
      Output:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x2) --> ?y2 [T2(x2,y2) ^
      *x5 S4(x1,x5) --> ?y4] ^
      *x3,*x4 S3(x3,x4) --> ?y3 [T3(x3,x4,y3)]  ]
       
       
       
       
      23. Input PSO TGD:
      ?f1(),?f2() *x1,*x2,*x3 
      [S1(x1,x2,x3) --> T1(f1(x1,x2),f2(x1,x2,x3),x3)]

      Output:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1,*x2 ?y1 
      *x3 ?y2 
      S1(x1,x2,x3) --> [T1(y1,y2,x3)   ]
       
      24. Input plain SO tgd:
      ?f1(),?f2(),?f3(),?f4() *x1,*x2,*x3,*x4,*x5 
      [S1(x1) ^ S2(x2) ^ S3(x3) --> T1(x1,x2,x3,f1(x1),f2(x1,x2),f3(x1,x2,x3))] ^ 
      [S4(x4,x5) --> T2(x4,x5,f4(x4 ,x5))]
       
      Output:
      The rewrite process is successful.
      Original plain SO tgd has 1 solution(s) available.
      -----------------------------------------------------------------
      Solution:1
      No.1:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1 S1(x1) --> ?y1 ^
      *x2 S2(x2) --> ?y2 ^
      *x3 S3(x3) --> ?y3 [T1(x1,x2,x3,y1,y2,y3)]  
       
       
      Nested tgd No.2:
      *x4,*x5 S4(x4,x5) --> [T2(x4,x5,y4)   ]
       
       
      • Test when results are multiple nested tgds in a single solution
       
      25. Input plain SO tgd:
      ?f1(),?f2() *x1 
      [S1(x1) --> T1(x1,f1(x1))] ^ 
      [S1(x1)^S2(x1) --> T2(x1,f1(x1))] ^ 
      [S3(x1)^S4(x1) --> T3(x1,f2(x1))]
       
      Output:
      The rewrite process is successful.
      Original plain SO tgd has 1 solution(s) available.
      -----------------------------------------------------------------
      Solution:1
      No.1:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      S2(x1) --> [T2(x1,y1)]  ]
       
      Nested tgd No.2:
      *x1 S3(x1)^S4(x1) --> [T3(x1,y2)   ]
       
       
      26. Input plain SO tgd:
      ?f1(),?f2() *x1,*x2,*x3,*x4 
      [S1(x1,x2)^S2(x2,x3) --> T1(x1,f1(x1,x2))] ^ 
      [S1(x1,x2)^S3(x2,x4) --> T2(x2,f1(x1,x2))] ^ 
      [S2(x2,x3)^S3(x2,x4) --> T3(x3,f2(x2,x3,x4))]
       
      Output:
      The rewrite process is successful.
      Original plain SO tgd has 1 solution(s) available.
      -----------------------------------------------------------------
      Solution:1
      No.1:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1,*x2 S1(x1,x2) --> ?y1 ^
      *x3 S2(x2,x3) --> [T1(x1,y1)] ^
      *x4 S3(x2,x4) --> [T2(x2,y1)]  
       
       
      Nested tgd No.2:
      *x2,*x3,*x4 S2(x2,x3)^S3(x2,x4) --> [T3(x3,y2)   ]
       
       
      27. Input plain SO tgd 
      ?f1(),?f2(),?f3(),?f4(),?f5(),?f6() *x1*x1*x1 
      [S1(x1) --> T1(x1,f1(x1))] ^ 
      [S1(x1)^S2(x2) --> T2(x2,f2(x1,x2))] ^ 
      [S1(x1)^S3(x3) --> T3(x3,f3(x1,x3))] ^ 
      [S4(x4) --> T4(x4,f4(x4))] ^ 
      [S1(x1)^S4(x4) --> T5(x1,x4)] ^ 
      [S4(x4)^S5(x5) --> T6(x4,x5,f6(x4,x5))]
       
      Output:
      The rewrite process is successful.
      Original plain SO tgd has 2 solution(s) available.
      -----------------------------------------------------------------
      Solution:1
      No.1:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x2) --> ?y2 [T2(x2,y2)] ^
      *x3 S3(x3) --> ?y3 [T3(x3,y3)] ^
      *x4 S4(x4) --> [T5(x1,x4)]  ]
       
      Nested tgd No.2:
      *x4 S4(x4) --> ?y4 [T4(x4,y4) ^
      *x5 S5(x5) --> ?y6 [T6(x4,x5,y6)]  ]
       
      -----------------------------------------------------------------
      Solution:2
      No.2:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x4 S4(x4) --> ?y4 [T4(x4,y4) ^
      *x1 S1(x1) --> [T5(x1,x4)] ^
      *x5 S5(x5) --> ?y6 [T6(x4,x5,y6)]  ]
       
      Nested tgd No.2:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x2) --> ?y2 [T2(x2,y2)] ^
      *x3 S3(x3) --> ?y3 [T3(x3,y3)]  ]
       
      Now we look at a simpler example:
      Input plain SO tgd:
      ?f1(),?f2() 
      *x1  [S1(x1) --> T1(x1,f1(x1))] ^
      [S1(x1)^S2(x1,x2) --> T2(x2,f1(x1))] ^
      [S2(x1,x2)^S3(x1,x3) --> T3(x3,f2(x1,x2,x3))] ^
      [S1(x1)^S3(x1,x3) --> T4(x1,x3)]  
       
      ******************************************************************
      The rewrite process is successful.
      Original plain SO tgd has 2 solution(s) available.
      -----------------------------------------------------------------
      Solution:1
      No.1:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x1,x2) --> [T2(x2,y1)] ^
      *x3 S3(x1,x3) --> [T4(x1,x3)]  ]
       
      Nested tgd No.2:
      *x1,*x2,*x3 S2(x1,x2)^S3(x1,x3) --> [T3(x3,y2)   ]
      -----------------------------------------------------------------
      Solution:2
      No.2:
      Current solution has 2 nested tgds.
      Nested tgd No.1:
      *x1,*x3 S3(x1,x3) --> ^
      *x2 S2(x1,x2) --> ?y2 [T3(x3,y2)] ^
      S1(x1) --> [T4(x1,x3)]  
       
       
      Nested tgd No.2:
      *x1 S1(x1) --> ?y1 [T1(x1,y1) ^
      *x2 S2(x1,x2) --> [T2(x2,y1)]  ]
       
      ******************************************************************
       
       
      • Hierarchical ordering Tests
       28. Input plain SO tgd:
      ?f1(),?f2(),?f3() *x1,*x2,*x3,*x4 
      [S1(x1)^S2(x2) --> T1(x1,f1(x1,x2))] ^ 
      [S1(x1)^S2(x2)^S3(x3) --> T2(x3,f1(x1,x2),f2(x1,x2,x3))] ^ 
      [S1(x1)^S2(x2)^S4(x4) --> T3(x4,f1(x1,x2),f3(x1,x2,x4))]

      Output:
      The rewrite process is successful.
      The equivalent nested tgds is:
      *x1,*x2 S1(x1)^S2(x2) --> ?y1 [T1(x1,y1) ^
      *x3 S3(x3) --> ?y2 [T2(x3,y1,y2)] ^
      *x4 S4(x4) --> ?y3 [T3(x4,y1,y3)]  ]
       
       
       
      29. Input plain SO tgd:
      ?f1(),?f2() *x1,*x2,*x3 
      [S1(x1) --> T1(x1,f1(x1))] ^ 
      [S1(x1)^S2(x2,x3) --> T2(x3,f2(x1,x2))]
      Output:
       Our algorithm cannot rewrite the original plain SO tgd to a nested tgd, the reason is: 
      The Skolem function doesn't fit into the pattern tree: 
      f2(x1,x2)
       
      Document Actions