A reachability-based theoretical framework for modeling and querying complex probabilistic graph data

Probabilistic graph data arise in a plethora of modern applications ranging from sensor networks to RDF query tools and IP-network monitoring systems. This is due to the fact that probabilistic graphs are able to capture and model uncertainty and imprecision that characterize datasets populating the above-mentioned scenarios. On the basis of this amenity, a large family of proposals devoted to model and query probabilistic graph data appeared, with alternate fortune. Nevertheless, few of these approaches address a challenge that is, indeed, relevant for graph data management research, i.e. the issue of modeling and querying complex probabilistic graph data, which, contrary to state-of-the-art initiatives, expose an inherently-complex nature, beyond common confidence-interval-based data models. Aimed by the goal of filling this gap, in this paper we propose a novel reachability-based theoretical framework for modeling and querying complex probabilistic graph data, by also providing the definition of some meaningful classes of graph queries that allow us to extract useful knowledge from such graphs in terms of algebra-aware (sub-)graphs, plus related (query) algorithms and semantics.