Detecting Unsatisfiable Conjunctive Property Path Queries under Shape Expression Schema
Keywords:
Graph Data, RDF, Property Path, SatisfiabilitySynopsis
This is a Chapter in:
Book:
Automated Systems, Data, and Sustainable Computing
Series:
Chapter Abstract:
Shape Expression (ShEx) is a novel schema language proposed for RDF/graph data. For a ShEx schema S and a query q, q is said to be unsatisfiable if for any valid data D under S q reports an empty answer over D. In general, the size of RDF/graph data is very large, and thus it is inefficient to perform unsatisfiable queries on such data. Therefore, it is desirable that we can detect unsatisfiable queries efficiently before executing them. In this paper, we consider Conjunctive Property Path, a generalization of Property Path defined in SPARQL 1.1, as the query language. First, we propose an algorithm for determining satisfiability of Conjunctive Property Path queries under ShEx schema. Then we conducted a preliminary experiment, which results suggest that the proposed algorithm determines if a given Conjunctive Property Path query is satisfiable efficiently.
Cite this paper as:
Maedaa Y., Suzuki N. (2022) Detecting Unsatisfiable Conjunctive Property Path Queries under Shape Expression Schema. In: Tiako P.F. (ed) Automated Systems, Data and Sustainable Computing. Chronicle of Computing. OkIP. https://doi.org/10.55432/978-1-6692-0001-7_2
Contact:
Nobutaka Suzuki
nsuzuki@slis.tsukuba.ac.jp
References
Baker, T. and Prud’hommeaux, E. (2019). Shape Expression (ShEx) primer.http://shexspec.github.io/primer/.
Benedikt, M., Fan, W., and Geerts, F. (2008). XPath satisfiability in the presence of DTDs. J. ACM, 55(2):8:1– 8:79. Figueira, D. (2018). Satisfiability of XPath on data trees. ACM SIGLOG News, 5(2):4–16.
Matsuoka, S. and Suzuki, N. (2020). Detecting unsatisfiable pattern queries under shape expression schema, Proceedings of the 16th International Conference on Web Information Systems and Technologies, 285–291.
Schmidt, M., Hornung, T., Lausen, G., and Pinkel, C. (2008). SP2Bench: a SPARQL performance bench- mark. Proceedings of ICDE, 371–393.
Staworko, S., Boneva, I., Labra Gayo, J. nad Hym, S., Prud’hommeaux, E., and Sorbrig., H. (2015). Complexity and expressiveness of ShEx for RDF. Proceedings of 18th International Conference on Database Theory, 195–211.
Thornton, K., Solbrig, H., Stupp, G. S., Labra Gayo, J. E., Mietchen, D., Prud’hommeaux, E., and Waagmeester, A. (2019). Using shape expressions (ShEx) to share RDF data models and to guide curation with rigorous validation. In Hitzler, P., Fernandez, M., Janowicz, K., Zaveri,
A., Gray, A. J., Lopez, V., Haller, A., and Hammar, K., editors, Proceedings of the European Semantic Web Conference, pages 606–620.
Zhang, X., den Bussche, J. V., and Picalausa, F. (2016). On the satisfiability problem for SPARQL patterns. Journal of Artificial Intelligence Research, 55:403–428.
