Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize ShEx for EXTRA predicates with non-repeated properties #133

Closed
labra opened this issue Jul 28, 2019 · 1 comment
Closed

Optimize ShEx for EXTRA predicates with non-repeated properties #133

labra opened this issue Jul 28, 2019 · 1 comment
Labels

Comments

@labra
Copy link
Member

labra commented Jul 28, 2019

A common pattern for Shape expressions is:

<S> EXTRA <p> {
 <p> @<T> {min,max}, 
 ... // other definitions without mentioning <p>
}

The meaning is that we expect between min and max values of property <p> with shape <T> and we don't give any further constraint on the rest of values of property <p>.

Currently, this pattern is checked using a regular expression like: C0{min,max}, C1* where C0 represents the <p> @<T> constraint and C1 represents the <p> NOT @<T> constraint which is very inefficient and can raise stack overflow exceptions as in issue #130

An optimization to validate shapes following this pattern is to count the number of values with property <p> that conform to shape <T> and check that it is between min and max.

@labra
Copy link
Member Author

labra commented Aug 2, 2019

The optimization has been implemented and tested. Further optimizations can be done but will have their own issues.

@labra labra closed this as completed Aug 2, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant