As the problems of interest in large-scale science are ever more complex or intertwined, scientists can bene t from machinery to manage hypotheses and their interconnection in the context of a large-scale research project. A partial order is assumed to model hypothesis interconnectivity, meaning that hypotheses may be `based on or equal to' one another. Then we investigate lattices as a mathematical abstraction for representing and managing hypothesis-driven research. We present queries designed to exploit lattice-theoretic topological features of a hypothesis-driven research and then discuss their complexity.
Large-scale science relies on data management technology in order to deal with the increasing
amount of observational and experimentally-produced data. As the problems of interest are ever
more complex or intertwined, scientists can also bene t from machinery to manage hypotheses
in the context of a large-scale research project. Hypotheses appear interconnected in a research,
playing roles of assumption or proposition to explain phenomena [
Problem Statement. Representation and management of scienti c hypotheses within the context of a large-scale research project.
We address this problem by considering that hypothesis interconnectivity is order-theoretic in
nature. We write h h , read hypothesis h `is based on or equal to' hypothesis h . We aim
at enabling a scientist end-user to query topological features of a research, such as hypothesis
connectivity, paths and neighborhoods. There are, nonetheless, some special topological features
that seem to be of particular interest in a hypothesis-driven research: given any two hypotheses
in a research, (i) what is their in mum hypothesis (\weakest stronger claim"), and (ii) what is
their supremum hypothesis (\strongest weaker claim"). Both are warranted to exist for all h ; h
in a partially-ordered set R, if R is a lattice [
Section 2 introduces notation and concepts from Lattice Theory (Order) for normalization and
easy reference. Section 3 introduces the (hypothesis-driven) research lattice abstraction. Section
4 considers querying features on a research lattice. Section 5 brie y discusses related work on
hypothesis data modeling. Section 6 concludes the paper.
a
a
a
a
b and b
a implies that a = b
c implies that a
(antisymmetry)
A partially ordered set, or poset hA; ri, A for short, consists of a non-empty set A and a binary
relation r on A, such that r satis es properties (P1){(P3). Note that a b means b a, i.e.,
has an inverse; and that < is de ned by :(P1) and (P3). If A is a poset, a, b 2 A, then a and b
are comparable if a b or b a. Otherwise, a and b are incomparable, in notation, a k b. A zero of
a poset P is an element 0 with 0 x for all x 2 P . A unit, 1, satis es x 1 for all x 2 P . There
are at most one zero and at most one unit in a poset. A bounded poset is one that has both 0 and
1. A poset P can be represented by a list of the pairs of elements satisfying the partial order. It
can also be represented by means of the covering relation: a is covered by b, in notation, a b, if
a < b and for no x, a < x < b. This relation is enough to determine a nite poset [
Given two hypotheses h ; h 2 R, we shall write: h h (h `is based on or equal to' h ); h < h (h `is based on' h ); h h (h `is directly based on' h ); and h k h (h `is incomparable to' h ).
Let H P , a 2 P , for an arbitrary poset hP ; i. Then a is an upper bound of H, if h a for all h 2 H. An upper bound a of H is the least upper bound of H or supremum of H if, for any upper bound b of H, we have a b. It is written a = sup H, and the uniqueness of the supremum can be shown straightforwardly.2 The concepts of lower bound and greatest lower bound or in mum are similarly de ned. The latter is denoted by inf H, and uniqueness of the in mum is veri ed likewise. The set of upper (lower) bounds of an element h is denoted " h (# h).
Def. 1. A poset L is a lattice if supfa; bg and inffa; bg exist for all a; b 2 L.
We can refer to lattices as algebraic structures by the notation:
a _ b
a ^ b
supfa; bg
inffa; bg
read _ the join, and ^ the meet. In lattices, these are binary operations, i.e., they can be applied
to any pair of elements a; b 2 L to yield again an element of L. For all a, b 2 L, these operations
satisfy idempotency, commutativity, associativity and absorption. Lattice Theory has singled out
a special kind of posets for detailed investigation. It is a vast mathematical theory with plenty of
interesting results. In Theoretical Computer Science, for instance, lattices are used in the study of
semantic properties of programs (e.g., con uence, termination) [
The inf{sup existence property of lattices as special posets may translate into neat properties of a hypothesis-driven research as a scienti c theory. 3
We characterize a hypothesis-driven research as a poset, further constrained to be a lattice. Def. 2. Let H be a set of hypotheses. The top, >, is a special hypothesis such that h >, for all h 2 H. The bottom, ?, is another special hypothesis, dual of >, such that ? h, for all h 2 H. Def. 3. A hypothesis-driven research poset R is a nite, bounded poset, whose elements are hypotheses, > 2 R is unit, and partial order reads `is based on or equal to.'3 Def. 4. Let R be a research poset. We say that R is lifted, written R?, if ? 2 R. Then ? is zero of R?. 1 http://en.wikipedia.org/wiki/Hasse_diagram. 2 In fact, if a0 and a1 are both suprema of H, then a0 a1, since a1 is an upper bound, and a0 is a supremum. Similarly, a1 a0, since a0 is an upper bound, and a1 is a supremum. Thus, by (P2), a0 = a1. 3 N.B.: since R is a nite poset, we can infer the set of partial order pairs from the set of covering pairs . At a logical level, we shall refer to both somewhat interchangeably. At the user level, only is seen. The top hypothesis, >, serves as a root element under which a research poset is built. It assumes nothing, leaving everything open for consideration. The bottom hypothesis, ?, is meant to indicate that the research is yet un nished, either because it is simply ongoing (without a nal hypothesis), or because there are two or more incomparable hypotheses that can be considered to be competing.
If there exists a hypothesis h 6= ? that is directly based on two others, i.e., h h and
h h , then it is intuitive to say that h and h are con uent to h as trains of thought.
As a stronger notion, consider a mental operation in which a scientist practitioner takes two (or
more) hypotheses h and h as input and (non-deterministically) generates another hypothesis
h as output. Def. 5 gives a precise meaning for that conceptual operation, which is founded in
Conceptual Blending [
Def. 5. Let R be a research poset, and let S h 2 R is a blend of S, written h C S, if h
R such that jSj > 1 and x k y for all x; y 2 S. Then s for all s 2 S and h s0 implies s0 2 S.
Examples of research posets are presented in Fig. 1. They have been derived from
authoritative sources, i.e., taken from their (historical) research context and organized according to our
conceptual framework|see Appendix B; note, in contrast to Fig. 1, that hypotheses lack their
inherent interconnectivity when presented in tabular form. Those research posets are all lattices.
Nonetheless, we need to investigate research posets in general w.r.t. the inf{sup existence property.
In a poset R, the greatest lower bound inf fx; yg of whatever pair fx; yg R may fail to exist for
two di erent reasons [
Lemma 1. Let R be a research poset. Then fx; yg` 6= ? and fx; ygu 6= ? for all x; y 2 R. Proof. By Def. 3, R is bounded. Then it has both 0 and 1. Since it has 0, and 0 x for all x 2 R, we have 0 2 fx; yg`. Thus fx; yg` 6= ?. Similarly, since it has 1 and x 1 for all x 2 R, we have 1 2 fx; ygu. Thus fx; ygu 6= ?.
By Lemma 1, we know that condition (i) above is avoided. We still need to ensure that condition (ii) is avoided as well. For that, we shall constrain our application of Conceptual Blending speci cally for scienti c thinking (Axiom 1). This axiom can be interpreted as a parsimony principle. Axiom 1. Let R be a research poset, and let h C S such that fx; yg Then there can be no h0 6= h in R such that h0 C S0 and fx; yg S0.
S, for h 2 R and S
Theorem 1. Let R = hR; i be a research poset, initialized := f(?; >)g, and let it be freely manipulated by Algorithms 1, 2 or 3 (cf. Appendix A) to derive an arbitrary poset R0. We claim that R0 is a lattice.
Proof. The proof is given in Appendix A. 4
We can treat querying features related to inf fa; bg and supfa; bg from an algebraic perspective through the operators meet and join (cf. Section 2). They are among the main querying capabilities we have in mind in view of a scientist end-user thinking over his/her research lattice. Let us consider some query examples (see Fig. 1). (Q1). Given (h2) Polynucletide structure and (h3) DNA storage of genetic information, nd their join (\strongest weaker claim"): f h 2 R j h = h2 _ h3 g. [ h1 ]. (Q2). Given (h2) Intra-species competition and (h5) Predator-prey coupling, nd their meet (\weakest stronger claim"): f h 2 R j h = h2 ^ h5 g. [ ? ]. (Q3). Given (h3) Logistic growth and (h5) Predator-prey coupling, nd the disjoint union of their complementary upper bounds: ( " h3 n " h5) S ( " h5 n " h3).
[ f(h3; 1); (h2; 1); (h5; 2); (h4; 2)g ]. (h1) F alling bodies
(h2) Elliptical orbits (h3) Gravitation
| is directly based on (upwards)
(h2) Intra-species competition
(h1) Intrinsic reaction
(h4)
T rophic interactions (h3) Logistic growth
(h5) Predator-prey
coupling > ?
(h2) Polynucleotide structure
(h3)
DNA storage of genetic information > (h1) Nucleic acid molecule
(h4) Charga 's rule (h5)
DNA double helix These queries illustrate a potential interest (Q1) in the strongest claim once dropping h2 and h3; or (Q2) in the weakest claim once assuming h2 and h5; or (Q3) in clustering sets of competing hypotheses (one set competing with the other) for inspection. Retrieving the up-set " h of a hypothesis (re exive transitive closure of ) in a research lattice can also be relevant. For brevity, we are presenting small examples, but the research lattice abstraction is meant to be used in large-scale science. Furthermore, we can think of research lattices being further merged on the web (merge as an additional operation), such that large lattices are to be formed.
The complexity of queries related to the meet and join operators (Q1-Q2) or to computing
re exive transitive closures (Q3) is a ordable. E cient methods for the two lattice operations
that also involve computing the closures are available in the literature [
Most of the current work on hypothesis modeling is found embodied in the RDF data model.4
We point out the initiatives on the Robot Scientist [
This work can be complementary to initiatives on the (semi-)automatic retrieval of hypotheses (or claims) from the narrative structure of scienti c documents. Primarily, we aim at providing scientists with a data management framework to operate their large-scale hypothesis-driven research. 4 http://www.w3.org/TR/rdf-primer/#rdfmodel.
In this paper we introduced a lattice-theoretic approach for managing hypothesis-driven research. To our knowledge, this is the rst study on scienti c hypotheses from a data management point of view. In this approach, scientists themselves are enabled with operations to insert/delete hypotheses into/from their research lattices and query them further. This research vision can be made into useful data management technology for hypothesis-driven large-scale science.
Proof. The proof roadmap is as follows. We refer to the insertion and deletion operations to accomplish it
by induction. So, consider research poset R? = hR; i, with = f(?; >)g, as given. We have inff>; ?g = ?
and supf>; ?g = >, therefore R? is a lattice. Now, assume by the induction hypothesis that R of size
jRj = k elements, k 2, is a lattice, either lifted or not.5 We must show that R0 := insert(R; h; ?), of size
jR0j = k + 1, is also a lattice, either after simple insertion, ? = s, or blending insertion, ? = S of a new
element h. Furthermore, suppose the insertion operations have been shown to preserve the property such
that R can be arbitrarily large, say jRj = M . Then, by reverse induction, assume that R of size jRj = k
elements, 2 < k M , is a lattice, either lifted or not. We must show that R0 := delete(R; h), of size
jR0j = k 1 is a lattice idem. Before we proceed with the induction argument for each operation, it is
worth highlighting some general features of posets. If a b, then inffa; bg = a and supfa; bg = b; hence,
to show that a poset is a lattice, it su ces to check the incomparable pairs, i.e., fa; bg such that a k b
[
Simple insertion (Algorithm 1). New element h s is connected to its one cover s 2 R. Then, if s = R(0), we have h = R0(0). Thus inffh; xg = h and supfh; xg = x for all x 2 R0. Otherwise, we should ensure that R0 is bounded (cf. Def. 3). If R was already R?, then just connect ? to h making ? h in R0?. Else, lift R0 to connect ? to both h and R(0). In any case, then, we have inffh; sg = h and supfh; sg = s, and inff?; hg = ? and supf?; hg = h. Now, it remains to check all pairs fh; xg such that x 2 R0 and h k x. Note, however, that # h = fh; ?g and ? x for all x 2 R0. Thus fh; xg` = f?g, i.e., inffh; xg = ?. 5 As a special element, ? is not counted for the purpose of the induction step, i.e., its insertion into R (\lifting") or its removal from R (\unlifting") is automated and not seen. Besides, note that x; s 2 R and R is a lattice by the induction hypothesis, therefore supfs; xg must be well de ned in R for all x 2 R. Since fs; xgu R does not change in R0 with the insertion of h, then supfs; xg is well de ned in R0 for all x 2 R0 idem. Finally, since h s for exactly one s 2 R0, then supfh; xg exists and is the same as supfs; xg.
Blending insertion (Algorithm 2). New element h C S is connected to its many covers s 2 S. For blending insertion, it is required that R is already lifted R?. If h is replacing ? as R0(0), then there is nothing to verify because R is a lattice by hypothesis and the connections h s in R0 just replace ? s in R for all s 2 S (the blending leads to an order-isomorphism ' : R ! R0). Otherwise, connect ? to h, and disconnect ? from all p S such that ? p in R. Then, for all pairs fx; yg S, we have supfx; yg in R0 the same as in R (which, by the induction hypothesis, are well de ned), and inf fx; yg = h. Finally, for all pairs fh; zg such that z 2 R0 and h k z, we have inffh; zg = ?. By the induction hypothesis, we know that supfx; zg is well de ned for all x 2 S R. Therefore supfh; zg must exist for each z such that z k h and coincide to supfx; zg for some x 2 S.
Deletion (Algorithm 3). If element h 2 R, such that h 6= > and h 6= ?, is R(0), then just lift R to R0? replacing h by ? in R0 and there is nothing to verify. Else, it has associated non-empty sets Q0 = fq0 2 R j q0 hg, and P 0 = fp0 2 R j h p0g. Consider, further, subsets Q Q0 such that Q = fq 2 R j q h and q x implies x = hg, and P P 0 such that P = fp 2 R j h p and x p implies x = hg. Then we can verify that R0 is a lattice by means of a twofold analysis, rst based on Q and P , and then broadened to their supersets Q0 and P 0. If jQj = 1 and jP j 1, connect the element q 2 Q to all p 2 P and then remove h from R0. When jP j > 1, we have inffx; yg = q for all x; y 2 P R0. Now, consider the superset P 0 of P . For all w 2 P 0 n P , (by construction) there exists some z 2 R such that z 6= h and z w. Take any p 2 P , and note that in R we had inffp; wg = h. Moreover, by the induction hypothesis, inffq; zg = ` for some ` 2 R (which has not been a ected by the deletion of h). Now, in R0, inffp; wg is the same as inffq; zg and, therefore, exists. For q 2 Q, the analysis of supfq; rg for all r 2 Q0 n Q is similar to what we just have seen for the elements of P and P 0. Besides, if jQj > 1 and jP j = 1, connect all q 2 Q to the only element p 2 P and then remove h from R0. That is the dual problem, thus the reasoning for the inf{sup existence is analogous. Otherwise, the logic follows idem. If jQj > 0 then connect all q 2 Q to >; if jP j > 0 then connect all p 2 P to ? (lifting R to R0? in case ? 2= R). Remove h from R0. It is straightforward to verify in R0 that, if jP j 2, then inffx; yg = ? for all x; y 2 P ; and if jQj 2, then supfx; yg = > for all x; y 2 Q. . returns: poset . holds zero of R . connects h to s . h is new zero of R . R is already lifted R? . disconnects ? . lifts R to R? 12: 9: 12: Algorithm 1 Simple insertion on R = hR; i.6
procedure insert(R : poset, h : element, s : element) Require: h 2= R, h 6= ?, and s 2 R, s 6= ? Ensure: If R given is a lattice, then R returned after the insertion of h is idem
R R [ fhg 3: zero R(0)
R R [ f(h; s)g if zero = s then 6: return R
else if ? 2 R then 9: iRf (?; sR)2 R[ f(t?h;ehn)g
R R n f(?; s)g else
R
R return R
R [ f?g
R [ f(?; h); (?; zero)g Algorithm 2 Blending insertion on R = hR; i.
procedure insert(R : poset, h : element, S : set) Require: h 2= R, ? 2 R, and S R is parsimonious (cf. Axiom 1) Ensure: If R given is a lattice, then R returned after the insertion of h is idem
R R [ fhg 3: if ? C S then
for all s 2 S do 6: RR RR n[f(f?(h; ;ss)g)g
R n f?g
R return R
R else for all s 2 S do
R R [ f(h; s)g if (?; s) 2 R then
R R n f(?; s)g
R [ f(?; h)g 6 By a slight abuse of notation, we write R instead of to refer to the set of covering pairs of R = hR; i. 9: 12: 15: 18: 21: 24: 27: 30: ID Author h1 Malthus h2 Verhulst h3 Verhulst h4 Lotka,
Volterra h5 Lotka,
Volterra ID Author h1 Miescher h2 Levene h3 Avery et al.
Algorithm 3 Deletion on R = hR; i.
procedure delete(R : poset, h : element) Require: h 6= > and h 6= ? Ensure: If R given is a lattice, then R returned after the deletion of h is idem
if h = R(0) then 3: R R [ f?g
S fs 2 R j h sg for all s 2 S do 6: R R [ f(?; s)g
R R n f(h; s)g else
C fc 2 R j c Q fq 2 C j q P fp 2 C j h if jQj = 1 and jP j for all p 2 P do [ f(q; p)g h or h h and q p and x 1 then
R R else if jQj > 1 and jP j = 1 then for all q 2 Q do
R R [ f(q; p)g else for all q 2 Q do
R R [ f(q; >)g if ? 2= R and jP j > 0 then
R R [ f?g for all p 2 P do
[ f(?; p)g
R R for all c 2 C do if c h then
R R n f(c; h)g n f(h; c)g else
R
R R R n fhg return R x implies x = hg p implies x = hg . returns: poset . lifts R to R? . disconnects h . lifts R to R?
\The velocities of a freely falling body are proportional to the times." \Each planet moves in an ellipse with the sun in one focus." \The gravitational force exerted by the sun on each planet is proportional to its mass and inversely proportional to the square of its distance to the sun."
Intra-species competition \Population growth is limited by competition for resources among individuals of the same species." Name Intrinsic reaction Logistic growth Trophic interactions Predator-prey coupling
Statement \Population changes by intrinsic reaction measured as natality and mortality rates." \Population grows by intrinsic reaction, but limited by competition." \Population growth/decay is limited by inter-species trophic interactions." \Population grows/decays by intrinsic reaction and is regulated by predator-prey interactions." \The nucleic acid molecule is a new substance that is in some sense equivalent to a protein." Polynucleotide structure \Nucleic acids are composed of a series of nucleotides, with each nucleotide composed of just one of four nitrogen-containing bases, a sugar molecule, and a phosphate group." DNA storage of genetic \DNA is the exclusive chromosomal component bearing the genetic information information of living cells." h4 Charga et al.
Charga 's rule \The total amount of purines and the total amount of pyrimidines are nearly equal." h5 Watson, Crick
DNA double helix \DNA has a three-dimensional double-helical structure."