Return to search

Relaxation of Subgraph Queries Delivering Empty Results

Graph databases with the property graph model are used in multiple domains including social networks, biology, and data integration. They provide schema-flexible storage for data of a different degree of a structure and support complex, expressive queries such as subgraph isomorphism queries. The exibility and expressiveness of graph databases make it difficult for the users to express queries correctly and can lead to unexpected query results, e.g. empty results. Therefore, we propose a relaxation approach for subgraph isomorphism queries that is able to automatically rewrite a graph query, such that the rewritten query is similar to the original query and returns a non-empty result set. In detail, we present relaxation operations applicable to a query, cardinality estimation heuristics, and strategies for prioritizing graph query elements to be relaxed. To determine the similarity between the original query and its relaxed variants, we propose a novel cardinality-based graph edit distance. The feasibility of our approach is shown by using real-world queries from the DBpedia query log.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:80646
Date16 September 2022
CreatorsVasilyeva, Elena, Thiele, Maik, Mocan, Adrian, Lehner, Wolfgang
PublisherACM
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/acceptedVersion, doc-type:conferenceObject, info:eu-repo/semantics/conferenceObject, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relation978-1-4503-3709-0, 28, 10.1145/2791347.2791382, info:eu-repo/grantAgreement/European Commission/FP7 | SP1 | ICT/284613//Linked Knowledge in Manufacturing, Engineering and Design for Next-Generation Production/LINKEDDESIGN

Page generated in 0.0022 seconds