Semiring-annotated data
- 5 October 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 41 (3), 5-14
- https://doi.org/10.1145/2380776.2380778
Abstract
We present an overview of the literature on querying semiring-annotated data , a notion we introduced five years ago in a paper with Val Tannen. First, we show that positive relational algebra calculations for various forms of annotated relations, as well as provenance models for such queries, are particular cases of the same general algorithm involving commutative semirings. For this reason, we present a formal framework for answering queries on data with annotations from commutative semirings, and propose a comprehensive provenance representation based on semirings of polynomials . We extend these considerations to XQuery views over annotated, unordered XML data, and show that the semiring framework suffices for a large positive fragment of XQuery applied to such data. Finally, we conclude with a brief overview of the large body of work that builds upon these results, including both extensions to the theoretical foundations and uses in practical applications.Keywords
This publication has 21 references indexed in Scilit:
- Reconcilable DifferencesTheory of Computing Systems, 2011
- Containment of Conjunctive Queries on Annotated RelationsTheory of Computing Systems, 2011
- Provenance in Databases: Why, How, and WhereFoundations and Trends® in Databases, 2007
- Models for Incomplete and Probabilistic InformationLecture Notes in Computer Science, 2006
- Tracing the lineage of view data in a warehousing environmentACM Transactions on Database Systems, 2000
- A probabilistic relational algebra for the integration of information retrieval and database systemsACM Transactions on Information Systems, 1997
- Query evaluation in probabilistic relational databasesTheoretical Computer Science, 1997
- Containment of conjunctive queriesACM Transactions on Database Systems, 1995
- Incomplete Information in Relational DatabasesJournal of the ACM, 1984
- Fuzzy setsInformation and Control, 1965