2023/05/14 by André Frochaux, Frochaux, André, Sarah Kleest-Meißner +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Data Management and Algorithms #Advanced Database Systems and Queries
paper · pdf · doi:10.48550/arxiv.2305.08236
A query model for sequence data was introduced in [11] in the form of subsequence-queries with wildcards and gap-size constraints (swg-queries, for short). These queries consist of a pattern over an alphabet of variables and types, as well as a global window size and a number of local gap-size constraints. We propose two new extensions of swg-queries, which both enrich the expressive power of swg-queries in different ways: subsequence-queries with generalised gap-size constraints (swgg-queries, for short) and disjunctive subsequence-queries (dswg-queries, for short). We discuss a suitable characterisation of containment, a classical property considered in database theory, and adapt results concerning the discovery of swg-queries to both, swgg-queries and dswg-queries.