search

ashkapsky / BigDatalog

Apache License 2.0
55 stars 20 forks source link

StackOverflowError for recursion of type a <- b, b <- a #8

Open thomasrebele opened 6 years ago

thomasrebele commented 6 years ago

Hello,

I tried to minimize #7 further. I arrived at

a(X,Y) <- b(X,Y).
b(X,Y) <- a(X,Y).

which leads to a StackOverflowError:

Exception in thread "main" java.lang.StackOverflowError
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1439)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616)
...

and then the stack trace repeats again and again

interesaaat commented 6 years ago

Hi Thomas,

I think that the problem here is that the program is not a valid Datalog program for Bigdatalog because there is no base relation.

On Sat, Oct 14, 2017, 2:42 PM Thomas Rebele notifications@github.com wrote:

Hello,

I tried to minimize #7 https://github.com/ashkapsky/BigDatalog/issues/7 further. I arrived at

a(X,Y) <- b(X,Y). b(X,Y) <- a(X,Y).

which leads to a StackOverflowError:

Exception in thread "main" java.lang.StackOverflowError at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1439) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616) ...

and then the stack trace repeats again and again

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/ashkapsky/BigDatalog/issues/8, or mute the thread https://github.com/notifications/unsubscribe-auth/ABdo92MCN25GdlGmQj8IHp6tIMJWuOPDks5ssSrhgaJpZM4P5igc .

thomasrebele commented 6 years ago

Hi, thanks for the idea. I tried it with an input relation:

a(X,Y) <- b(X,Y).
b(X,Y) <- a(X,Y).
database({  a(X:string, Y:string) }).

with query b(A,B).

I still get an StackOverflowError, but with a different stack trace:

Exception in thread "main" java.lang.StackOverflowError
    at java.lang.StringBuilder.append(StringBuilder.java:136)
    at edu.ucla.cs.wis.bigdatalog.compiler.predicate.DerivedPredicate.toString(DerivedPredicate.java:43)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.BasicClique.toString(BasicClique.java:49)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:338)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:329)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYLiteralType(XYCliqueAnalyzer.java:574)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYRuleType(XYCliqueAnalyzer.java:439)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique2(XYCliqueAnalyzer.java:292)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:273)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:347)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:329)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYLiteralType(XYCliqueAnalyzer.java:574)
    at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYRuleType(XYCliqueAnalyzer.java:439)
...
interesaaat commented 6 years ago

Still the same problem, a is an intensional relation. To make it work you have to add another (extensional) relation c and populate a from c:

a(X,Y) <- c(X,Y).

a(X,Y) <- b(X,Y). b(X,Y) <- a(X,Y). database({ c(X:string, Y:string) }).

On Sun, Oct 15, 2017 at 3:44 AM, Thomas Rebele notifications@github.com wrote:

Hi, thanks for the idea. I tried it with an input relation:

a(X,Y) <- b(X,Y). b(X,Y) <- a(X,Y). database({ a(X:string, Y:string) }).

with query b(A,B).

I still get an StackOverflowError, but with a different stack trace:

Exception in thread "main" java.lang.StackOverflowError at java.lang.StringBuilder.append(StringBuilder.java:136) at edu.ucla.cs.wis.bigdatalog.compiler.predicate.DerivedPredicate.toString(DerivedPredicate.java:43) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.BasicClique.toString(BasicClique.java:49) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:338) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:329) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYLiteralType(XYCliqueAnalyzer.java:574) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYRuleType(XYCliqueAnalyzer.java:439) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique2(XYCliqueAnalyzer.java:292) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:273) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:347) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.isXYClique(XYCliqueAnalyzer.java:329) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYLiteralType(XYCliqueAnalyzer.java:574) at edu.ucla.cs.wis.bigdatalog.compiler.analysis.XYCliqueAnalyzer.findXYRuleType(XYCliqueAnalyzer.java:439) ...

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ashkapsky/BigDatalog/issues/8#issuecomment-336702785, or mute the thread https://github.com/notifications/unsubscribe-auth/ABdo9yI3UuIi8mUSa41pMD8N-o9-Eazoks5sseIMgaJpZM4P5igc .

thomasrebele commented 6 years ago

That gives me still another StackOverflowError:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.ArrayList.iterator(ArrayList.java:834)
    at edu.ucla.cs.wis.bigdatalog.compiler.predicate.graph.PCGAndNode.isNonLinearRecursive(PCGAndNode.java:80)
    at edu.ucla.cs.wis.bigdatalog.compiler.recursion.Clique.determineRecursiveType(Clique.java:110)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1558)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186)
    at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249)
...
interesaaat commented 6 years ago

Ok then it is a bug :)

On Sun, Oct 15, 2017 at 12:30 PM, Thomas Rebele notifications@github.com wrote:

That gives me still another StackOverflowError:

Exception in thread "main" java.lang.StackOverflowError at java.util.ArrayList.iterator(ArrayList.java:834) at edu.ucla.cs.wis.bigdatalog.compiler.predicate.graph.PCGAndNode.isNonLinearRecursive(PCGAndNode.java:80) at edu.ucla.cs.wis.bigdatalog.compiler.recursion.Clique.determineRecursiveType(Clique.java:110) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1558) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateCliqueOperator(ProgramGenerator.java:1616) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateRecursiveOperator(ProgramGenerator.java:1472) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperator(ProgramGenerator.java:186) at edu.ucla.cs.wis.bigdatalog.interpreter.relational.ProgramGenerator.generateOperators(ProgramGenerator.java:249) ...

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/ashkapsky/BigDatalog/issues/8#issuecomment-336735306, or mute the thread https://github.com/notifications/unsubscribe-auth/ABdo91H-mh-tYt5sSRJI-t_Unhd9gbBrks5ssl1hgaJpZM4P5igc .

wangzk commented 6 years ago

I can reproduce the bug. It is surprise that the relation is that simple. I also ran this simple program with the author's serial Datalog engine DeALS-0.9.jar and it worked. Therefore, the bug lies on the BigDatalog side.