Coalgebraic Foundations of Semi-Structured Data

数据库在现代信息社会中具有不可替代的作用。传统上，信息存储在采用关系数据模型和查询语言SQL的严格结构化的数据库中。这导致了高度优化的关系数据库管理系统，如Oracle或Mircrosoft SQL，它们具有大规模的工业部署。支撑这些系统的成功的是它们与关系代数和数理逻辑中的数学基础的密切联系。然而，互联网已经极大地改变了我们对数据和数据库的理解：i）Web上的数据本质上是分层的，并以网络/图形的形式排列; ii）Web的分散性意味着数据来自各种异构源，通常不完整或不可靠，并且没有统一的结构。尽管如此，Web数据仍然保留了一些结构，因此，半结构化数据试图了解什么结构持续存在以及如何利用它。在数学上，半结构化数据通常表示为未排名的标记树，其中节点通过父，子和兄弟关系访问，或者标记图，其中节点通过边关系访问。数据元素存储在节点处。由于上述Web数据的特殊特征，与存储在关系数据库中的数据的查询语言相比，用于半结构化数据的查询语言面临显著更大的挑战：i）查询必须在树或图内导航路径结构，并且查询沿着这种路径沿着找到的数据元素，以探索数据的重要属性;以及ii）必须通常经由本体将公共词汇表添加到数据，该公共词汇表提供用于集成来自异类源的语义相关数据的逻辑层。但是，随着半结构化数据模型变得越来越复杂和富有表现力-例如，为了对数据的不确定性进行建模-匹配查询和本体语言的发展一直在努力跟上步伐。事实上，虽然有大量的工作，具体的半结构化数据模型和相应的查询语言，目前还没有全面的理论，既占现有的半结构化数据格式和查询语言，并能够指导他们的扩展到下一代的半结构化数据格式。例如，虽然广泛使用的查询语言XML最近已经从XML扩展到图形数据，目前还没有商定的机制，以进一步扩展XML到图形数据的不确定性，我们的核心见解是，共代数提供了正确的抽象层次，以支持一个全面的理论，查询和本体语言的半结构化数据。这是因为i）余代数通过余代数模态逻辑推广了用于遍历树和图的常用模态逻辑; ii）余代数通过余代数逻辑编程推广了基于逻辑编程的标准规则本体语言。

Databases are irreplaceable in our modern information society. Classically, information has been stored in rigidly structured databases employing the relational data model and the query language SQL. This has led to highly optimised relational database management systems such as Oracle or Mircrosoft SQL that have large-scale industrial deployment. Underpinning much of the success of these systems has been their close connection with their mathematical foundations within relational algebra and mathematical logic. However, the internet has dramatically changed our understanding of data and databases: i) data on the Web is inherently hierarchical and arranged in a network/graph; and ii) the decentralised nature of the Web means that data comes from various heterogenous sources, is often incomplete or unreliable and has no uniform structure. Still, Web data retains some structure and, consequently, semi-structured data seeks to understand what structure persists and how it can be utilised. Examples of widespread, industrially-used data models are XML, JSON and RDF.Mathematically, semi-structured data is usually represented as unranked labelled trees where nodes are accessed via the parent, child and sibling relations or labelled graphs where nodes are accessed via the edge relation. Data elements are stored at the nodes. Due to the special features of Web data mentioned above, query languages for semi-structured data face significantly greater challenges compared to those for data stored in a relational database: i) queries must navigate the path structure within a tree or graph and query the data elements found along such paths to explore important properties of the data; and ii) one must add a common vocabulary to the data - often via an ontology - that provides a logical layer for integrating semantically related data from heterogeneous sources. But as semi-structured data models have become increasingly sophisticated and expressive - e.g. in order to model the uncertainty attached to the data - the development of matching query and ontology languages have struggled to keep pace. Indeed, while there is a large body of work on specific semi-structured data models and their corresponding query languages there is currently no comprehensive theory that both accounts for existing semi-structured data formats and their query languages, and is able to guide their extension to the next generation of semi-structured data formats. For example, while the widely used query language XPath has been recently extended from XML to graph data, there is currently no agreed mechanism to further extend XPath to graph data with uncertainty.Our central insight is that coalgebra provides the right level of abstraction to underpin a comprehensive theory of query and ontology languages for semi-structured data. This is because i) coalgebra generalises - via coalgebraic modal logic - the usual modal logics used for traversing trees and graphs; and ii) coalgebra generalises - via coalgebraic logic programming - standard rule-based ontology languages which are based upon logic programming.