Top

Published in:

2018 | OriginalPaper | Chapter

Computing Probabilistic Queries in the Presence of Uncertainty via Probabilistic Automata

Authors : Theodore Andronikos, Alexander Singh, Konstantinos Giannakis, Spyros Sioutas

Published in: Algorithmic Aspects of Cloud Computing

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The emergence of uncertainty as an inherent aspect of RDF and linked data has spurred a number of works of both theoretical and practical interest These works aim to incorporate such information in a meaningful way in the computation of queries. In this paper, we propose a framework of query evaluation in the presence of uncertainty, based on probabilistic automata, which are simple yet efficient computational models. We showcase this method on relevant examples, where we show how to construct and exploit the convenient properties of such automata to evaluate RDF queries with adjustable cutoff. Finally, we present some directions for further investigation on this particular line of research, taking into account possible generalizations of this work.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Towards an Algebraic Cost Model for Graph Operators

next chapter Improving Rule-Based Elasticity Control by Adapting the Sensitivity of the Auto-Scaling Decision Timeframe

SPARQL 1.1 Query Language. Technical report, W3C (2013), http://www.w3.org/TR/sparql11-query

Akbarinia, R., Valduriez, P., Verger, G.: Efficient evaluation of SUM queries over probabilistic data. IEEE Trans. Knowl. Data Eng. 25(4), 764–775 (2013)CrossRef

Baier, C., Grösser, M., Bertrand, N.: Probabilistic \(\omega \)-automata. J. ACM 59(1), 1–52 (2012)MathSciNetCrossRefMATH

Barceló, P., Libkin, L., Reutter, J.L.: Querying regular graph patterns. J. ACM (JACM) 61(1), 8 (2014)MathSciNetCrossRefMATH

Dalvi, N., Suciu, D.: Efficient query evaluation on probabilistic databases. The VLDB J.- Int. J. Very Large Data Bases 16(4), 523–544 (2007)CrossRef

Fang, H., Zhang, X.: pSPARQL: a querying language for probabilistic RDF. In: Proceedings of ISWC Posters and Demos (2016)

Fernandez, M., Suciu, D.: Optimizing regular path expressions using graph schemas. In: Proceedings of the 14th International Conference on Data Engineering, pp. 14–23. IEEE (1998)

Giannakis, K., Andronikos, T.: Querying linked data and Büchi automata. In: 2014 9th International Workshop on Semantic and Social Media Adaptation and Personalization (SMAP), pp. 110–114. IEEE (2014)

Giannakis, K., Theocharopoulou, G., Papalitsas, C., Andronikos, T., Vlamos, P.: Associating \(\omega \)-automata to path queries on Webs of Linked Data. Eng. Appl. Artif. Intell. 51, 115–123 (2016)CrossRef

10.

Hartig, O.: An overview on execution strategies for Linked Data queries. Datenbank-Spektrum 13(2), 89–99 (2013)CrossRef

11.

Hua, M., Pei, J.: Probabilistic path queries in road networks: traffic uncertainty aware path selection. In: Proceedings of the 13th International Conference on Extending Database Technology, pp. 347–358. ACM (2010)

12.

Huang, H., Liu, C.: Query evaluation on probabilistic RDF databases. In: Vossen, G., Long, D.D.E., Yu, J.X. (eds.) WISE 2009. LNCS, vol. 5802, pp. 307–320. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04409-0_32 CrossRef

13.

Khan, A., Chen, L.: On uncertain graphs modeling and queries. Proc. VLDB Endowment 8(12), 2042–2043 (2015)CrossRef

14.

Krompaß, D., Nickel, M., Tresp, V.: Querying factorized probabilistic triple databases. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8797, pp. 114–129. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11915-1_8

15.

Lian, X., Chen, L., Wang, G.: Quality-aware subgraph matching over inconsistent probabilistic graph databases. IEEE Trans. Knowl. Data Eng. 28(6), 1560–1574 (2016)CrossRef

16.

Marshall, M.S., Boyce, R., Deus, H.F., Zhao, J., Willighagen, E.L., Samwald, M., Pichler, E., Hajagos, J., Prud’hommeaux, E., Stephens, S.: Emerging practices for mapping and linking life sciences data using RDF-a case series. Web Semant. Sci. Serv. Agents World Wide Web 14, 2–13 (2012)CrossRef

17.

Paz, A.: Introduction to probabilistic automata. Academic Press Inc., Orlando (1971)MATH

18.

Rabin, M.O.: Probabilistic automata. Inf. Control 6(3), 230–245 (1963)MathSciNetCrossRefMATH

19.

Reynolds, D.: Position paper: uncertainty reasoning for linked data. In: Workshop, vol. 14 (2014)

20.

Schoenfisch, J.: Querying probabilistic ontologies with SPARQL. In: Proceedings GI-Edition, vol. 232, pp. 2245–2256 (2014)

21.

Sistla, A.P., Hu, T., Chowdhry, V.: Similarity based retrieval from sequence databases using automata as queries. In: Proceedings of the Eleventh International Conference on Information and Knowledge Management, pp. 237–244. ACM (2002)

22.

Theocharopoulou, G., Giannakis, K.: Web mining to create semantic content: a case study for the environment. In: Iliadis, L., Maglogiannis, I., Papadopoulos, H., Karatzas, K., Sioutas, S. (eds.) AIAI 2012. IFIP AICT, vol. 382, pp. 411–420. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33412-2_42 CrossRef

23.

Wang, X., Ling, J., Wang, J., Wang, K., Feng, Z.: Answering provenance-aware regular path queries on RDF graphs using an automata-based algorithm. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 395–396. ACM (2014)

24.

Zhang, X., Feng, Z., Wang, X., Rao, G., Wu, W.: Context-free path queries on RDF graphs. In: Groth, P., Simperl, E., Gray, A., Sabou, M., Krötzsch, M., Lecue, F., Flöck, F., Gil, Y. (eds.) ISWC 2016. LNCS, vol. 9981, pp. 632–648. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46523-4_38 CrossRef

Title: Computing Probabilistic Queries in the Presence of Uncertainty via Probabilistic Automata
Authors: Theodore Andronikos
Alexander Singh
Konstantinos Giannakis
Spyros Sioutas
Publisher: Springer International Publishing
Book: Algorithmic Aspects of Cloud Computing
Print ISBN: 978-3-319-74874-0

Electronic ISBN: 978-3-319-74875-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-74875-7_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner