This section extends the information retrieval capability of an ordinary semistructured query language to handle labels with properties. Emphasis is on the query language aspects that are affected by the new labels. These aspects are quite localized, since labels are used only in path regular expressions to traverse paths in the semistructure. There are two parts to the extension. First, when retrieving data, only valid paths should be followed, as discussed in Section 2. We define a Valid predicate to test whether a path is valid by determining whether the path can be collapsed to a single edge with a label that preserves the information content of all the labels along the path. Second, path regular expressions must be generalized to support labels with properties and required properties. This involves redefining how labels are matched in the evaluation of an expression. We conclude by observing that the extension is strictly additive--the extended retrieval mechanism works as expected on a semistructure with simple string labels.