Execution time scales exponentially with the presence of optional properties

[larsgw]

trafficstars

What is broken?

shexjs in node

Version

1.0.0-alpha.29

What happened (e.g., it crashed)?

Validating the following data:

@prefix ex: <http://example.org/>.

ex:foo
  ex:a "bar";
  ex:b "bar";
  ex:c "bar";
  ex:d "bar";
  ex:e "bar";
  ex:f "bar";
  ex:g "bar";
  ex:h "bar";
  ex:i "bar";
  ex:j "bar";
  ex:k "bar";
  ex:l "bar";
  ex:m "bar";
  ex:n "bar";
  ex:o "bar";
  ex:p "bar";
  ex:q "bar";
  ex:r "bar";
  ex:s "bar";
  ex:t "bar";
  ex:u "bar";
  ex:v "bar";
  ex:w "bar";
  ex:x "bar";
  ex:y "bar";
  ex:z "bar".

against the following shape:

PREFIX ex: <http://example.org/>
BASE <http://example.org/shape/>

start=@<foo>

<foo> IRI CLOSED {
  ex:a LITERAL?;
  ex:b LITERAL?;
  ex:c LITERAL?;
  ex:d LITERAL?;
  ex:e LITERAL?;
  ex:f LITERAL?;
  ex:g LITERAL?;
  ex:h LITERAL?;
  ex:i LITERAL?;
  ex:j LITERAL?;
  ex:k LITERAL?;
  ex:l LITERAL?;
  ex:m LITERAL?;
  ex:n LITERAL?;
  ex:o LITERAL?;
  ex:p LITERAL?;
  ex:q LITERAL?;
  ex:r LITERAL?;
  ex:s LITERAL?;
  ex:t LITERAL?;
  ex:u LITERAL?;
  ex:v LITERAL?;
  ex:w LITERAL?;
  ex:x LITERAL?;
  ex:y LITERAL?;
  ex:z LITERAL?
}

does not finish executing within a reasonable time. The projected time would be about 23.7 years.

What should have happened instead (e.g., it shouldn't crash)?

Could it partition the triples in a way that does not scale exponentially with the number of triples? None of the predicates overlap and the shape is CLOSED.

How can we reproduce this error?

See above.