{'fraction_non_alphanumeric': 0.027294303797468354, 'fraction_numerical': 0.006329113924050633, 'mean_word_length': 5.138349514563107, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relaxed Regular Path Queries in Lightweight DLs (Extended Abstract)

Regular path queries (RPQs) is a well-investigated query language that dates back to the early 90’s, where its capabilities to navigate graph-structured data attracted much attention in research on semistructured data and graph databases [10,6]. This interest was revived in recent years, since in many application areas data is graph-structured and represented in graph database models. Notable examples of applications of RPQs are querying biological networks, the semantic web and social networks. Moreover, RPQs and its extensions are part of SPARQL, which is the standard language recommended by the W3C to query RDF data. Formally, a graph database consists of a labeled directed graph, where edge labels correspond to binary predicates stating relations between data items. A RPQ consists of a regular language over these labels, and retrieves pairs of data items (a, b) that are connected by paths complying to the specified regular language. The extension of two-way RPQs (2RPQ) allows to traverse edges backwards, and the more expressive language of conjunctive 2RPQs (C2RPQ) allows conjunctions of 2RPQs that can share variables. In scenarios where a RPQ yields no answers over a particular database, it can be useful to relax the query to retrieve more than the classical answers, i.e., pairs that are connected by paths that are “similar enough” to the paths required by the query. This can be practical to provide feasible alternatives in applications where data is gathered automatically from heterogeneous data sources and exact semantics need not yield the expected results. Similarly, in applications where the data is irregular and evolves in structure and content, it can be hard for users to have full knowledge of its vocabulary and structure and queries that approximate/relax the set of answers may be helpful. Several approaches have been considered to address this problem, as for instance, [8,9,7,12]. In particular, [7] proposes an elegant and tractable solution that uses a weighted finite-state transducers to define the approximation semantics. Roughly speaking, such a transducer is a mechanism that transforms input words into corresponding output words, and computes a weight quantifying the cost of the transformation. The idea is to use a transducer as a means to specify which paths are allowed to be considered approximations/distortions of the “ideal” paths specified by the query, and to specify their distortion costs.