论文标题
序列数据中的表现力
Expressiveness within Sequence Datalog
论文作者
论文摘要
在旧应用程序和新应用程序中，我们将数据数据研究作为序列数据库的语言。我们重新考虑了数据编写程序的经典特征，例如否定，递归，中间谓词和较高的股权关系。我们还考虑了对序列有用的新功能，尤其是路径表达式和“包装”之间的方程式。我们的目标是在序列的背景下阐明所有这些不同特征的相对表现力。为了我们的目标，我们建立了许多冗余和原始性结果，表明某些功能可以或不能以其他功能来表达。这些结果描绘了所有可能使用我们考虑的六个功能形成的所有可能的序列数据片段之间的表达关系。
Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and "packing". Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider.
