Flexible Query Answering on Graph-modeled Data

The largeness and the heterogeneity of most graph-modeleddatasets in several database application areas make the queryprocess a real challenge because of the lack of a completeknowledge of the vocabulary used, as well as of the informationabout the structural relationships between the data.To overcome these problems, flexible query answering capabilitiesare an essential need. In this paper we present a general model for supporting approximate queries on graphmodeled data. Approximation is both on the vocabularies and the structure. The model is general in that it is not bound to a specific graph data model, rather it gracefully accommodates labeled directed/undirected data graphs with labeled/unlabeled edges. The query answering principles underlying the model are not compelled to a specific data graph, instead they are founded on properties inferable from the data model the data graph conforms to. We complement the work with a ranking model to deal with data approximations and with an efficient top-k retrieval algorithm which smartly accesses ad-hoc data structures andgenerates the most promising answers in an order correlatedwith the ranking measures. Experimental results prove thegood effectiveness and efficiency of our proposal on differentreal world datasets.