Please refer to the errata for this document, which may include some normative corrections.
A color-coded version of this document showing changes made since the previous version is also available.
This document is also available in these non-normative formats: PDF version.
See also translations.
Copyright © 2013 W3C® (MIT, ERCIM, Keio, Beihang), All Rights Reserved. W3C liability, trademark and document use rules apply.
This document, developed by the Rule Interchange Format (RIF) Working Group, specifies RIF-Core, a common subset of RIF-BLD and RIF-PRD based on RIF-DTB 1.0. The RIF-Core presentation syntax and semantics are specified by restriction in two different ways. First, RIF-Core is specified by restricting the syntax and semantics of RIF-BLD, and second, by restricting RIF-PRD. The XML serialization syntax of RIF-Core is specified by a mapping from the presentation syntax. A normative XML schema is also provided.
This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.
This document is being published as one of a set of 13 documents:
There have been no changes to the body of this document since the previous version. For details on earlier changes, see the change log.
Please send any comments to<EMAIL_ADDRESS>(public archive). Although work on this document by the Rule Interchange Format (RIF) Working Group is complete, comments may be addressed in the errata or in future revisions. Open discussion among developers is welcome at<EMAIL_ADDRESS>(public archive).
This document has been reviewed by W3C Members, by software developers, and by other W3C groups and interested parties, and is endorsed by the Director as a W3C Recommendation. It is a stable document and may be used as reference material or cited from another document. W3C's role in making the Recommendation is to draw attention to the specification and to promote its widespread deployment. This enhances the functionality and interoperability of the Web.
This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent.
This specification describes RIF-Core (the Core dialect of the Rule Interchange Format). From a theoretical perspective, RIF-Core corresponds to the language of definite Horn rules without function symbols (often called 'Datalog') with a standard first-order semantics. RIF-Core thus is a subset of RIF-BLD [RIF-BLD]. At the same time, RIF-Core is a language of production rules where conclusions are interpreted as assert actions. RIF-Core thus also is a subset of RIF-PRD [RIF-PRD]. Moreover, RIF-Core is based on built-in functions and predicates over selected XML Schema datatypes, as specified in RIF-DTB 1.0 [RIF-DTB]. The common subset of RIF-BLD and RIF-PRD is specified based on RIF-DTB 1.0.
Syntactically, RIF-Core has a number of Datalog extensions to support features such as objects and frames as in F-logic [KLW95], internationalized resource identifiers (or IRIs, defined by [RFC-3987]) as identifiers for concepts, and XML Schema datatypes [XML-SCHEMA2]. In addition, RIF RDF and OWL Compatibility [RIF-RDF+OWL] defines the syntax and semantics of integrated RIF-Core/RDF and RIF-Core/OWL languages. These features make RIF-Core a Web-aware language. However, it should be kept in mind that RIF is designed to enable interoperability among rule languages in general, and its uses are not limited to the Web.
RIF-Core is defined as a specialization of RIF-BLD (hence of [RIF-FLD], making it a starting point of the RIF extensibility framework). It is a syntactic subset of RIF-BLD, so that a well-formed RIF-Core formula (including document and condition formulas) is also a well-formed RIF-BLD formula.
RIF-Core is also a syntactic subset of [RIF-PRD]. It is intended that a RIF-PRD consumer can treat a RIF-Core document as if it was a RIF-PRD rule set while it also conforms to the normative RIF-Core first order semantics. However, due to the presence of builtin functions and predicates there are rule sets in the syntactic intersection of RIF-PRD and RIF-BLD which would not terminate under RIF-PRD semantics. We therefore define a notion of safe RIF-Core rules, which is a subset of RIF-Core rules that can be executed using a forward chaining strategy, and we define conformance in terms of such safe rules. These notions of safeness and conformance are defined formally in section 5 Conformance and Safeness.
RIF-Core is not the maximal common subset of RIF-BLD and RIF-PRD. It omits some features from the intersection which do not significantly add to the expressiveness of the language and are judged to be not widely supported by rule languages.
To give a preview, here is a simple complete RIF-Core example deriving a ternary relation from its inverse.
Example 1 (An introductory RIF-Core example).
A rule can be written in English to derive buy relationships from the sell relationships that are stored as facts (e.g., as exemplified by the English statements below):
The fact Mary buys LeRif from John can be logically derived by a modus ponens argument. Assuming Web IRIs for the predicates buy and sell, as well as for the individuals John, Mary, and LeRif, the above English phrase can be represented in RIF-Core Presentation Syntax as follows.
Document( Prefix(cpt <http://example.com/concepts#>) Prefix(ppl <http://example.com/people#>) Prefix(bks <http://example.com/books#>) Group ( Forall ?Buyer ?Item ?Seller ( cpt:buy(?Buyer ?Item ?Seller) :- cpt:sell(?Seller ?Item ?Buyer) ) cpt:sell(ppl:John bks:LeRif ppl:Mary) ) )
For the interchange of documents containing such rules (and facts), an equivalent RIF-Core XML syntax is provided in this specification. To formalize their meaning, a RIF-Core Semantics is specified.
This document assumes familiarity with [RIF-BLD] or [RIF-PRD], as RIF-Core is derived from these documents via syntactic restrictions.
Like RIF-BLD and RIF-PRD, RIF-Core has both a presentation syntax and an XML syntax. It is defined in "mathematical English," a special form of English for communicating mathematical definitions, examples, etc. and by an EBNF syntax. The mathematical English is normative, the EBNF is not normative; both instances of the presentation syntax are not intended to be a concrete syntax for RIF-Core. The English presentation syntax deliberately leaves out details such as the delimiters of the various syntactic components, escape symbols, parenthesizing, precedence of operators, and the like. Since RIF is an interchange format, it uses XML, and only XML, as its concrete syntax. RIF-Core conformance is described in terms of semantics-preserving mappings.
Since RIF-Core is a syntactic subset of RIF-BLD, this section defines the presentation syntax of RIF-Core as a restriction on the presentation syntax of RIF-BLD.
The alphabet of the presentation language of RIF-Core is the alphabet of the RIF-BLD presentation language with the exclusion of the symbol ## (subclass) and the set of symbols ArgNames (used for named-argument uniterms).
The Terms of RIF-Core are the terms of RIF-BLD with the exclusion of subclass terms and of terms with named arguments. In RIF-Core there are only closed ground lists.
Definition (List Term)
A closed list of the form List() (i.e., a list in which m=0) is called the empty list.
The Formulas of RIF-Core are the formulas of RIF-BLD with the following restrictions.
RIF-Core allows every term and formula to be optionally annotated in the same way as in RIF-BLD. The frame formulas that are allowed as part of an annotation must be syntactically correct for RIF-Core. In particular, no function symbols are allowed in such a formula.
A syntactically correct RIF-Core formula that passes the well-formedness test for RIF-BLD is also a well-formed RIF-Core formula.
Recall that RIF-Core does not allow uninterpreted (i.e., non-external) function symbols. Therefore no symbol in RIF-Core can occur in the context of an (uninterpreted) function symbol.
Until now, we have used mathematical English to specify the syntax of RIF-Core as a restriction on RIF-BLD. Tool developers, however, may prefer EBNF notation, which provides a more succinct view of the syntax. However, EBNF is unable to express all of the well-formedness conditions. For instance, the requirement that each symbol appear in only one context cannot be expressed in EBNF. As a result, the EBNF grammar defines a strict superset of RIF-Core. For that reason this section is not normative.
The EBNF for the RIF-Core presentation syntax is given as follows. For convenience of reading we show the entire EBNF divided into three parts (rules, conditions, and annotations); these are derived from the ENBF for RIF-BLD by applying the restrictions described above.
Rule Language:
Document ::= IRIMETA? 'Document' '(' Base? Prefix* Import* Group? ')' Base ::= 'Base' '(' ANGLEBRACKIRI ')' Prefix ::= 'Prefix' '(' NCName ANGLEBRACKIRI ')' Import ::= IRIMETA? 'Import' '(' LOCATOR PROFILE? ')' Group ::= IRIMETA? 'Group' '(' (RULE | Group)* ')' RULE ::= (IRIMETA? 'Forall' Var+ '(' CLAUSE ')') | CLAUSE CLAUSE ::= Implies | ATOMIC Implies ::= IRIMETA? (ATOMIC | 'And' '(' ATOMIC* ')') ':-' FORMULA LOCATOR ::= ANGLEBRACKIRI PROFILE ::= ANGLEBRACKIRI
Condition Language:
FORMULA ::= IRIMETA? 'And' '(' FORMULA* ')' | IRIMETA? 'Or' '(' FORMULA* ')' | IRIMETA? 'Exists' Var+ '(' FORMULA ')' | ATOMIC | IRIMETA? Equal | IRIMETA? Member | IRIMETA? 'External' '(' Atom ')' ATOMIC ::= IRIMETA? (Atom | Frame) Atom ::= UNITERM UNITERM ::= Const '(' (TERM* ')' GROUNDUNITERM ::= Const '(' GROUNDTERM* ')' Equal ::= TERM '=' TERM Member ::= TERM '#' TERM Frame ::= TERM '[' (TERM '->' TERM)* ']' TERM ::= IRIMETA? (Const | Var | List | 'External' '(' Expr ')') GROUNDTERM ::= IRIMETA? (Const | List | 'External' '(' GROUNDUNITERM ')') Expr ::= UNITERM List ::= 'List' '(' GROUNDTERM* ')' Const ::= '"' UNICODESTRING '"^^' SYMSPACE | CONSTSHORT Var ::= '?' Name Name ::= NCName | '"' UNICODESTRING '"' SYMSPACE ::= ANGLEBRACKIRI | CURIE
Annotations:
IRIMETA ::= '(*' IRICONST? (Frame | 'And' '(' Frame* ')')? '*)'
ANGLEBRACKIRI, CURIE, CONSTSHORT, and UNICODESTRING are defined in Section Shortcuts for Constants in RIF's Presentation Syntax of [RIF-DTB].
The following subsections explain and exemplify the Condition Language, Rule Language, and Annotations parts.
The RIF-Core Condition Language represents formulas that can be used in the premises of RIF-Core rules (also called rule bodies). The EBNF grammar for a superset of the RIF-Core condition language is shown in the above conditions part.
This is a specialization of the EBNF for the RIF-BLD condition language specified in the RIF-BLD conditions part reflecting the syntax restrictions on RIF-Core described normatively in sections 2.1 through 2.5 above.
Example 3 from the RIF-BLD document, illustrates some RIF-BLD conditions. All the conditions, except for the terms with named arguments and the equalities with (non-ground) list terms, are also RIF-Core conditions.
The presentation syntax for RIF-Core rules is based on the syntax in Section EBNF for the RIF-Core Condition Language with the productions shown in the above rules part.
Again, this is a specialization of the EBNF for the RIF-BLD rule language specified in the RIF-BLD rules part reflecting the syntax restrictions on RIF-Core described normatively in sections 2.1 through 2.5 above.
Example 4 from the RIF-BLD document also illustrates a set of RIF-Core rules. In contrast, Example 7 from the RIF-BLD document shows a formula that is not in RIF-Core because it includes terms with named arguments, which are not allowed in this dialect.
The presentation syntax for RIF-Core annotations uses the production shown in the above annotations part.
This defines the specialization of the EBNF for the RIF-BLD annotation language specified through the RIF-BLD annotations part where annotation frames use the more restricted TERMs defined in the above conditions part of RIF-Core.
Example 5 from the RIF-BLD document also illustrates a RIF-Core document that contains an annotated group formula.
RIF-Core is a syntactic subset of RIF-PRD, and this section defines the presentation syntax of RIF-Core as a restriction on the presentation syntax of RIF-PRD Conditions, Actions, and Rules.
The alphabet of the presentation language of RIF-Core is the alphabet of the RIF-PRD presentation language (Conditions, Actions, and Rules) with the exclusion of the symbols ##, such that, Not, INeg, Do, Assert, Retract, Modify, Execute, and New.
The Terms of RIF-Core are the terms of RIF-PRD with the exclusion of subclass terms. In Core there are only closed ground lists.
The Formulas of RIF-Core are the formulas of RIF-PRD with the exclusion of negation formulas.
RIF-Core allows every term and formula to be optionally annotated in the same way as in RIF-PRD. The frame formulas that are allowed as part of an annotation must be syntactically correct for RIF-Core.
A syntactically correct RIF-Core formula that passes the well-formedness test for RIF-PRD is also a well-formed RIF-Core formula.
 A RIF-Core group is a RIF-PRD group without strategy and without priority.
RIF-Core is a syntactic subset of RIF-BLD, and the semantics of RIF-Core is identical to the semantics of RIF-BLD for that subset. RIF-Core is also a syntactic subset of RIF-PRD, and the semantics of RIF-Core is also identical to the semantics of RIF-PRD for that subset.
The XML syntax of RIF-Core is a subset of the XML syntax of RIF-BLD. All XML tags of RIF-BLD (except Subclass, sub and super) are supported, but the XML schema of RIF-Core restricts their context with respect to what is allowed by the XML schema of RIF-BLD. The semantics of the XML syntax for RIF-Core is defined through the same RIF-BLD XML-to-presentation syntax mapping.
XML serialization of a complete RIF-Core document appears in the RIF-BLD specification as Example 8.
RIF-Core is a syntactic subset of both RIF-BLD and RIF-PRD. The semantics of a RIF-Core formula is the same as the semantics given to it by RIF-BLD.
All RIF-Core documents are also syntactically valid RIF-PRD documents. However, some formulas may be unsafe and cannot be executed under the RIF-PRD operational semantics. Thus, in order to allow production rule systems and logic programming systems to interchange rules via RIF-Core, we restrict RIF-Core to safe rules so that the logical semantics of RIF-BLD and the operational fixed-point semantics of RIF-PRD coincide.
Intuitively, safeness of rules guarantees that, when performing reasoning in a forward-chaining manner, it is possible to find bindings for all the variables in the rule so that the condition can be evaluated.
To define safeness, we need to define, first, the notion of binding patterns for externally defined terms, as well as under what conditions variables are considered bound.
Definition (Binding pattern). Binding patterns are lists of the form (p1, ..., pn), such that pi=b or pi=u, for 1 ≤ i ≤ n: b stands for a "bound" and u stands for an "unbound" argument. ☐
Each external function or predicate has an associated list of valid binding patterns. We define here the binding patterns valid for the functions and predicates defined in [RIF-DTB].
Every function or predicate f defined in [RIF-DTB] has a valid binding pattern for each of its schemas with only the symbol b such that its length is the number of arguments in the schema. In addition,
The functions and predicates defined in [RIF-DTB] have no other valid binding patterns.
To keep the definitions concise and intuitive, boundedness and safeness are defined, below, for condition formulas in disjunctive normal form, that can be existentially quantified themselves, but that contain, otherwise, no existential sub-formula. The definitions apply to any valid RIF-Core condition formula, because they can always, in principle, be put in that form, by applying the following syntactic transforms, in sequence:
Definition (Boundedness). An external function term External(f(t1,...,tn)) is bound in a condition formula, if and only if f has a valid binding pattern (p1, ..., pn) and, for all j, 1 ≤ j ≤ n, such that pj=b, tj is bound in the formula.
A variable, v, is bound in an atomic formula, a, if and only if
A variable, v, is bound in a conjunction formula, f = And(c1...cn), n ≥ 1, if and only if, either
A variable, v, is bound in a disjunction formula, if and only if v is bound in every disjunct where it occurs;
A variable, v, is bound in an existential formula, Exists v1,...,vn (f'), n ≥ 1, if and only if v is bound in f'. ☐
Notice that the variables, v1,...,vn, that are existentially quantified in an existential formula f = Exists v1,...,vn (f'), are bound in any formula, F, that contains f as a sub-formula, if and only if they are bound in f, since they do not exist outside of f.
Definition (Safeness). A variable, v, is safe in a condition formula, f, if and only if
A RIF-Core rule, r is safe if and only if
A group, Group (s1...sn), n ≥ 0, is safe if and only if
A document is safe if and only if
Example. Consider the following formula:
Forall ?x ?y ?z ?u (ex:p(?x) :- Or( And( ex:q(?z) External(pred:iri-string(?x ?z)))) And( ?x=?y ?y=?u ex:q(?u)))
One can verify that this formula is safe, in the following way: the only variable appearing in the conclusion of the rule is ?x; ?x is safe in the first component of the disjunction, because it occurs in the atomic formula pred:iri-string(?x,?z). It is also safe in the second disjunct, because it occurs as the left term in an equality formula where the right term is ?y, which is safe because it occurs as the left term in an equality formula where the right term is ?u, which is safe because it occurs in the atomic formula ex:q(?u). Being safe in both disjuncts, ?x is safe in the disjunction.
Moreover, ?x, ?y, ?z and ?u are all bound in the body of the rule:
While safeness guarantees the possibility to do forward chaining with the rules, it does not guarantee that it is possible to construct a finite grounding. For this purpose we define strong safeness.
The conformance clauses for RIF-Core only require conformance over safe rule sets as defined above. However, some rule engines, such as some Datalog engines, are only able to process rule sets which can be finitely grounded. For maximum interoperability with such systems it is recommended that RIF-Core producers restrict themselves to strongly safe rule sets where possible.
 For the purposes of the definitions in this section we view frames a[b -> c] and membership formulas a#b, respectively, as ternary and binary predicate symbols, and so (->,3), (#,2) ∈ P. Note that equality = does not appear in P.
We define the graph of variable dependencies of a set of atomic formulas A as a labeled directed graph GR=(V, E, L), where the labeling function L maps edges to sets of external function and predicate symbols, V is the set of variables appearing in A, and E is the smallest set and L' is the smallest function such that for every variable ?V
Finally, L is defined as: for every (e,e') ∈ E, L((e,e')) is the union of the minimal sets in L'((e,e')).
For every rule implication, φ :- ψ, we define the collection, Bψ, of the sets of the atomic formulas in each of the conjunctions that are the components of ψ', where ψ' is ψ rewritten as a condition formula in disjunctive normal form, possibly existentially quantified itself, but otherwise containing no existential sub-formula (see description of the transform in the section Safeness, above).
The dependency graph of a set of implications R is a labelled directed graph GR=(V, E), where edges are triples (v,v',l) such that v, v' ∈ V and l is a set of external function and predicate symbols. V is defined as: for every (p,n) ∈ P and every integer i such that 1 ≤ i ≤ n, (p,n)/i ∈ V. E is the smallest set such that for every (p,n)/i ∈ V and every φ :- ψ in R such that there is an atomic subformula p(t1,...,ti,...,tn) of φ, then for every variable ?V appearing in ti:
Definition (Strong safeness). A set of rule implications R is strongly safe if its dependency graph does not contain cycles involving edges labelled with sets involving a function defined in [RIF-DTB] that is not a casting function. A RIF document D is strongly safe if the set R of rule implications that are subformulas of D is strongly safe.
RIF-Core conformance is described in terms of semantics-preserving transformations.
Let Τ be a set of datatypes and symbol spaces that includes the datatypes specified in [RIF-DTB] and the symbol spaces rif:iri and rif:local. Suppose also that Ε is a set of external predicates and functions that includes the built-ins listed in [RIF-DTB]. We say that a formula φ is a CoreΤ,Ε formula iff
A RIF processor is a conformant CoreΤ,Ε consumer iff it implements a semantics-preserving mapping from the set of all safe CoreΤ,Ε formulas to the language L of the processor.
A RIF processor is a conformant CoreΤ,Ε producer iff it implements a semantics-preserving mapping from the language L of the processor to a set of safe CoreΤ,Ε formulas.
An admissible document is an XML document that conforms to all the syntactic constraints of RIF-Core, including ones that cannot be checked by an XML Schema validator. Note that the concrete presentation syntax given in Section 2.6 is purely informative (to help implementers see the set of language structures supported by RIF-Core); the only normative concrete syntax for RIF-Core is the XML syntax.
In addition:
This document is the product of the Rules Interchange Format (RIF) Working Group (see below) whose members deserve recognition for their time and commitment. The editors extend special thanks to Jos de Bruijn for his safeness definition and to: Jos de Bruijn, Leora Morgenstern, Christian de Sainte-Marie, Stella Mitchell and Changhai Ke for their thorough reviews and insightful discussions; the working group chairs, Chris Welty and Christian de Sainte-Marie, for their invaluable technical help and inspirational leadership; and W3C staff contact Sandro Hawke, a constant source of ideas, help, and feedback.
The regular attendees at meetings of the Rule Interchange Format (RIF) Working Group at the time of the publication were:
Adrian Paschke (Freie Universitaet Berlin),
Axel Polleres (DERI),
Chris Welty (IBM),
Christian de Sainte Marie (IBM),
Dave Reynolds (HP),
Gary Hallmark (ORACLE),
Harold Boley (NRC),
Jos de Bruijn (FUB),
Leora Morgenstern (IBM),
Michael Kifer (Stony Brook),
Mike Dean (BBN),
Sandro Hawke (W3C/MIT), and
Stella Mitchell (IBM).
The namespace of RIF is "http://www.w3.org/2007/rif#".
XML schemas for the RIF-Core sublanguages are defined below and are also available at http://www.w3.org/2010/rif-schema/core/ with additional examples.
<?xml version="1.0" encoding="UTF-8"?> <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xml="http://www.w3.org/XML/1998/namespace" xmlns="http://www.w3.org/2007/rif#" targetNamespace="http://www.w3.org/2007/rif#" elementFormDefault="qualified" version="Id: CoreCond.xsd, v. 1.4, 2010-05-08, hboley/apaschke"> <xs:import namespace='http://www.w3.org/XML/1998/namespace' schemaLocation='http://www.w3.org/2001/xml.xsd'/> <xs:annotation> <xs:documentation> This is the XML schema for the Condition Language as defined by the RIF-Core dialect. The schema is based on the following EBNF for the RIF-Core Condition Language (prepared for generalization to the RIF-BLD and RIF-PRD Condition Languages): FORMULA ::= IRIMETA? 'And' '(' FORMULA* ')' | IRIMETA? 'Or' '(' FORMULA* ')' | IRIMETA? 'Exists' Var+ '(' FORMULA ')' | ATOMIC | IRIMETA? Equal | IRIMETA? Member | IRIMETA? 'External' '(' Atom ')' ATOMIC ::= IRIMETA? (Atom | Frame) Atom ::= UNITERM UNITERM ::= Const '(' (TERM* ')' GROUNDUNITERM ::= Const '(' GROUNDTERM* ')' Equal ::= TERM '=' TERM Member ::= TERM '#' TERM Frame ::= TERM '[' (TERM '->' TERM)* ']' TERM ::= IRIMETA? (Const | Var | List | 'External' '(' Expr ')') GROUNDTERM ::= IRIMETA? (Const | List | 'External' '(' GROUNDUNITERM ')') Expr ::= UNITERM List ::= 'List' '(' GROUNDTERM* ')' Const ::= '"' UNICODESTRING '"^^' SYMSPACE | CONSTSHORT Var ::= '?' Name Name ::= NCName | '"' UNICODESTRING '"' SYMSPACE ::= ANGLEBRACKIRI | CURIE IRIMETA ::= '(*' IRICONST? (Frame | 'And' '(' Frame* ')')? '*)' </xs:documentation> </xs:annotation> <xs:group name="FORMULA"> <!-- FORMULA ::= IRIMETA? 'And' '(' FORMULA* ')' | IRIMETA? 'Or' '(' FORMULA* ')' | IRIMETA? 'Exists' Var+ '(' FORMULA ')' | ATOMIC | IRIMETA? Equal | IRIMETA? Member | IRIMETA?  ATOMIC ::= IRIMETA? (Atom | Frame) --> <xs:choice> <xs:element ref="Atom"/> <xs:element ref="Frame"/> </xs:choice> </xs:group> <xs:element name="Atom"> <!-- Atom ::= UNITERM --> <xs:complexType> <xs:sequence> <xs:group ref="UNITERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="UNITERM"> <!-- UNITERM ::= Const '(' (TERM* ')' --> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="op"/> <xs:element name="args" type="args-UNITERM.type" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="GROUNDUNITERM"> <!-- sensitive to ground terms GROUNDUNITERM ::= Const '(' (GROUNDTERM* ')' --> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="op"/> <xs:element name="args" type="args-GROUNDUNITERM.type" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:element name="op"> <xs:complexType> <xs:sequence> <xs:element ref="Const"/> </xs:sequence> </xs:complexType> </xs:element> <xs:complexType name="args-UNITERM.type"> <!-- sensitive to UNITERM (TERM) context--> <xs:sequence> <xs:group ref="TERM" minOccurs="1" maxOccurs="unbounded"/> </xs:sequence> <xs:attribute name="ordered" type="xs:string" fixed="yes"/> </xs:complexType> <xs:complexType name="args-GROUNDUNITERM.type"> <!-- sensitive to GROUNDUNITERM (TERM) context--> <xs:sequence> <xs:group ref="GROUNDTERM" minOccurs="1" maxOccurs="unbounded"/> </xs:sequence> <xs:attribute name="ordered" type="xs:string" fixed="yes"/> </xs:complexType> <xs:element name="Equal"> <!-- Equal ::= TERM '=' TERM --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="left"/> <xs:element ref="right"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="left"> <xs:complexType> <xs:sequence> <xs:group ref="TERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="right"> <xs:complexType> <xs:sequence> <xs:group ref="TERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="Member"> <!-- Member ::= TERM '#' TERM --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="instance"/> <xs:element ref="class"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="instance"> <xs:complexType> <xs:sequence> <xs:group ref="TERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="class"> <xs:complexType> <xs:sequence> <xs:group ref="TERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="Frame"> <!-- Frame ::= TERM '[' (TERM '->' TERM)* ']' --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="object"/> <xs:element name="slot" type="slot-Frame.type" minOccurs="0" maxOccurs="unbounded"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="object"> <xs:complexType> <xs:sequence> <xs:group ref="TERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:complexType name="slot-Frame.type"> <!-- sensitive to Frame (TERM) context--> <xs:sequence> <xs:group ref="TERM"/> <xs:group ref="TERM"/> </xs:sequence> <xs:attribute name="ordered" type="xs:string" fixed="yes"/> </xs:complexType> <xs:group name="TERM"> <!-- TERM ::= IRIMETA? (Const | Var | List | 'External' '(' Expr ')') --> <xs:choice> <xs:element ref="Const"/> <xs:element ref="Var"/> <xs:element ref="List"/> <xs:element name="External" type="External-TERM.type"/> </xs:choice> </xs:group> <xs:group name="GROUNDTERM"> <!-- GROUNDTERM ::= IRIMETA? (Const | List | 'External' '(' GROUNDUNITERM ')') --> <xs:choice> <xs:element ref="Const"/> <xs:element ref="List"/> <xs:element name="External" type="External-GROUNDUNITERM.type"/> </xs:choice> </xs:group> <xs:element name="List"> <!-- List ::= 'List' '(' GROUNDTERM* ')' rewritten as List ::= 'List' '(' LISTELEMENTS? ')' --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:group ref="LISTELEMENTS" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="LISTELEMENTS"> <!--  Expr ::= UNITERM --> <xs:complexType> <xs:sequence> <xs:group ref="UNITERM"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="Const"> <!-- Const ::= '"' UNICODESTRING '"^^' SYMSPACE | CONSTSHORT --> <xs:complexType mixed="true"> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> </xs:sequence> <xs:attribute name="type" type="xs:anyURI" use="required"/> <xs:attribute ref="xml:lang"/> </xs:complexType> </xs:element> <xs:element name="Name" type="xs:string"> <!-- Name ::= UNICODESTRING --> </xs:element> <xs:element name="Var"> <!-- Var ::= '?' Name --> <xs:complexType mixed="true"> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="IRIMETA"> <!-- IRIMETA ::= '(*' IRICONST? (Frame | 'And' '(' Frame* ')')? '*)' --> <xs:sequence> <xs:element ref="id" minOccurs="0" maxOccurs="1"/> <xs:element ref="meta" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:element name="id"> <xs:complexType> <xs:sequence> <xs:element name="Const" type="IRICONST.type"/> <!-- type="&rif;iri" --> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="meta"> <xs:complexType> <xs:choice> <xs:element ref="Frame"/> <xs:element name="And" type="And-meta.type"/> </xs:choice> </xs:complexType> </xs:element> <xs:complexType name="And-meta.type"> <!-- sensitive to meta (Frame) context--> <xs:sequence> <xs:element name="formula" type="formula-meta.type" minOccurs="0" maxOccurs="unbounded"/> </xs:sequence> </xs:complexType> <xs:complexType name="formula-meta.type"> <!-- sensitive to meta (Frame) context--> <xs:sequence> <xs:element ref="Frame"/> </xs:sequence> </xs:complexType> <xs:complexType name="IRICONST.type" mixed="true"> <!-- sensitive to location/id context--> <xs:sequence/> <xs:attribute name="type" type="xs:anyURI" use="required" fixed="http://www.w3.org/2007/rif#iri"/> </xs:complexType> </xs:schema>
<?xml version="1.0" encoding="UTF-8"?> <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xml="http://www.w3.org/XML/1998/namespace" xmlns="http://www.w3.org/2007/rif#" targetNamespace="http://www.w3.org/2007/rif#" elementFormDefault="qualified" version="Id: CoreRule.xsd, v. 1.5, 2010-05-08, hboley/apaschke"> <xs:annotation> <xs:documentation> This is the XML schema for the Rule Language as defined by the RIF-Core dialect. The schema is based on the following EBNF for the RIF-Core Rule Language (prepared for generalization to the RIF-BLD and RIF-PRD Rule Languages): Document ::= IRIMETA? 'Document' '(' Base? Prefix* Import* Group? ')' Base ::= 'Base' '(' ANGLEBRACKIRI ')' Prefix ::= 'Prefix' '(' NCName ANGLEBRACKIRI ')' Import ::= IRIMETA? 'Import' '(' LOCATOR PROFILE? ')' Group ::= IRIMETA? 'Group' '(' (RULE | Group)* ')' RULE ::= (IRIMETA? 'Forall' Var+ '(' CLAUSE ')') | CLAUSE CLAUSE ::= Implies | ATOMIC Implies ::= IRIMETA? (ATOMIC | 'And' '(' ATOMIC* ')') ':-' FORMULA LOCATOR ::= ANGLEBRACKIRI PROFILE ::= ANGLEBRACKIRI Note that this is an extension of the syntax for the RIF-Core Condition Language (CoreCond.xsd). </xs:documentation> </xs:annotation> <!-- The Rule Language includes the Condition Language from the same directory --> <xs:include schemaLocation="CoreCond.xsd"/> <xs:element name="Document"> <!-- Document ::= IRIMETA? 'Document' '(' Base? Prefix* Import* Group? ')' --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="directive" minOccurs="0" maxOccurs="unbounded"/> <xs:element ref="payload" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="directive"> <!-- Base and Prefix represented directly in XML --> <xs:complexType> <xs:sequence> <xs:element ref="Import"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="payload"> <xs:complexType> <xs:sequence> <xs:element ref="Group"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="Import"> <!-- Import ::= IRIMETA? 'Import' '(' LOCATOR PROFILE? ')' LOCATOR ::= ANGLEBRACKIRI PROFILE ::= ANGLEBRACKIRI --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="location"/> <xs:element ref="profile" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="location" type="xs:anyURI"/> <xs:element name="profile" type="xs:anyURI"/> <xs:element name="Group"> <!-- Group ::= IRIMETA? 'Group' '(' (RULE | Group)* ')' --> <xs:complexType> <xs:sequence> <xs:group ref="Group.content"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="Group.content"> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="sentence" minOccurs="0" maxOccurs="unbounded"/> </xs:sequence> </xs:group> <xs:element name="sentence"> <xs:complexType> <xs:choice> <xs:group ref="RULE"/> <xs:element ref="Group"/> </xs:choice> </xs:complexType> </xs:element> <xs:group name="RULE"> <!-- RULE ::= (IRIMETA? 'Forall' Var+ '(' CLAUSE ')') | CLAUSE --> <xs:choice> <xs:element ref="Forall"/> <xs:group ref="CLAUSE"/> </xs:choice> </xs:group> <xs:element name="Forall"> <xs:complexType> <xs:sequence> <xs:group ref="Forall.content"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="Forall.content"> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="declare" minOccurs="1" maxOccurs="unbounded"/> <!-- different from formula in And, Or and Exists --> <xs:element name="formula"> <xs:complexType> <xs:group ref="CLAUSE"/> </xs:complexType> </xs:element> </xs:sequence> </xs:group> <xs:group name="CLAUSE"> <!-- CLAUSE ::= Implies | ATOMIC --> <xs:choice> <xs:element ref="Implies"/> <xs:group ref="ATOMIC"/> </xs:choice> </xs:group> <xs:element name="Implies"> <!-- Implies ::= IRIMETA? (ATOMIC | 'And' '(' ATOMIC* ')') ':-' FORMULA --> <xs:complexType> <xs:sequence> <xs:group ref="IRIMETA" minOccurs="0" maxOccurs="1"/> <xs:element ref="if"/> <xs:element ref="then"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="if"> <xs:complexType> <xs:sequence> <xs:group ref="FORMULA"/> </xs:sequence> </xs:complexType> </xs:element> <xs:element name="then"> <xs:complexType> <xs:sequence> <xs:group ref="then.content"/> </xs:sequence> </xs:complexType> </xs:element> <xs:group name="then.content"> <xs:choice> <xs:group ref="ATOMIC"/> <xs:element name="And" type="And-then.type"/> </xs:choice> </xs:group> <xs:complexType name="And-then.type"> <!-- sensitive to then (ATOMIC) context--> <xs:sequence> <xs:element name="formula" type="formula-then.type" minOccurs="0" maxOccurs="unbounded"/> </xs:sequence> </xs:complexType> <xs:complexType name="formula-then.type"> <!-- sensitive to then (ATOMIC) context--> <xs:sequence> <xs:group ref="ATOMIC"/> </xs:sequence> </xs:complexType> </xs:schema>
The anticipated RIF media type is "application/rif+xml". The registration for this media type (pending IETF discussion and approval by the IESG) follows.
Type name: application Subtype name: rif+xml Required parameters: none Optional parameters: charset, as per RFC 3023 (XML Media Types) Encoding considerations: same as RFC 3023 (XML Media Types) Security considerations: Systems which consume RIF documents are potentially vulnerable to attack by malicious producers of RIF documents. The vulnerabilities and forms of attack are similar to those of other Web-based formats with programming or scripting capabilities, such as HTML with embedded Javascript. Excessive Resource Use / Denial of Service Attacks Complete processing of a RIF document, even a conformant RIF Core document, may require arbitrarily great CPU and memory resources. Through the use of "import", processing may also require arbitrary URI dereferencing, which may consume all available network resources on the consuming system or other systems. RIF consuming systems SHOULD implement reasonable defenses against these attacks. Exploiting Implementation Flaws RIF is a relatively complex format, and rule engines can be extremely sophisticated, so it is likely that some RIF consuming systems will have bugs which allow specially constructed RIF documents to perform inappropriate operations. We urge RIF implementors to make systems which carefully anticipate and handle all possible inputs, including those which present syntactic or semantic errors. External (Application) Functions Because RIF may be extended with local, application defined datatypes and functions, new vulnerabilities may be introduced. Before being installed on systems which consume untrusted RIF documents, these external functions should be closely reviewed for their own vulnerabilities and for the vulnerabilities that may occur when they are used in unexpected combinations, like "cross-site scripting" attacks. In addition, as this media type uses the "+xml" convention, it shares the same security considerations as other XML formats; see RFC 3023 (XML Media Types). Interoperability considerations: This media type is intended to be shared with other RIF dialects, to be specified in the future. Interoperation between the dialects is governed by the RIF specifications. Published specifications: RIF Core Dialect W3C Working Draft (Recommendation Track) http://www.w3.org/TR/rif-core/ RIF Datatypes and Builtins W3C Working Draft (Recommendation Track) http://www.w3.org/TR/rif-dtb/ RIF Basic Logic Dialect W3C Working Draft (Recommendation Track) http://www.w3.org/TR/rif-bld/ RIF Production Rule Dialect W3C Working Draft (Recommendation Track) http://www.w3.org/TR/rif-prd/ RIF Framework for Logic Dialects W3C Working Draft (Recommendation Track) http://www.w3.org/TR/rif-fld/ This media type is intended for use by all RIF dialects, including those to be specified in the future. Identification of the RIF dialect in use by a document is done by examining the use of specific XML elements within the document. Applications that use this media type: See: http://www.w3.org/2005/rules/wiki/Implementations Additional information: Magic number(s): As with XML in general (See RFC 3023 (XML Media Types)), there is no magic number for this format. However, the XML namespace "http://www.w3.org/2007/rif#" will normally be present in the document. It may theoretically be missing if the document uses XML entities in an obfuscatory manner, and may also be present in documents with ther media types, so use of the namespace is not conclusive. The hex form of that namespace will depend on the charset. For utf-8, the hex is: 68 74 74 70 3a 2f 2f 77 77 77 2e 77 33 2e 6f 72. File extension(s): .rif (or .xml) Macintosh file type code(s): "TEXT" (like other XML) Person & email address to contact for further information: Sandro Hawke<EMAIL_ADDRESS>Please send technical comments and questions about RIF to<EMAIL_ADDRESS>a mailing list with a public archive at http://lists.w3.org/Archives/Public/public-rif-comments/ Intended usage: COMMON Restrictions on usage: None Author: The editor and contact for this media type registration is Sandro Hawke<EMAIL_ADDRESS>Change controller: RIF is a product of the Rule Interchange Format (RIF) Working Group of the World Wide Web Consortium (W3C). See http://www.w3.org/2005/rules/wg for information on the group. The W3C (currently acting through this working group) has change control over the RIF specification.
This appendix summarizes the main changes to this document.
Changes since the draft of July 3, 2009.
Changes since the Candidate Recommendation of October 1, 2009.
Changes since the Recommendation of 22 June, 2010.


An abstract class, which all HTML elements extend.
- Annotations
- DocsEditable()
- DomName('Element')
- Extends
- Object
- EventTarget
- Node
- Element
- Implements
Constants
-
EventStreamProvider<Event>
abortEvent
=
const EventStreamProvider<Event>
('abort') -
constStatic factory designed to expose
abort
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
beforeCopyEvent
=
const EventStreamProvider<Event>
('beforecopy') -
constStatic factory designed to expose
beforecopy
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
beforeCutEvent
=
const EventStreamProvider<Event>
('beforecut') -
constStatic factory designed to expose
beforecut
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
beforePasteEvent
=
const EventStreamProvider<Event>
('beforepaste') -
constStatic factory designed to expose
beforepaste
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
blurEvent
=
const EventStreamProvider<Event>
('blur') -
constStatic factory designed to expose
blur
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
canPlayEvent
=
const EventStreamProvider<Event>
('canplay') -
const
-
EventStreamProvider<Event>
canPlayThroughEvent
=
const EventStreamProvider<Event>
('canplaythrough') -
const
-
EventStreamProvider<Event>
changeEvent
=
const EventStreamProvider<Event>
('change') -
constStatic factory designed to expose
change
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
clickEvent
=
const EventStreamProvider<MouseEvent>
('click') -
constStatic factory designed to expose
click
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
contextMenuEvent
=
const EventStreamProvider<MouseEvent>
('contextmenu') -
constStatic factory designed to expose
contextmenu
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
copyEvent
=
const EventStreamProvider<Event>
('copy') -
constStatic factory designed to expose
copy
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
cutEvent
=
const EventStreamProvider<Event>
('cut') -
constStatic factory designed to expose
cut
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
doubleClickEvent
=
const EventStreamProvider<Event>
('dblclick') -
constStatic factory designed to expose
doubleclick
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
dragEndEvent
=
const EventStreamProvider<MouseEvent>
('dragend') -
constA stream of
dragend
events fired when an element completes a drag operation. -
EventStreamProvider<MouseEvent>
dragEnterEvent
=
const EventStreamProvider<MouseEvent>
('dragenter') -
constA stream of
dragenter
events fired when a dragged object is first dragged over an element. -
EventStreamProvider<MouseEvent>
dragEvent
=
const EventStreamProvider<MouseEvent>
('drag') -
constA stream of
drag
events fired when an element is currently being dragged. -
EventStreamProvider<MouseEvent>
dragLeaveEvent
=
const EventStreamProvider<MouseEvent>
('dragleave') -
constA stream of
dragleave
events fired when an object being dragged over an element leaves the element's target area. -
EventStreamProvider<MouseEvent>
dragOverEvent
=
const EventStreamProvider<MouseEvent>
('dragover') -
constA stream of
dragover
events fired when a dragged object is currently being dragged over an element. -
EventStreamProvider<MouseEvent>
dragStartEvent
=
const EventStreamProvider<MouseEvent>
('dragstart') -
constA stream of
dragstart
events for a dragged element whose drag has begun. -
EventStreamProvider<MouseEvent>
dropEvent
=
const EventStreamProvider<MouseEvent>
('drop') -
constA stream of
drop
events fired when a dragged object is dropped on an element. -
EventStreamProvider<Event>
durationChangeEvent
=
const EventStreamProvider<Event>
('durationchange') -
const
-
EventStreamProvider<Event>
emptiedEvent
=
const EventStreamProvider<Event>
('emptied') -
const
-
EventStreamProvider<Event>
endedEvent
=
const EventStreamProvider<Event>
('ended') -
const
-
EventStreamProvider<Event>
errorEvent
=
const EventStreamProvider<Event>
('error') -
constStatic factory designed to expose
error
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
focusEvent
=
const EventStreamProvider<Event>
('focus') -
constStatic factory designed to expose
focus
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
fullscreenChangeEvent
=
const EventStreamProvider<Event>
('webkitfullscreenchange') -
constStatic factory designed to expose
fullscreenchange
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
fullscreenErrorEvent
=
const EventStreamProvider<Event>
('webkitfullscreenerror') -
constStatic factory designed to expose
fullscreenerror
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
inputEvent
=
const EventStreamProvider<Event>
('input') -
constStatic factory designed to expose
input
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
invalidEvent
=
const EventStreamProvider<Event>
('invalid') -
constStatic factory designed to expose
invalid
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<KeyboardEvent>
keyDownEvent
=
const EventStreamProvider<KeyboardEvent>
('keydown') -
constStatic factory designed to expose
keydown
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<KeyboardEvent>
keyPressEvent
=
const EventStreamProvider<KeyboardEvent>
('keypress') -
constStatic factory designed to expose
keypress
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<KeyboardEvent>
keyUpEvent
=
const EventStreamProvider<KeyboardEvent>
('keyup') -
constStatic factory designed to expose
keyup
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
loadedDataEvent
=
const EventStreamProvider<Event>
('loadeddata') -
const
-
EventStreamProvider<Event>
loadedMetadataEvent
=
const EventStreamProvider<Event>
('loadedmetadata') -
const
-
EventStreamProvider<Event>
loadEvent
=
const EventStreamProvider<Event>
('load') -
constStatic factory designed to expose
load
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseDownEvent
=
const EventStreamProvider<MouseEvent>
('mousedown') -
constStatic factory designed to expose
mousedown
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseEnterEvent
=
const EventStreamProvider<MouseEvent>
('mouseenter') -
constStatic factory designed to expose
mouseenter
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseLeaveEvent
=
const EventStreamProvider<MouseEvent>
('mouseleave') -
constStatic factory designed to expose
mouseleave
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseMoveEvent
=
const EventStreamProvider<MouseEvent>
('mousemove') -
constStatic factory designed to expose
mousemove
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseOutEvent
=
const EventStreamProvider<MouseEvent>
('mouseout') -
constStatic factory designed to expose
mouseout
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseOverEvent
=
const EventStreamProvider<MouseEvent>
('mouseover') -
constStatic factory designed to expose
mouseover
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<MouseEvent>
mouseUpEvent
=
const EventStreamProvider<MouseEvent>
('mouseup') -
constStatic factory designed to expose
mouseup
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<WheelEvent>
mouseWheelEvent
=
const EventStreamProvider<WheelEvent>
('mousewheel') -
const
-
EventStreamProvider<Event>
pasteEvent
=
const EventStreamProvider<Event>
('paste') -
constStatic factory designed to expose
paste
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
pauseEvent
=
const EventStreamProvider<Event>
('pause') -
const
-
EventStreamProvider<Event>
playEvent
=
const EventStreamProvider<Event>
('play') -
const
-
EventStreamProvider<Event>
playingEvent
=
const EventStreamProvider<Event>
('playing') -
const
-
EventStreamProvider<Event>
rateChangeEvent
=
const EventStreamProvider<Event>
('ratechange') -
const
-
EventStreamProvider<Event>
resetEvent
=
const EventStreamProvider<Event>
('reset') -
constStatic factory designed to expose
reset
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
resizeEvent
=
const EventStreamProvider<Event>
('resize') -
const
-
EventStreamProvider<Event>
scrollEvent
=
const EventStreamProvider<Event>
('scroll') -
constStatic factory designed to expose
scroll
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
searchEvent
=
const EventStreamProvider<Event>
('search') -
constStatic factory designed to expose
search
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
seekedEvent
=
const EventStreamProvider<Event>
('seeked') -
const
-
EventStreamProvider<Event>
seekingEvent
=
const EventStreamProvider<Event>
('seeking') -
const
-
EventStreamProvider<Event>
selectEvent
=
const EventStreamProvider<Event>
('select') -
constStatic factory designed to expose
select
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
selectStartEvent
=
const EventStreamProvider<Event>
('selectstart') -
constStatic factory designed to expose
selectstart
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
stalledEvent
=
const EventStreamProvider<Event>
('stalled') -
const
-
EventStreamProvider<Event>
submitEvent
=
const EventStreamProvider<Event>
('submit') -
constStatic factory designed to expose
submit
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<Event>
suspendEvent
=
const EventStreamProvider<Event>
('suspend') -
const
-
EventStreamProvider<Event>
timeUpdateEvent
=
const EventStreamProvider<Event>
('timeupdate') -
const
-
EventStreamProvider<TouchEvent>
touchCancelEvent
=
const EventStreamProvider<TouchEvent>
('touchcancel') -
constStatic factory designed to expose
touchcancel
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TouchEvent>
touchEndEvent
=
const EventStreamProvider<TouchEvent>
('touchend') -
constStatic factory designed to expose
touchend
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TouchEvent>
touchEnterEvent
=
const EventStreamProvider<TouchEvent>
('touchenter') -
constStatic factory designed to expose
touchenter
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TouchEvent>
touchLeaveEvent
=
const EventStreamProvider<TouchEvent>
('touchleave') -
constStatic factory designed to expose
touchleave
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TouchEvent>
touchMoveEvent
=
const EventStreamProvider<TouchEvent>
('touchmove') -
constStatic factory designed to expose
touchmove
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TouchEvent>
touchStartEvent
=
const EventStreamProvider<TouchEvent>
('touchstart') -
constStatic factory designed to expose
touchstart
events to event handlers that are not necessarily instances of Element. -
EventStreamProvider<TransitionEvent>
transitionEndEvent
=
const EventStreamProvider<TransitionEvent>
('transitionend') -
const
-
EventStreamProvider<Event>
volumeChangeEvent
=
const EventStreamProvider<Event>
('volumechange') -
const
-
EventStreamProvider<Event>
waitingEvent
=
const EventStreamProvider<Event>
('waiting') -
const
Static Methods
-
isTagSupported(
String tag) → bool - Checks to see if the tag name is supported by the current platform.
Properties
- Map<String,String> attributes
-
read / writeAll attributes on this element.
- String baseUri
-
read-only, inherited
- CssRect borderEdge
-
read-onlyAccess the dimensions and position of this element's content + padding + border box.
- List<Node> childNodes
-
read-only, inheritedA list of this node's children.
- List<Element> children
-
read / writeList of the direct children of this element.
- CssClassSet classes
-
read / writeThe set of CSS classes applied to this element.
- String className
-
read / write
- Rectangle client
-
read-onlyGets the position of this element relative to the client area of the page.
- int clientHeight
-
read-only
- int clientLeft
-
read-only
- int clientTop
-
read-only
- int clientWidth
-
read-only
- CssRect contentEdge
-
read-onlyAccess this element's content position.
- String contentEditable
-
read / write
- MenuElement contextMenu
-
read / write
- Map<String,String> dataset
-
read / writeAllows access to all custom data attributes (data-*) set on this element.
- String dir
-
read / write
- Point documentOffset
-
read-onlyProvides the coordinates of the element relative to the top of the document.
- bool draggable
-
read / write
- String dropzone
-
read / write
- Node firstChild
-
read-only, inheritedThe first child of this node.
-
read / write
- String id
-
read / write
- String innerHtml
-
read / writeParses the HTML fragment and sets it as the contents of this element.
- bool isContentEditable
-
read-only
- String lang
-
read / write
- Node lastChild
-
read-only, inheritedThe last child of this node.
- String localName
-
read-only
- CssRect marginEdge
-
read-onlyAccess the dimensions and position of this element's content + padding + border + margin box.
- String namespaceUri
-
read-onlyA URI that identifies the XML namespace of this element.
- Element nextElementSibling
-
read-only
- Node nextNode
-
read-only, inheritedThe next sibling node.
- String nodeName
-
read-only, inheritedThe name of this node.
- List<Node> nodes
-
read / write, inheritedA modifiable list of this node's children.
- int nodeType
-
read-only, inheritedThe type of node.
- String nodeValue
-
read-only, inheritedThe value of this node.
- Rectangle offset
-
read-onlyGets the offset of this element relative to its offsetParent.
- int offsetHeight
-
read-only
- int offsetLeft
-
read-only
- Element offsetParent
-
read-only
- int offsetTop
-
read-only
- int offsetWidth
-
read-only
- ElementEvents on
-
read-onlyThis is an ease-of-use accessor for event streams which should only be used when an explicit accessor is not available.
- ElementStream<Event> onAbort
-
read-onlyStream of
abort
events handled by thisElement
. - ElementStream<Event> onBeforeCopy
-
read-onlyStream of
beforecopy
events handled by thisElement
. - ElementStream<Event> onBeforeCut
-
read-onlyStream of
beforecut
events handled by thisElement
. - ElementStream<Event> onBeforePaste
-
read-onlyStream of
beforepaste
events handled by thisElement
. - ElementStream<Event> onBlur
-
read-onlyStream of
blur
events handled by thisElement
. - ElementStream<Event> onCanPlay
-
read-only
- ElementStream<Event> onCanPlayThrough
-
read-only
- ElementStream<Event> onChange
-
read-onlyStream of
change
events handled by thisElement
. - ElementStream<MouseEvent> onClick
-
read-onlyStream of
click
events handled by thisElement
. - ElementStream<MouseEvent> onContextMenu
-
read-onlyStream of
contextmenu
events handled by thisElement
. - ElementStream<Event> onCopy
-
read-onlyStream of
copy
events handled by thisElement
. - ElementStream<Event> onCut
-
read-onlyStream of
cut
events handled by thisElement
. - ElementStream<Event> onDoubleClick
-
read-onlyStream of
doubleclick
events handled by thisElement
. - ElementStream<MouseEvent> onDrag
-
read-onlyA stream of
drag
events fired when this element currently being dragged. - ElementStream<MouseEvent> onDragEnd
-
read-onlyA stream of
dragend
events fired when this element completes a drag operation. - ElementStream<MouseEvent> onDragEnter
-
read-onlyA stream of
dragenter
events fired when a dragged object is first dragged over this element. - ElementStream<MouseEvent> onDragLeave
-
read-onlyA stream of
dragleave
events fired when an object being dragged over this element leaves this element's target area. - ElementStream<MouseEvent> onDragOver
-
read-onlyA stream of
dragover
events fired when a dragged object is currently being dragged over this element. - ElementStream<MouseEvent> onDragStart
-
read-onlyA stream of
dragstart
events fired when this element starts being dragged. - ElementStream<MouseEvent> onDrop
-
read-onlyA stream of
drop
events fired when a dragged object is dropped on this element. - ElementStream<Event> onDurationChange
-
read-only
- ElementStream<Event> onEmptied
-
read-only
- ElementStream<Event> onEnded
-
read-only
- ElementStream<Event> onError
-
read-onlyStream of
error
events handled by thisElement
. - ElementStream<Event> onFocus
-
read-onlyStream of
focus
events handled by thisElement
. - ElementStream<Event> onFullscreenChange
-
read-onlyStream of
fullscreenchange
events handled by thisElement
. - ElementStream<Event> onFullscreenError
-
read-onlyStream of
fullscreenerror
events handled by thisElement
. - ElementStream<Event> onInput
-
read-onlyStream of
input
events handled by thisElement
. - ElementStream<Event> onInvalid
-
read-onlyStream of
invalid
events handled by thisElement
. - ElementStream<KeyboardEvent> onKeyDown
-
read-onlyStream of
keydown
events handled by thisElement
. - ElementStream<KeyboardEvent> onKeyPress
-
read-onlyStream of
keypress
events handled by thisElement
. - ElementStream<KeyboardEvent> onKeyUp
-
read-onlyStream of
keyup
events handled by thisElement
. - ElementStream<Event> onLoad
-
read-onlyStream of
load
events handled by thisElement
. - ElementStream<Event> onLoadedData
-
read-only
- ElementStream<Event> onLoadedMetadata
-
read-only
- ElementStream<MouseEvent> onMouseDown
-
read-onlyStream of
mousedown
events handled by thisElement
. - ElementStream<MouseEvent> onMouseEnter
-
read-onlyStream of
mouseenter
events handled by thisElement
. - ElementStream<MouseEvent> onMouseLeave
-
read-onlyStream of
mouseleave
events handled by thisElement
. - ElementStream<MouseEvent> onMouseMove
-
read-onlyStream of
mousemove
events handled by thisElement
. - ElementStream<MouseEvent> onMouseOut
-
read-onlyStream of
mouseout
events handled by thisElement
. - ElementStream<MouseEvent> onMouseOver
-
read-onlyStream of
mouseover
events handled by thisElement
. - ElementStream<MouseEvent> onMouseUp
-
read-onlyStream of
mouseup
events handled by thisElement
. - ElementStream<WheelEvent> onMouseWheel
-
read-onlyStream of
mousewheel
events handled by thisElement
. - ElementStream<Event> onPaste
-
read-onlyStream of
paste
events handled by thisElement
. - ElementStream<Event> onPause
-
read-only
- ElementStream<Event> onPlay
-
read-only
- ElementStream<Event> onPlaying
-
read-only
- ElementStream<Event> onRateChange
-
read-only
- ElementStream<Event> onReset
-
read-onlyStream of
reset
events handled by thisElement
. - ElementStream<Event> onResize
-
read-only
- ElementStream<Event> onScroll
-
read-onlyStream of
scroll
events handled by thisElement
. - ElementStream<Event> onSearch
-
read-onlyStream of
search
events handled by thisElement
. - ElementStream<Event> onSeeked
-
read-only
- ElementStream<Event> onSeeking
-
read-only
- ElementStream<Event> onSelect
-
read-onlyStream of
select
events handled by thisElement
. - ElementStream<Event> onSelectStart
-
read-onlyStream of
selectstart
events handled by thisElement
. - ElementStream<Event> onStalled
-
read-only
- ElementStream<Event> onSubmit
-
read-onlyStream of
submit
events handled by thisElement
. - ElementStream<Event> onSuspend
-
read-only
- ElementStream<Event> onTimeUpdate
-
read-only
- ElementStream<TouchEvent> onTouchCancel
-
read-onlyStream of
touchcancel
events handled by thisElement
. - ElementStream<TouchEvent> onTouchEnd
-
read-onlyStream of
touchend
events handled by thisElement
. - ElementStream<TouchEvent> onTouchEnter
-
read-onlyStream of
touchenter
events handled by thisElement
. - ElementStream<TouchEvent> onTouchLeave
-
read-onlyStream of
touchleave
events handled by thisElement
. - ElementStream<TouchEvent> onTouchMove
-
read-onlyStream of
touchmove
events handled by thisElement
. - ElementStream<TouchEvent> onTouchStart
-
read-onlyStream of
touchstart
events handled by thisElement
. - ElementStream<TransitionEvent> onTransitionEnd
-
read-onlyStream of
transitionend
events handled by thisElement
. - ElementStream<Event> onVolumeChange
-
read-only
- ElementStream<Event> onWaiting
-
read-only
- String outerHtml
-
read-only
- Document ownerDocument
-
read-only, inheritedThe document this node belongs to.
- CssRect paddingEdge
-
read-onlyAccess the dimensions and position of this element's content + padding box.
- Element parent
-
read-only, inheritedThe parent element of this node.
- Node parentNode
-
read-only, inheritedThe parent node of this node.
- Element previousElementSibling
-
read-only
- Node previousNode
-
read-only, inheritedThe previous sibling node.
- int scrollHeight
-
read-only
- int scrollLeft
-
read / write
- int scrollTop
-
read / write
- int scrollWidth
-
read-only
- ShadowRoot shadowRoot
-
read-only
- bool spellcheck
-
read / write
- CssStyleDeclaration style
-
read-only
- int tabIndex
-
read / write
- String tagName
-
read-only
- String text
-
read / write, inheritedAll text within this node and its decendents.
- String title
-
read / write
- bool translate
-
read / write
- dynamic xtag
-
read / writeExperimental support for web components. This field stores a reference to the component implementation. It was inspired by Mozilla's x-tags project. Please note: in the future it may be possible to
extend Element
from your class, in which case this field will be deprecated.
Constructors
- Element.a()
-
Creates a new
<a>
element. - Element.article()
-
Creates a new
<article>
element. - Element.aside()
-
Creates a new
<aside>
element. - Element.audio()
-
Creates a new
<audio>
element. - Element.br()
-
Creates a new
<br>
element. - Element.canvas()
-
Creates a new
<canvas>
element. - Element.created()
- Custom element creation constructor.
- Element.div()
-
Creates a new
<div>
element. -
Creates a new
<footer>
element. - Element.header()
-
Creates a new
<header>
element. - Element.hr()
-
Creates a new
<hr>
element. - Element.html(String html, {NodeValidator validator, NodeTreeSanitizer treeSanitizer})
- Creates an HTML element from a valid fragment of HTML.
- Element.iframe()
-
Creates a new
<iframe>
element. - Element.img()
-
Creates a new
<img>
element. - Element.li()
-
Creates a new
<li>
element. -
Creates a new
<nav>
element. - Element.ol()
-
Creates a new
<ol>
element. - Element.option()
-
Creates a new
<option>
element. - Element.p()
-
Creates a new
<p>
element. - Element.pre()
-
Creates a new
<pre>
element. - Element.section()
-
Creates a new
<section>
element. - Element.select()
-
Creates a new
<select>
element. - Element.span()
-
Creates a new
<span>
element. - Element.svg()
-
Creates a new
<svg>
element. - Element.table()
-
Creates a new
<table>
element. - Element.tag(String tag, [String typeExtention])
- Creates the HTML element specified by the tag name.
- Element.td()
-
Creates a new
<td>
element. - Element.textarea()
-
Creates a new
<textarea>
element. - Element.th()
-
Creates a new
<th>
element. - Element.tr()
-
Creates a new
<tr>
element. - Element.ul()
-
Creates a new
<ul>
element. - Element.video()
-
Creates a new
<video>
element.
Methods
-
addEventListener(
String type, dynamic listener(Event event), [bool useCapture]) → void -
inherited
-
animate(
Object effect, [Object timing]) → AnimationPlayer -
append(
Node newChild) → Node -
inheritedAdds a node to the end of the child nodes list of this node.
-
appendHtml(
String text, {NodeValidator validator, NodeTreeSanitizer treeSanitizer}) → void - Parses the specified text as HTML and adds the resulting node after the last child of this element.
-
appendText(
String text) → void - Adds the specified text after the last child of this element.
-
attached(
) → void - Called by the DOM when this element has been inserted into the live document.
-
attributeChanged(
String name, String oldValue, String newValue) → void - Called by the DOM whenever an attribute on this has been changed.
-
blur(
) → void -
click(
) → void -
clone(
bool deep) → Node -
inheritedReturns a copy of this node.
-
contains(
Node other) → bool -
inheritedReturns true if this node contains the specified node.
-
createFragment(
String html, {NodeValidator validator, NodeTreeSanitizer treeSanitizer}) → DocumentFragment - Create a DocumentFragment from the HTML fragment and ensure that it follows the sanitization rules specified by the validator or treeSanitizer.
-
createShadowRoot(
) → ShadowRoot -
detached(
) → void - Called by the DOM when this element has been removed from the live document.
-
dispatchEvent(
Event event) → bool -
inherited
-
enteredView(
) → void - Deprecated*: override attached instead.
-
focus(
) → void -
getAnimationPlayers(
) → List<AnimationPlayer> -
getAttribute(
String name) → String -
getAttributeNS(
String namespaceURI, String localName) → String -
getBoundingClientRect(
) → Rectangle - Returns the smallest bounding rectangle that encompasses this element's padding, scrollbar, and border.
-
getClientRects(
) → List<Rectangle> - Returns a list of bounding rectangles for each box associated with this element.
-
getComputedStyle(
[String pseudoElement]) → CssStyleDeclaration - The set of all CSS values applied to this element, including inherited and default values.
-
getDestinationInsertionPoints(
) → List<Node> - Returns a list of shadow DOM insertion points to which this element is distributed.
-
getElementsByClassName(
String classNames) → List<Node> - Returns a list of nodes with the given class name inside this element.
-
getNamespacedAttributes(
String namespace) → Map<String,String> - Gets a map for manipulating the attributes of a particular namespace.
-
hasChildNodes(
) → bool -
inheritedReturns true if this node has any children.
-
insertAdjacentElement(
String where, Element element) → Element -
insertAdjacentHtml(
String where, String html, {NodeValidator validator, NodeTreeSanitizer treeSanitizer}) → void - Parses text as an HTML fragment and inserts it into the DOM at the specified location.
-
insertAdjacentText(
String where, String text) → void -
insertAllBefore(
Iterable<Node> newNodes, Node refChild) → Node -
inheritedInserts all of the nodes into this node directly before refChild.
-
insertBefore(
Node newChild, Node refChild) → Node -
inheritedInserts all of the nodes into this node directly before refChild.
-
leftView(
) → void - Deprecated*: override detached instead.
-
matches(
String selectors) → bool -
matchesWithAncestors(
String selectors) → bool - Checks if this element or any of its parents match the CSS selectors.
-
offsetTo(
Element parent) → Point -
Provides the offset of this element's borderEdge relative to the
specified
parent
. -
query(
String relativeSelectors) → Element - Alias for querySelector. Note this function is deprecated because its semantics will be changing in the future.
-
queryAll(
String relativeSelectors) → ElementList<Element> - Alias for querySelectorAll. Note this function is deprecated because its semantics will be changing in the future.
-
querySelector(
String selectors) → Element - Finds the first descendant element of this element that matches the specified group of selectors.
-
querySelectorAll(
String selectors) → ElementList<Element> - Finds all descendent elements of this element that match the specified group of selectors.
-
remove(
) → void - Removes this node from the DOM.
-
removeEventListener(
String type, dynamic listener(Event event), [bool useCapture]) → void -
inherited
-
replaceWith(
Node otherNode) → Node -
inheritedReplaces this node with another node.
-
requestFullscreen(
) → void -
requestPointerLock(
) → void -
scrollIntoView(
[ScrollAlignment alignment]) → void - Scrolls this element into view.
-
setAttribute(
String name, String value) → void -
setAttributeNS(
String namespaceURI, String qualifiedName, String value) → void -
setInnerHtml(
String html, {NodeValidator validator, NodeTreeSanitizer treeSanitizer}) → void - Parses the HTML fragment and sets it as the contents of this element. This ensures that the generated content follows the sanitization rules specified by the validator or treeSanitizer.
-
toString(
) → String - The string representation of this element.


{% set title = "Authorize " + client["client_name"] %} {% extends "base.html" %} {% block body %}
You are currently logged in as {{ crsid }}.
Grant access permissions to {{ client["client_name"] }}.
{{ client["client_name"] }} only needs to know your username (crsid)


Systems is how we see the world, design is how we change it.
Systems Design Engineering (SYDE) has a focus on systems thinking and design thinking. Systems thinking, is way of thinking about and modelling the world. Design thinking is applied to create human-centered solutions to these problems. Used together, we can tackle interdisciplinary problems that cover many fields of engineering.
SYDE is an accredited engineering program, meaning its graduates are eligible for the Professional Engineering designation through PEO. As such we learn a lot of theory in math and physics, as well as applications in hardware and software. The first two years are about understanding the physical world, and acquiring analytic and math skills. This toolbox of skills allows us to solve real, hands-on problems involving large systems.
Design is a complementary skill set of processes for planning and executing solutions to problems. The perfect complement to engineering, design is rarely taught outright to engineers. Human-centered design processes allow an engineer to think beyond the technical aspects of a problem. Design ensures that an engineer's solution "fits human desires, needs, and capabilities. After all, why do we make products? We make them for people to use." We practice our design skills every term through project courses.
The skills that we learn in SYDE can be applied to any problem in any field. Our core courses teach us a diverse mix of applied and technical skills, broken down by field below. Students also have access to a wide array of technical electives, and can specialize in nearly any other field of engineering.
For future students: Below is a chart of all the core SYDE courses you will take during your degree, grouped by subject and year. To view full course descriptions, visit the official Systems Design course calendar . Consider if you enjoy the general topics enough to study them for the next 5 years; we want you to be happy with your choice of degree!
Design is really an act of communication, which means having a deep understanding of the person with whom the designer is communicating.
What sets SYDE apart from your typical engineering program is our emphasis on designing for all people. Design is more than making things aesthetically pleasing; it is a method to design useable solutions. Human Centered Design means questioning the problem that you think you need to solve. It involves deeply understanding the people who will use your engineered solution. Design is all about starting with people, instead of starting technical. This process is an effective way to solve engineering problems, as well as the human concerns that accompany them.
Design thinking is a human-centered approach to innovation that draws from the designer’s toolkit to integrate the needs of people, the possibilities of technology, and the requirements for business success.
While many of our design courses are project-focused, there is a great set of tools that we learn to apply.
If I had an hour to solve a problem I’d spend 55 minutes thinking about the problem and 5 minutes thinking about solutions.
Engineering problems are complicated, and they will only grow in complexity as society progresses.  Look inside and you will find:
These small parts connected together as a phone create an impact on society greater than they could by themselves. This is a system, and one that a Systems Design Engineer may work on.
Systems are an organized assembly of interconnected components. The interactions of components create behaviours that affect the system as a whole. This definition is general on purpose; systems can be anything. The process you learn for analyzing the drive-train of a car can be applied to analyzing the resilience of an entire city. Systems thinking is a method for designing and managing these diverse systems. In essence it is a unique way of viewing problems.
As engineers, use systems thinking to create models of physical systems so as to understand engineering problems. This is why we take so many physics and math courses, so that we can apply our skills to modelling dynamic systems. Such problems may be as simple as a slinky that continues bouncing even after you drop it down a staircase. This also applies to complex problems involving many moving parts, stresses, and applied forces.


--- layout: default ---
Database of maritime fasteners found somewhere in the oceans.
Some sort of description here.
Chandler tender spirits barkadeer wherry doubloon plunder killick execution dock starboard.  Blow the man down bilge water yo-ho-ho Plate Fleet Sea Legs mutiny gally landlubber or just lubber chandler black jack.


Module: Mongoid::Traversable
Overview
Provides behavior around traversing the document graph.
Defined Under Namespace
Modules: ClassMethods, DiscriminatorAssignment, DiscriminatorRetrieval
Instance Method Summary collapse
-
#_children ⇒ Array<Document>
Get all child
Documents
to thisDocument
, going n levels deep if necessary. - #_parent ⇒ Object
- #_parent=(p) ⇒ Object
-
#_reset_memoized_children! ⇒ nil
Resets the memoized children on the object.
-
#_root ⇒ Document
Return the root document in the object graph.
-
#_root? ⇒ true, false
Is this document the root document of the hierarchy?.
-
#collect_children ⇒ Array<Document>
Collect all the children of this document.
-
#flag_children_persisted ⇒ Array<Document>
Marks all children as being persisted.
-
#hereditary? ⇒ true, false
Determines if the document is a subclass of another document.
-
#parentize(document) ⇒ Document
Sets up a child/parent association.
-
#remove_child(child) ⇒ Object
Remove a child document from this parent.
-
#reset_persisted_children ⇒ Array<Document>
After children are persisted we can call this to move all their changes and flag them as persisted in one call.
Instance Method Details
#_children ⇒ Array<Document>
Get all child Documents
to this Document
, going n levels deep if necessary. This is used when calling update persistence operations from the root document, where changes in the entire tree need to be determined. Note that persistence from the embedded documents will always be preferred, since they are optimized calls… This operation can get expensive in domains with large hierarchies.
132 133 134 |
# File 'lib/mongoid/traversable.rb', line 132 def _children @__children ||= collect_children end |
#_parent ⇒ Object
14 15 16 |
# File 'lib/mongoid/traversable.rb', line 14 def _parent @__parent ||= nil end |
#_parent=(p) ⇒ Object
18 19 20 |
# File 'lib/mongoid/traversable.rb', line 18 def _parent=(p) @__parent = p end |
#_reset_memoized_children! ⇒ nil
Resets the memoized children on the object. Called internally when an embedded array changes size.
244 245 246 247 |
# File 'lib/mongoid/traversable.rb', line 244 def _reset_memoized_children! _parent._reset_memoized_children! if _parent @__children = nil end |
#_root ⇒ Document
Return the root document in the object graph. If the current document is the root object in the graph it will return self.
256 257 258 259 260 |
# File 'lib/mongoid/traversable.rb', line 256 def _root object = self while (object._parent) do object = object._parent; end object end |
#_root? ⇒ true, false
Is this document the root document of the hierarchy?
270 271 272 |
# File 'lib/mongoid/traversable.rb', line 270 def _root? _parent ? false : true end |
#collect_children ⇒ Array<Document>
Collect all the children of this document.
144 145 146 147 148 149 150 151 152 153 154 155 156 |
# File 'lib/mongoid/traversable.rb', line 144 def collect_children children = [] .each_pair do |name, association| without_autobuild do child = send(name) Array.wrap(child).each do |doc| children.push(doc) children.concat(doc._children) end if child end end children end |
#flag_children_persisted ⇒ Array<Document>
Marks all children as being persisted.
166 167 168 169 170 |
# File 'lib/mongoid/traversable.rb', line 166 def flag_children_persisted _children.each do |child| child.new_record = false end end |
#hereditary? ⇒ true, false
Determines if the document is a subclass of another document.
178 179 180 |
# File 'lib/mongoid/traversable.rb', line 178 def hereditary? self.class.hereditary? end |
#parentize(document) ⇒ Document
Sets up a child/parent association. This is used for newly created objects so they can be properly added to the graph.
191 192 193 |
# File 'lib/mongoid/traversable.rb', line 191 def parentize(document) self._parent = document end |
#remove_child(child) ⇒ Object
Remove a child document from this parent. If an embeds one then set to nil, otherwise remove from the embeds many.
This is called from the RemoveEmbedded
persistence command.
206 207 208 209 210 211 212 213 214 |
# File 'lib/mongoid/traversable.rb', line 206 def remove_child(child) name = child.association_name if child. remove_ivar(name) else relation = send(name) relation.send(:delete_one, child) end end |
#reset_persisted_children ⇒ Array<Document>
After children are persisted we can call this to move all their changes and flag them as persisted in one call.
225 226 227 228 229 230 231 |
# File 'lib/mongoid/traversable.rb', line 225 def reset_persisted_children _children.each do |child| child.move_changes child.new_record = false end _reset_memoized_children! end |


# Great Galloping Cuckoos
## Algorithms Faster than $log(n)$
### [Codemash](http://codemash.org) v<IP_ADDRESS> - 8 January 2016
## Matt Williams
[matt<EMAIL_ADDRESS>[@matt_k_williams](http://twitter.com/matt_k_williams)
[http://matthewkwilliams.com](http://matthewkwilliams.com)
[http://20slides.com](http://20slides.com)
[http://github.com/aetherical](http://github.com/aetherical)
Note
: The lovely picture is by my daughter Althea
## Background aka Why am I Up Here?
* Raspberry Pi Addict
* Search for "real" work for Pi's
* In the process I've discovered lots of new and nifty algorithms
## Disclaimers
1. I am not a Mathmetician
2. I am not a Chemist (this will make sense later)
3. I am not an expert
4. I have become passionate about this topic
## Good Algorithms Matter
> The real reason behind choosing good algorithms to solve a problem
> is that the good ones either break the problem into smaller problems
> or are myopic; focusing only on the steps needed to reach an
> answer. All else is superfluous.
## Real World™ Considerations
Each algorithm has its "sweet spot", but the considerations tend to be among the following:
* Space
* Runtime
* Data Access
> Know thy data
> -- "Not Socrates"
> Like sand through the hourglass, so is the data of our lives
> -- Also "Not Socrates"
## The Big $O$
- $O()$ refers to the complexity of an algorithm.
- You can also think of it in terms of the number of cycles/comparisons/steps to complete its task.
## $O(n)$
### Linear Time
Size | Cycles
----:|---------:
1 | 1
2 | 2
10 | 10
100 | 100
1000 | 1000
## $O(n^2)$
## Quadratic Time
Size | Cycles
----:|---------:
1 | 1
2 | 4
10 | 100
100 | 10000
1000 | 1000000
## $O(nlog(n))$
Size | Cycles
----:|----------:
1 | 0
2 | 1
10 | 23
100 | 460
1000 | 6907
## $O(log(n))$
### Logarithmic Time
Size | Cycles
----:|----------:
1 | 0
2 | 1
10 | 3
100 | 7
1000 | 10
## $O(log(i))$
### Logarithmic Time
Size | Cycles
----:|----------:
1 | 1
2 | 1
10 | 1
100 | 2
1000 | 3
## $O(log(log(n)))$
### "Logalog"
Size | Cycles
----:|------------:
100000 | 2
1000000 | 2
10000000 | 2
100000000 | 2
1000000000 | 3
## $O(1)$
### Constant Time
Size | Cycles
----:|---------:
1 | 1
2 | 1
10 | 1
100 | 1
1000 | 1
## Searches
Looking for 812...
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Linear
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Binary
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Binary
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Binary
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Binary
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Galloping Search
- First published in 1976!!!!
- Sliding Window
- Good for cases where
- The target is at beginning or end
- The bounds of the search space are not closed (like log file)
- Approaches $O(log(i))$
## Galloping Search
First window is $2^1$ long.
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^ ^
| |
'-----'
## Galloping Search
Second window is $2^2$ long.
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^ ^
| |
'-----------------'
## Galloping Search
Third window is $2^3$ (or to the end of the array) wide. When the
proper window is found, then do a binary search on the window.
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^ ^
| |
'-----------------------------'
## Where it Beats Binary Search
- If 22 is the target, binary search takes 3 checks. Galloping search finds it on a window boundary.
* * Galloping
| o Binary
.-----.
| |
v v
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^ ^ ^
| | |
o o o
3 2 1
## Where it Beats Binary Search
- If looking for 13, then binary search takes 4 checks to find it isn't a match. Galloping finds it isn't in the array immediately.
* * Galloping
| o Binary
.--+--.
| |
v v
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^ ^ ^ ^
| | | |
o o o o
4 3 2 1
## Variants on Galloping Search
- Start at other end
- Trot -- step grows linearly (1,2,3,...) so that the indexes are
(1,3,6,10,15,...). Once the value is overshot, then hone in with
binary search. $O(\sqrt n)$
## Interpolation Search
## Interpolation Search
* Similar to how we look up a word in a dictionary.
* Instead of splitting in $1/2$ each time, make a guess where it should be in range of values
* Assumes an uniform distribution of points
* Approaches $O(log(log(n)))$
## Interpolation Search
### Predicted Location
$(seeking/max)/size$
## Interpolation Search
First check point: $(812 / 931) * 12 = 10$
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
^
|
## Search Summary
Searching for 812
Algorithm | # of Iterations
----------|---------------:
Linear | 10
Binary | 4
Galloping | 4
Interpolation | 1
> "What the hell is this monstrosity?
>
> "Jerry says the name is probably some kind of rotten pun. What does it do?"
>
> "Basically it takes the value of the characters of a demon's name, multiplies them by a number, adds another number and then divides the result by 65,353. Then it uses that result as a subscript in some kind of an array." She shook her head again. "Why 65,353? Jesus! You know, if this guy doesn't come back we may never understand some of this stuff." -- [The Wizardry Compiled by Rick Cook](http://www.baenebooks.com/showproduct.aspx?ProductID=1632&SEName=the-wizardry-compiled)
## Hash
* Used for sparsely populated universes
* Quick lookup of values
* Often implemented with a space the size of a (largeish) prime. 65353 is a large prime near the maximum size of a 16 bit unsigned Integer.
## Hash
.-----.
| |
+-----+
| |
+-----+
| |
+-----+
| |
+-----+
| |
'-----'
## Hash
Hashing function maps entity to limited space in hash
$(CRC(entity) modulus ARRAYLENGTH)$
.-----.
| |
+-----+
| 5 |
+-----+
| |
+-----+
| 9 |
+-----+
| |
'-----'
## Hash Collision
Try to insert 23; but it collides with 5.
.-----.
| |
+-----+
| 5 |
+-----+
| |
+-----+
| 9 |
+-----+
| |
'-----'
## Handling Collisions
* Rehash with larger hash table
* Buckets
## Hash: Bucket Hash
.-----.
| |
+-----+ .-----.
| 5 +-->| 23 |
+-----+ '-----'
| |
+-----+
| 9 |
+-----+
| |
'-----'
## Hash: Bucket Hash
.-----.
| A |
+-----+ .-----. .-----.
| 5 +-->| 23 +-->| 72 |
+-----+ '-----' '-----'
| |
+-----+ .-----. .-----. .-----.
| 9 +-->| 101 +-->| bee +-->| X |
+-----+ '-----' '-----' '-----'
| b |
'-----'
## Cuckoo Hash
A common cuckoo chick pushes one of its host’s eggs out of the nest. Detail of figure 1 from [Anderson et al. (2009)](http://dx.doi.org/10.1371/journal.pone.0007725)
## Cuckoo Hash
A common cuckoo chick pushes one of its host’s eggs out of the nest. Detail of figure 1 from [Anderson et al. (2009)](http://dx.doi.org/10.1371/journal.pone.0007725)
## Cuckoo Hash
Trying to insert 23 again, it collides with 5
.-----. .-----.
| | | |
+-----+ +-----+
| 5 | | |
+-----+ +-----+
| | | |
+-----+ +-----+
| 9 | | |
+-----+ +-----+
| | | |
'-----' '-----'
## Evict 5
Each hash has a separate hashing function
.-----. .-----.
| | | |
+-----+ +-----+
| 23 +----+ | |
+-----+ | +-----+
| | | | |
+-----+ | +-----+
| 9 | +---->+ 5 |
+-----+ +-----+
| | | |
'-----' '-----'
## Time Passes
.-----. .-----.
| | | M |
+-----+ +-----+
| 23 | | X |
+-----+ +-----+
| B | | |
+-----+ +-----+
| 9 | | 5 |
+-----+ +-----+
| | | |
'-----' '-----'
## Multiple Evictions
Adding 101, collides with B & B collides with X
.-----. .-----.
| | | M |
+-----+ +-----+
| 23 | | X |
+-----+ +-----+
| B | | |
+-----+ +-----+
| 9 | | 5 |
+-----+ +-----+
| | | |
'-----' '-----'
## Multiple Evictions
.-----. .-----.
| | | M |
+-----+ +-----+
| 23 | +------->+ B +--+
+-----+ | +-----+ |
| 101 +-+ | | |
+-----+ +-----+ |
| 9 | | 5 | |
+-----+ +-----+ |
| X +<-+ | | |
'-----' | '-----' |
+----------------+
## Advantages of Cuckoo Hash
* Approaches $O(1)$ for inserts
* $O(1)$ for lookups
## Limitations of Cuckoo Hash
* Needs a certain amount of empty space; if not an eviction cycle can occur
* May need to resize & rehash to keep evictions from looping
> Obi-Wan: "That Hash is our only hope."
>
> Yoda: "No.... there is another."
## Peacock Hash
* Handles collisions by adding extra smaller hashes
* Originally devised for network routers to store IP/Mac Addresses
* Realtime, constant time
## Peacock Hash
.-----.
| |
+-----+ .-----.
| 23 | | X |
+-----+ +-----+ .-----.
| B | | | | M |
+-----+ +-----+ '-----'
| 9 | | 5 |
+-----+ '-----'
| |
'-----'
## Unordered Set
* Can be implemented as a list or as a hash
* Inserts are cheap; retrievals may not be
.-.
.-+ |
.--+ 5 '--.
| X |
.+ A Z 3 +.
| Pi |
'+ cat 2.7 +'
| 99 |
'--+ 101 .--'
'-+ |
'-'
## Ordered Sets
* Elements stored sorted; inserts can be expensive
.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.-----.
| 1 | 22 | 47 | 135 | 239 | 333 | 497 | 764 | 799 | 812 | 876 | 931 |
'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'-----'
## Stored as Tree
.---.
| 333 |
'---'
/ \
/ \
/ \
/ \
.---. .---.
| 47 | | 764 |
'---' '---'
/ \ / \
/ \ / \
.---. .---. .---. .---.
| 22 | | 135 | | 497 | | 812 |
'---' '---' '---' '---'
## Set Intersection
## Set Intersection
* Surveyed implementations are $O(n)$ for intersection
* Ruby
* Java
* Go
## Galloping Intersection
## Comparisons of Set Intersections
Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)
Algorithm | # of comparisons
-----------|----------------:
Sequential | 119479075
Adaptive | 83326341
Small Adaptive | 68706234
Interpolation Sequential | 55275738
Interpolation Adaptive | 58558408
## Comparisons of Set Intersections
Excerpted from [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)
Algorithm | # of comparisons
-----------|----------------:
Sequential | 119479075
Interpolation Small Adaptive | 44525318
Extrapolation Small Adaptive | 50018852
Extrapolate Many Small Adaptive | 44087712
Extrapolate Ahead Small Adaptive | 43930174
## Case Study
* Search for Real Work™ for my Pi Cluster
* Pi 2B
* 4 Cores / 900 Mhz
* 1G Ram
* I/O on USB 2 Bus (480 MHz)
## Case Study
* Substructure Search
* PubChem from NIH
* 150GB compressed download
* Uncompressed, 25K substances is 120MB; whole ~3TB
* ~69 Million substances
## Smiles
* Text Description of Chemical Structures
* C1CCCCC1 is a benzene ring
* Typically Hydrogen is left out
* Can be more than one way to describe the same structure
"Benzene-aromatic-3D-balls" by Benjah-bmm27 - Own work. Licensed under Public Domain via Commons.
## Naive Solution
> SMILES is text.
> What do we use to search text?
Image by [EpicBusinessman](https://www.reddit.com/user/EpicBusinessman); from [I drew this GREP thing and kinda forgot about it.](https://www.reddit.com/r/gamegrumps/comments/1yffou/i_drew_this_grep_thing_and_kinda_forgot_about_it/)
## Naive Solution
* 5 Pi 2B, searching a subset of data
* ID, Smiles, Name
* Docker Swarm to distribute workload
## Naive Solution
Structure | Results | Time
----------|--------:|-----:
C1CCCCC1=O | ~2500 | 5s
C1CCCCC1O | ~17500 | 15s
## Fingerprints
* Pubchem has a defined bitmap to describe a molecule
* 880 bits wide
* Has >2 Carbon, >4 Carbon, Boron, A ring
## Lightbulb
* SMILES can be converted to Fingerprint with Chemistry Dev Kit
* If I create sets of substances which have a particular bit set, I
can take the intersections of those sets to find the substances
which match the fingerprint.
## Sets
* 810 sets, one for each bit in the bitmap
* One file per bit in bitmap containing a list of substances which have the bit set.
* Using unsigned 32bit ints, the sets are anywhere from 4 bytes to 225MB in size.
* Median 9.3M (2326026 substances)
* Average 40M
* 33GB total
## Optimizations
Memoization FTW!
: If I've solved it once, why solve it again?
## Optimizations
* Start from the smallest set and compare it with other sets
* In cases where the majority of the substances have this property, consider inverting the set -- checking against the substances which don't have the property
## If it's a bitmap... why not use bitmap tools
* In order to fit the universe, 10000 x 10000 1 bit PNG
* 12K to 6.8M
* Median 1.7M
* Average 2.4M
## Bitmaps
* ImageMagick on a 3.5 GHz box requires 10s/image intersection using a single core.
* `convert FILE1 FILE2 -compose Darken -composite out.png`
* Using 5 cores can do 30/minute
* Pre-Calculating all of the paths will take ~20 years.
## Credits
- Presentation created with Reveal.js
- Markdown and Diagram rendering via Markdeep
## Resources: General Topics
- [Big O notation](https://en.wikipedia.org/wiki/Big_O_notation)
- [SIMD](https://en.wikipedia.org/wiki/SIMD)
## Resources: Bitmaps
- [Better bitmap performance with Roaring bitmaps](http://arxiv.org/pdf/1402.6407v9.pdf)
- [A General SIMD-based Approach to Accelerating Compression Algorithms](http://arxiv.org/abs/1502.01916)
- [Roaring Bitmap](https://github.com/lemire/RoaringBitmap)
## Resources: Cuckoos
- [Cuckoo Hashing Visualization](http://www.lkozma.net/cuckoo_hashing_visualization/)
- [Cuckoo Hashing](http://citeseerx.ist.psu.edu/viewdoc/download?doi=<IP_ADDRESS>.4189&rep=rep1&type=pdf) (the original paper)
- [cuckoo - GoDoc](https://godoc.org/github.com/tildeleb/cuckoo) (go library)
- [garethm/cuckoo](https://github.com/garethm/cuckoo) (ruby)
## Resources: Searches
* [Binary search](http://www.programming-algorithms.net/article/40119/Binary-search)
* [Linear search](http://www.programming-algorithms.net/article/40168/Linear-search)
* [Prune and search](http://www.programming-algorithms.net/article/41235/Prune-and-search)
## Resources: Galloping Search
- [Beating the binary search algorithm – interpolation search, galloping search](http://blog.teamleadnet.com/2014/06/beating-binary-search-algorithm.html)
- [AN ALMOST OPTIMAL ALGORTTHM FOR UNBOUNDED SEARCHING](http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-1679.pdf)
## Resources: Interpolation
- [Interpolation search](http://www.programming-algorithms.net/article/40348/Interpolation-search)
## Resources: Peacock Hashes
- [Approximately-Perfect Hashing: Improving Network Throughput through Efficient Off-chip Routing Table Lookup](http://www.cise.ufl.edu/~zhuang/doc/infocom11.pdf)
- [Peacock Hashing: Deterministic and Updatable Hashing for High Performance Networking](http://www.arl.wustl.edu/~sailesh/papers/Peacoc%20Hash%20v2.doc)
## Resources: Sets
- [A Fast Set Intersection Algorithm for Sorted Sequences](http://www.cs.ucr.edu/~stelo/cpm/cpm04/25_Baeza-yates.pdf)
- [Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences](https://cs.uwaterloo.ca/~ajsaling/papers/paper-spire.pdf)
- [Experimental Comparison of Set Intersection Algorithms for Inverted Indexing](http://ceur-ws.org/Vol-1003/58.pdf)
- [Fast Set Intersection in Memory](http://research.microsoft.com/pubs/142850/p255-dingkoenig.pdf)
- [Faster Adaptive Set Intersections for Text Searching](http://www.cs.toronto.edu/~tl/papers/wea06.pdf)
- [Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions](http://www.vldb.org/pvldb/vol8/p293-inoue.pdf)
- [SIMD Compression and the Intersection of Sorted Integers](http://arxiv.org/abs/1401.6399)
## Resources: Cheminformatics
* [The PubChem Project](https://pubchem.ncbi.nlm.nih.gov/)
* [SDF Toolkit](http://cactus.nci.nih.gov/SDF_toolkit/) (perl)
* [Chemistry Development Kit](http://sourceforge.net/projects/cdk/) (java)
* [Simplified molecular-input line-entry system (SMILES)](https://en.wikipedia.org/wiki/Simplified_molecular-input_line-entry_system)
## Resources: Raspberry Pi
* [http://raspberrypi.org](http://raspberrypi.org)
* [http://blog.hypriot.org](http://blog.hypriot.org)
* [http://matthewkwilliams.com](http://matthewkwilliams.com)


Toggle navigation
Final Portfolio Bootstrap and D3
Home
Filled Area Chart
Multi-series Line Chart (Ex 7) with Legend
Vertical Bar Chart
Horizontal Bar Chart
Stack Bar Chart
Donut Chart
Pie Chart
User-Filterable Multi-Line Chart
Resizing versions of Ex 5 and Ex 8, Part 2
Bootstrap Dashboard
Final Project Bootstrap and D3
Portfolio
d3 Chart Porfolio
Filled Area Chart
Multi-series Line Chart (Ex 7) with Legend
Vertical Bar Chart
Horizontal Bar Chart
Stacked Bar Chart
Donut Chart
Pie Chart
User-Filterable Multi-Line Chart
Resizing
Bootstrap Dashboard