Preferentially Annotated Regular Path Queries

Abstract. In this paper, we introduce preferential regular path queries. These are regular path queries whose symbols are annotated with prefer-ence weights for “scaling ” up or down the intrinsic importance of match-ing a symbol against a (semistructured) database edge label. Annotated regular path queries are expressed syntactically as annotated regular expressions. We interpret these expressions in a uniform semiring frame-work, which allows different semantics specializations for the same syn-tactic annotations. For our preference queries, we study three important aspects: (1) (progressive) query answering (2) (certain) query answer-ing in LAV data-integration systems, and (3) query containment and equivalence. In all of these, we obtain important positive results, which encourage the use of our preference framework for enhanced querying of semistructured databases.