Formal Languages in Information Extraction and Graph Databases

摘要

This abstract covers two areas of data management, research in which formal language theory plays a central role, namely in Information Extraction and Graph Databases.Information Extraction. Automata-based foundations of Information Extraction (e.g., [9,16,34]) have become a popular research topic over the last years. One framework that has been studied in this context is that of document spanners [16]. Document spanners model information extraction tasks as functions that map input text documents to a relation of spans, i.e., intervals of start and end positions in the text. A particular interesting class of spanners is the class of regular spanners, which is based on regular languages with capture variables. This class satisfies a number of interesting complexity and expressiveness properties and therefore caused a revival of automata- and formal language techniques in database research. Examples of such work are on the enumeration of answers [1,18], expressiveness [20,21,33], complexity issues [22,29,32], integration of weights [15], and distributed evaluation [14]. That said, the document spanners framework is not the only one that is studied in this context, and there are other elegant frameworks that can express information extraction functions beyond the spanner framework, e.g., [9,34].