An increasing amount of information is being collected in structured, evolving, curated databases, driving the question of how information extracted from such datasets via queries should be cited. Unlike traditional research products which have a xed granularity, data citation is a challenge because the granularity varies. Di erent portions of the database, with varying granularity, may have di erent citations. Furthermore, there are an in nite number of queries over a database, so we cannot hope to explicitly attach a citation to every possible result set and/or query. We present the novel problem of automatically generating citations for general queries over a relational database, and explore a solution based on citation views, each of which attaches a citation to a view of the database. Citation views are then used to automatically construct citations for general queries.
Citation is essential to traditional scholarship. It helps identify the cited material
so that it can be retrieved, gives credit to the creator of the material, dates it, and
so on. In the context of printed materials, such as books and journals, citation
is well understood. However, the world is now digital, and an increasing amount
of information is being collected in structured and evolving curated databases,
driving database owners, publishers and standards groups to consider how such
data should be cited [
Unlike traditional publications which have a xed granularity to which
citations can be attached { e.g. a conference proceedings, or a paper in a
conference proceedings { data citation is a challenge because the granularity varies.
For example, the content of a scienti c database frequently represents the
effort of a large number of members of the scienti c community (some use cases
are presented in Section 2). Di erent portions of the database, with varying
granularity, are contributed and/or curated by di erent subgroups of these
individuals. While a citation to the database as a whole is typically provided as a
traditional publication, whose author list includes the owners and developers of
? This is an extended abstract of [
Since there are a potentially in nite number of queries, each accessing and
generating di erent subsets of the database, we cannot hope to explicitly attach
a citation to every possible result set and/or query. Instead, we must nd ways
of specifying citations for some semantically meaningful portions of the database
(possibly de ned declaratively via queries), and use these to automatically
construct citations for more general queries. Thus data citation is a computational
problem, as argued in [
Our approach draws inspiration from results in two areas: query rewriting
using views, which has been well studied in the context of query optimization,
data integration [
We start with a notion of citation views, through which database
owners specify how citations are attached to the output of some number of queries
(views) over the database representing typical usage patterns. The citation to a
general query is then constructed by rewriting it to a set of equivalent queries
using the citation views, and combining the citations attached to these views
to construct a citation to the query (Section 3). To construct the citation, we
leverage the fact that citations and provenance are both forms of annotation that
are manipulated through queries [
Currently, several data resources specify how citations to single resources, collections, result lists and data subsets should be constructed but do not generate the appropriate citation. Three such examples are Eagle-i4 (an RDF dataset built to facilitate translational science research which allows researchers to share information about resources such as cell lines and software), Reactome5, an open-source, curated and peer reviewed pathway relational database, and Drugbank6, a relational database (available also as RDF and XML) combining detailed chemical, pharmacological and pharmaceutical data with comprehensive sequence, structure, and pathway information. Instructions are given on which snippets of information on the web page view of the resource should be included in a citation to the resource, but generating the citation is left to the user.
The example we will use throughout the remainder of this paper is the IUPHAR/BPS Guide to Pharmacology (GtoPdb).7 GtoPdb is a relational database that contains expertly curated information about drugs in clinical use and some experimental drugs. Users view information through a hierarchy of web pages: The top level divides information by families of drug targets that reect typical pharmacological thinking; lower levels divide the families into subfamilies and so on down to individual drugs. The content of a particular family \landing" page is curated by a committee of experts; a family may also have a \detailed introduction page" which is written by a set of contributors, who are not necessarily the same as the committee of experts for the family. Currently, citations for these views are hard-coded into the web pages { queries are issued against the underlying relational database to obtain content for the page as well as the committee members or contributors. Thus, GtoPdb in fact does generates citations, but only to a subset of the possible queries against the underlying relational database, i.e. those corresponding to web-page views of the data.
In the future, the owners of GtoPdb would like to allow users to issue general queries against the relational database and automatically generate a citation for the result. We address this problem in the remainder of the paper. 3
We assume that queries and views are expressed as Conjunctive Queries (see [
De nition 1. A citation view is a triple (V , CV , FV ) where { V is the view de nition of form X:V (Y ) : Q; { CV is the citation query of form X: CV (Y 0) : Q0; and { FV is the citation function which transforms the output of the citation query (i.e. the bindings to variables Y 0) into a citation in some desired format, such as JSON or XML.
In V and CV : { Q and Q0 are conjunctions of atoms; { X = [x1; :::; xn], Y = [y1; :::; ym], Y 0 = [y10; :::; yp0] are ordered sequences of variables; { X Y are subsets of the variables in Q; { X and Y 0 are subsets of the variables in Q0.
The terms x1; :::; xn are the parameters of V and CV . Parameters are optional, in which case the -term may be dropped. If there is a -term the citation view is called parameterized.
Each choice of values for the parameters may lead to a di erent view instance and di erent citation. We denote the view instance by applying the view to the input parameter values, e.g. if the view is
(x1; : : : ; xn)V (Y ) : Q and is passed parameter values (a1; : : : ; an), we write
V (Y )(a1; : : : ; an): Since the citation query Q0 is also parametrized by X, each valuation of X leads to a di erent result for Q0. The output of the citation function { the citation for the view { becomes an annotation on each tuple in the output of the instantiated view. Thus for every sequence of parameter values (a1; : : : ; an), the citation for all tuples in V (Y )(a1; : : : ; an) is Fv(Cv(Y 0)(a1; : : : ; an)). Note that the citation views and queries have to be de ned by the DBA and thus they can be considered a user choice. On the other hand, we can also foresee some methods to automatic de ne views and queries for instance by using query logs. Example 1. We use as a running example a simpli ed database schema for GtoPdb, in which keys are underlined:
FamilyIntro(FID, Text) Person(PID, PName, A liation) FC(FID, PID), FID references Family, PID references Person FIC (FID, PID), FID references FamilyIntro, PID references Person MetaData(Type, Value)
Intuitively, FC captures the committee members who curate the content of a family page while FIC captures the contributors who author the Family Introduction page of a family. The last table, MetaData, captures other information that may be useful to include in citations, such as the owner of the database (\Owner", \Tony Harmar"), the URL of the database (\URL", \guidetopharmacology.org") and the current version number of the database (\Version", \23").
To express citation views for GtoPdb we start by de ning a small set of view de nitions.
F:V 1(F; N; T y) F:V 2(F; T x)
V 3(F; N; T y) : F amily(F; N; T y) : F amilyIntro(F; T x) : F amily(F; N; T y) All views except V 3 are parameterized. V 1 and V 2 restrict the output to a single tuple since the parameter, F, corresponds to the key FID in Family. V 3 contains all tuples in Family. For each of the views, we de ne a citation query.
F: CV 1(F; N; P n) : F: CV 2(F; N; T x; P n) :
F amily(F; N; T y); F C(F; C); P erson(C; P n; A)
F amily(F; N; T y); F amilyIntro(F; T x); CV 3(X1; X2) :
F IC(F; C); P erson(C; P n; A) M etaData(T 1; X1); T 1 = \Owner";
M etaData(T 2; X2); T 2 = \U RL"
Since V1 and its citation query CV 1 are parameterized by F, each valuation of V1 results in a single tuple and each tuple may have a di erent citation. As an example, for the family with FID=11 the citation is a function of the result of CV 1(F,N,Pn)(\11"), which consists of the family id, name and list of committee members. In contrast to V 1 and V 2, V 3 is not parameterized, which means that all tuples have the same citation in V3. CV 3 uses the MetaData table to obtain the url and owner of the database.
Database owners specify a set of citation views, from which the citation for a general query over the database will be constructed. Our approach is to rewrite as much of the query as possible using the view de nitions, and combine their citations to construct a citation for the input query. We start by de ning what a rewriting is.
De nition 2. Let R be a set of relation names, Q be a query, and V be a set of views. The query Q0 is a rewriting of Q using V if: { the subgoals of Q0 are either relation names in R, views in V, or comparison predicates; { Q0 is equivalent to Q; { no subgoal of Q0 can be removed and obtain an equivalent query; and { no subset of subgoals of Q0 can be replaced by a view in V and obtain an equivalent query.
A rewriting is total if its subgoals contain only views and comparison predicates; otherwise, if its subgoals also contain relation names, it is partial. We illustrate the trade-o s between di erent rewritings in terms of the citations generated through an example.
Example 2. Let us consider a query which nds the name and text of the introduction of families with type \gpcr".
Q(N; T x) : F amily(F; N; T y); F amilyIntro(F; T x); T y = \gpcr"
Q1(N; T x) : V 1(F; N; T y); V 2(F; T x); T y = \gpcr" Q2(N; T x) : V 3(F; N; T y); V 2(F; T x); T y = \gpcr"
These two rewritings are total and the di erence between Q1 and Q2 is that the former uses V1, while the latter uses V3; CV 1 produces a citation for each distinct family, whereas CV 3 provides a single citation for the entire view. In this sense, V 3 is more general than V 1. In neither case is the comparison predicate T y = \gpcr" matched by the lambda term of the view.
As we have seen, a single query may be rewritten in multiple ways and each
rewriting may use one or more views. The question is how the citation for the
query result should be de ned as a function of these rewritings. To do this,
observe that citations and provenance are both forms of annotation that are
manipulated through queries [
In provenance semirings, provenance tokens (base annotations) are associated with each tuple in a relational instance (EDB). Restricting our attention to SPJU queries, there are two ways in which tuples are combined through queries: { Joint use, as in a join which combines two tuples to form a new tuple. In this case, the provenance annotation of the new tuple is the ` ' of the annotations of the two input tuples. { Alternate use, as when one or more tuples are \identi ed" via unions or projections to form a new tuple. In this case, the provenance annotation of the new tuple is the `+' of the annotations of all input tuples.
In citations, annotations are de ned through the citation queries (and their corresponding functions). Citation views are combined in two di erent ways when providing a citation to general queries: they may appear jointly in equivalent rewritings of the query, or they may appear in alternate rewritings.
In the following, we will assign query output with citations that are the combination of results of citation functions, through + and based on the use of the views in the query. The resulting structure of citations is that of a commutative semiring: we start with a set of basic citations C, and introduce an abstract operation + on it with the properties that + is commutative, associative, and has some neutral element 0 in C. Similarly we introduce an operation with the same properties, but with a di erent neutral element 1. Last, we impose that is distributive over +.
We start by de ning a citation for a single binding of a single rewriting of the query. This dictates a single output tuple, and a particular valuation to the parameters of the views. We de ne the citation of the output tuples as the joint use of citations for the views and the parameter valuations, denoted by \ ". De nition 3. Let Q be a query, let V be a set of citation views and let Q0 be a (partial) rewriting of Q using V 1; :::; V n 2 V . Further let B be a binding to the variables of Q0, yielding an output tuple t. The citation for t w.r.t. Q; Q0; V; B, denoted as cite(t; Q; Q0; V; B), is de ned as FV 1(CV 1(B1)) . . . FV n(CV n(Bn)) where Bi is the application of B to the variables occurring in an atom involving V i in Q0.
Example 3. Consider the rewriting Q1 from Example 2, and consider the binding to its variables F=\11", N=\Calcitonin", Ty = \gpcr" and Tx=\stu ". The resulting tuple is (\Calcitonin", "stu "), and the citation we get for this particular binding is the citation assigned in V 1 to family \11" (note that the lambda parameter of V 1 is F ), combined via with the one assigned in V 2 to the same family (i.e., FV 1 FV 2): fID: \11", Name: \Calcitonin", Committee: [\Hay", \Poyner"]g fID: \11", Name: \Calcitonin", Text: \The calcitonin peptide family ", Contributors: [\Brown", \Smith"]g.
So far we have only de ned the citation for a single binding. Multiple bindings lead to multiple alternative citations, which we capture using +. De nition 4. Let Q; V; Q0 be as in De nition 3, and let t be the set of all bindings for Q0 that yield a tuple t. The citation for t w.r.t. Q; Q0 (denoted as cite(t; Q; Q0; V )) is denoted as B2 t cite(t; Q; Q0; V; B).
Example 4. Recall Q1 and assume now that the family name N=\Calcitonin" is shared by two families, with identi ers 11 and 12. This leads to two bindings to the variables of Q1, and intuitively to two ways of using the views to get the output tuple (\Calcitonin"). The citation for the tuple, in this case, will be a \+" over the expression in Example 3 and a similar expression for family id 12: fID: \11", Name: \Calcitonin", Committee: [\Hay", \Poyner"]g fID: \11", Name: \Calcitonin", Text: \The calcitonin peptide family", Contributors: [\Brown", \Smith"]g + fID: \12", Name: \Calcitonin", Text: \The calcitonin peptide family", Contributors: [\Brown", \Hey"]g
For example, \ " could be a join of some sort and \+" could be union.
Finally, a query may have multiple rewritings, each leading to a possibly di erent citation. These are again alternatives, but the function used to combine the citations for them may be di erent than the one used for multiple bindings for a single rewriting. We therefore use +R (\+ for rewritings") to denote this function, whose operands are elements of the citation semiring (i.e. polynomials using + and ). +R has a neutral value 0R, and is associative and commutative. Note that this is a formal semantics, not a means of computation: going through all rewritings would be an impractical implementation.
There are many interpretations \ " , \+", and +R that could be used. For \ " and \+", union or join are natural interpretations. For +R, the \minimum" in some ordering would also be natural. These ordering could re ect how \precise" or \comprehensive" the rewritings are relative to each other, or the \size" of the resulting citation. 5
We presented an approach for automatically constructing citations to information extracted from a database via general queries. In this approach, owners of the database specify citations to a small set of (possibly parameterized) views of the database which represent typical usage patterns; they also give interpretations to the combining functions + , and +R. A query against the database is then rewritten using the views, and a citation for the result set constructed using the interpretations of the combining functions.
The described model can be used for constructing citations using only schema level information (as is done in query optimization using views) as well as using citation annotations attached to tuples (as is done with reasoning about provenance). Note that reasoning at the tuple level requires changes to an existing database both in terms of the schema (to capture citation annotations on view tuples) and in terms of query processing (to combine citation annotations).
While we have formally de ned a model for citations for query results, we have not given e cient means for computing them. In particular, it is infeasible both in terms of run time and the size of the resulting citation to go through all rewritings and all assignments within each of them. A precursor for algorithms in this respect is further modeling of (some of) the \black boxes" of the model, which include the citation functions and the semiring operations. We have demonstrated initial ideas in this respect, such as the assumption of idempotence over + and its use in some cases. Even for restricted cases, designing e cient algorithms for computing citations is a non-trivial task. To this end, our future work will also study further connections to relevant classic problems in the literature such as query inclusion (which we have mentioned as useful for the preference relation); query rewriting using views; using logs to understand database usage and decide what citation views should be speci ed; caching and materialization; and the maintenance and presentation of data provenance. Acknowledgments The authors would like to thank Peter Buneman and Val Tannen for many fruitful discussions. Peter Buneman initially formulated several of these ideas in the context of XML. This work has been partially funded by NSF IIS 1302212, NSF ACI 1547360, and NIH 3-U01-EB-020954-02S1; by the ERC under the FP7, ERC grant MoDaS, agreement 291071; by the ISF (1636/13); and by a grant from the Blavatnik Interdisciplinary Cyber Research Center.