La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

www2006-rules-tutorial-v6 [Read-Only]

De
52 pages
Version Notes for this Tutorial SlidesetWELCOME! to the WWW-2006 Tutorial“Semantic Web Rules with Ontologies, and The final-version slideset (5/25/06) is, as compared their E-Service Applications” to the hard-copy tutorial notes:by Benjamin Grosof and Mike Dean• Updated generally (fairly minor updates, nothing radical) INSTRUCTIONS! All participants, please:– Particularly about W3C RIF Standards effort Download the final-version tutorial (ongoing) slideset (updated since conference hard-copy version)http://ebusiness.mit.edu/bgrosof/#WWW2006RulesTutorialSign in on the participants list (hard copy sheet) with your name, organization, email; optionally also add your interests, homepage URL5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 1 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 2Top-Level Outline of TutorialSlideset 1 of• Overview and Get Acquainted“Semantic Web Rules with Ontologies, and their E-Service Applications” A. Core -- KR Languages and Standards B. Tools -- SweetRules, Jena, cwm, and Moreby Benjamin Grosof*andMike Dean**(BREAK in middle) *MIT Sloan School of Management, http://ebusiness.mit.edu/bgrosof**BBN Technologies, http://www.daml.org/people/mdeanC. Applications -- Policies, Services, and Semantic IntegrationWWW-2006 Conference Tutorial (half-day),that the 15 International Conference on the World Wide Web, May 26, 2006, • WindupEdinburgh, Scotland, UKVersion ...
Voir plus Voir moins

Version Notes for this Tutorial SlidesetWELCOME! to the WWW-2006 Tutorial
“Semantic Web Rules with Ontologies, and
The final-version slideset (5/25/06) is, as compared
their E-Service Applications” to the hard-copy tutorial notes:
by Benjamin Grosof and Mike Dean
• Updated generally (fairly minor updates, nothing radical)
INSTRUCTIONS! All participants, please:
– Particularly about W3C RIF Standards effort Download the final-version tutorial
(ongoing)
slideset (updated since conference hard-copy version)
http://ebusiness.mit.edu/bgrosof/#WWW2006RulesTutorial
Sign in on the participants list (hard copy
sheet) with your name, organization, email;
optionally also add your interests, homepage URL
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 1 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 2
Top-Level Outline of TutorialSlideset 1 of
• Overview and Get Acquainted
“Semantic Web Rules with Ontologies, and
their E-Service Applications” A. Core -- KR Languages and Standards
B. Tools -- SweetRules, Jena, cwm, and More
by Benjamin Grosof*andMike Dean**
(BREAK in middle)
*MIT Sloan School of Management, http://ebusiness.mit.edu/bgrosof
**BBN Technologies, http://www.daml.org/people/mdean
C. Applications -- Policies, Services, and Semantic Integration
WWW-2006 Conference Tutorial (half-day),
that the 15 International Conference on the World Wide Web, May 26, 2006, • Windup
Edinburgh, Scotland, UK
Version Date: May 25, 2006
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 3 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 4
Next Generation Web
Big Questions Addressed
Semantic Web Services
• What are the critical features/aspects of the
new technology for SW rules, in combination
Semantic Web techniques Web Services techniques with ontologies? API’s on Web
Automated
(WSDL, SOAP)Knowledge Bases
Rules (RuleML) Two interwoven aspects: • What business problems does it help solve? Program: Web Services XMLOntologies (OWL)
Data: Semantic WebDatabases (SQL,
XQuery, RDF)
First Generation • … from a researcher perspective…
Web
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 5 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 6
1Outline of Part A. Outline of Part B.
A. Core -- KR Languages and Standards B. Tools -- SweetRules, Jena, cwm, and More1. Intro
(BREAK in middle) 2. Overview of Logic Knowledge Representations and Standards
3. Horn Logic / Horn LP
4. Nonmonotonic LP 1. Commercially Important pre-SW Rule Systems
5. Procedural Attachments - Prolog, production rules, DBMS
6. Frame syntax/logic; Hilog; Lloyd-Topor 2. Overview of SW Rule Generations
7. RuleML 3. 1st Gen.: Rudimentary Interoperability and XML/RDF Support
8. Combining Rules with Ontologies; Description LP - CommonRules, SweetRules V1, OWLJessKB
9. Datatypes
4. 2nd Gen.: Rule Systems within RDF/OWL/SW Toolkits 10. Review of OWL and RDF
- cwm, Jena-2, and others11. SWRL
5. 3rd Gen.: SW Rule Integration and Life Cycle12. W3C RIF and OMG PRR
- SweetRules V2 13. Additional Aspects and Approaches
- Default/OO Inheritance, Integrity Constraints
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 7 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 8
Outline of Part C.
C. Applications -- Policies, Services, and Semantic Integration Let’s Get Acquainted
0. Quick Overview of SWS Task Clusters
• … We’ll go around the room …1. Ontology Translation and Semantic Integration
- SWRL uses, ECOIN, financial services
2. End-to-End E-Contracting and Business Process Automation • Please BRIEFLY (10sec max) tell the group your
- supply chain, e-tailing, auctions, SweetDeal, Process Handbook
name, organization3. Business Policies including Trust
- credit, health, RBAC, XACML, P3P, justifications
4. Semantic Web Services • Please also SIGN IN on the participants list (a hard-
-SWSF, WSMO copy sheet) with your name, organization, email
5. Prospective Early Adopter areas, strategy, and market evolution – + optionally: interests, homepage URL
6. Windup and Discussion
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 9 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 10
Quickie Bio of Presenter Benjamin Grosof Quickie Bio of Presenter Mike Dean
• MIT Sloan professor since 2000 • Principal Engineer, BBN Technologies
• 12 years at IBM T.J. Watson Research; 2 years at startups • B.S. in Computer Engineering from Stanford University.
• PhD Comp Sci, Stanford; BA Applied Math Econ/Mgmt, Harvard
• Semantic web services is main research area: • Principal Investigator, DAML Integration and Transition effort
– Rules as core technology • Chair, Joint US/EU ad hoc Markup Language Committee
– Business Applications, Implications, Strategy: – responsible for DAML+OIL and SWRL
• e-contracting/supply-chain; finance; trust; … • Editor, OWL Web Ontology Language Reference
– Overall knowledge representation, e-commerce, intelligent agents
• Developer of several Semantic Web tools and reference data sets
• Actively using SWRL in a variety of Semantic Web applications • Co-Founder, Rule Markup Language Initiative – the leading emerging
) • Member, W3C RDF Core, Web Ontology, and Rule Interchange standards body in semantic web rules (http://www.ruleml.org
Format Working Groups– Co-Lead, DAML Rules
– Co-Lead on Rules, Joint US-EU ad hoc Agent Markup Language Committee • Member, RuleML Steering Committee
• Invited Expert Member, W3C Rules Interchange Format (RIF) Working Group •er, Architecture Committee, Semantic Web Services Initiative
• Core participant in Semantic Web Services Initiative – which coordinates world-wide
SWS research and early standards (http://www.swsi.org)
– Area Editor for Contracts & Negotiation, Language Committee
– Co-Chair, Industrial Partners program (SWSIP) 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 11 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 12
2Outline of Part A.Slideset 2 of
A. Core -- KR Languages and Standards
1. Intro “Semantic Web Rules with Ontologies, and
2. Overview of Logic Knowledge Representations and Standards
their E-Service Applications” 3. Horn Logic / Horn LP
4. Nonmonotonic LP
5. Procedural Attachments
by Benjamin Grosof*andMike Dean** 6. Frame syntax/logic; Hilog; Lloyd-Topor
*MIT Sloan School of Management, http://ebusiness.mit.edu/bgrosof 7. RuleML
8. Combining Rules with Ontologies; Description LP**BBN Technologies, http://www.daml.org/people/mdean
9. Datatypes
10. Review of OWL and RDF WWW-2006 Conference Tutorial (half-day),
th 11. SWRL at the 15 International Conference on the World Wide Web, May 26, 2006,
12. W3C RIF and OMG PRREdinburgh, Scotland, UK
13. Additional Aspects and Approaches
Version Date: May 25, 2006 - Default/OO Inheritance, Integrity Constraints
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 13 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 14
Flavors of Rules Commercially Most Commercial Applications of Rules
Important today in E-Business today in E-Business
• There are many. An established area since the 1980’s.
– Expert systems, policy management, workflow, systems • E.g., in OO app’s, DB’s, workflows. management, etc.
– Far more applications to date than of Description Logic.
• Relational databases, SQL: Views, queries, facts are all rules.
• SQL99 even has recursive rules.
• Advantages in systems specification, maintenance, integration. • Production rules (OPS5 heritage): e.g.,
– Jess, ILOG, Blaze, Haley: rule-based Java/C++ objects.
• Market momentum: moderately fast growing • Event-Condition-Action rules (loose family), cf.:
– Fast in early-mid 1980’s.
– business process automation / workflow tools. – Slow late 1980’s-mid-1990’s.
– active databases; publish-subscribe. – Picked up again in late 1990’s. (Embeddable methodologies.)
• Prolog. “logic programs” as a full programming language. – Accelerating in 2000’s.
• (Lesser: other knowledge-based systems.)
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 15 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 16
Vision: Uses of Rules in E-Business Rule-based Semantic Web Services
• Rules/LP in appropriate combination with DL as KR, for RSWS
• Rules as an important aspect of coming world of Internet e-business:
– DL good for categorizing: a service overall, its inputs, its outputsrule-based business policies & business processes, for B2B & B2C.
– represent seller’s offerings of products & services, capabilities, bids;
map offerings from multiple suppliers to common catalog. • Rules to describe service process models
– represent buyer’s requests, interests, bids; → matchmaking. – rules good for representing:
– represent sales help, customer help, procurement, authorization/trust, • preconditions and postconditions, their contingent relationships
brokering, workflow.
• contingent behavior/features of the service more generally,
– high level of conceptual abstraction; easier for non-programmers to
– e.g., exceptions/problemsunderstand, specify, dynamically modify & merge.
– familiarity and naturalness of rules to software/knowledge engineers– executable but can treat as data, separate from code
• potentially ubiquitous; already wide: e.g., SQL views, queries.
• Rules in communicating applications, e.g., embedded intelligent agents. • Rules to specify deals about services: cf. e-contracting.
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 17 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 18

Application Scenarios Rule-based Semantic Web Services
for Rule-based Semantic Web Services
• Rules often good to executably specify service process models
• SweetDeal [Grosof & Poon 2002] configurable reusable e-contracts: – e.g., business process automation using procedural attachments to
– LP rules about agent contracts with exception handlingperform side-effectful/state-changing actions ("effectors" triggered by
– … on top of DL ontologies about business processes;drawing of conclusions)
– e.g., rules obtain info via procedural attachments ("sensors" test rule – a scenario motivating DLP
conditions) • Other:
– e.g., rules for knowledge translation or inferencing – Trust management / authorization (Delegation Logic) [Li, Grosof, &
Feigenbaum 2000]– e.g., info services exposing relational DBs
– Financial knowledge integration (ECOIN) [Firat, Madnick, & Grosof
2002]
• Infrastructural: rule system functionality as services: • Rule-based translation among contexts / ontologies
– e.g., inferencing, translation • Equational ontologies
– Business policies, more generally, e.g., privacy (P3P)
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 19 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 20
Semantic Rules: Differences from Rules in
Why Standardize Rules Now? the 1980’s / Expert Systems Era
• Get the KR right (knowledge representation)• Rules as a form of KR (knowledge representation) are
– More mature research understandingespecially useful: – Semantics independent of algorithm/implementation
– Cleaner; avoid general programming/scripting language capabilities– relatively mature from basic research viewpoint
– Highly scaleable performance; better algorithms; choice from interoperability
– Highly modular wrt updating; use prioritization– good for prescriptive specifications (vs. descriptive)
– Highly dynamic, scaleable rulebase authoring: distributed, integration, partnering• a restricted programming mechanism
• Leverage Web, esp. XML
– integrate well into commercially mainstream – Interoperable syntax
software engineering, e.g., OO and DB – Merge knowledge bases
• easily embeddable; familiar • Embeddable
– Into mainstream software development environments (Java, C++, C#); not its own • vendors interested already: Webizing, app. dev. tools
programming language/system (cf. Prolog)
• ⇒⇒ Identified as part of mission of the W3C Semantic • Knowledge Sharing: intra- or inter- enterprise
Web Activity, for example • Broader set of Applications
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 21 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 22
Standardization: Current Scene Rules News Highlights (last 18 months)
• RuleML Initiative since fall 2000 • RuleML-2005 International Conference on Rules and Rule
Markup Languages for the Semantic Web– works with all the major umbrella standards bodies
– Now a full conference, maturing from 3 annual Workshops – collaborates with SWSI, WSMO, Joint Committee
each colocated with ISWC• OMG standards effort on Production Rules since winter 2004-05
• SweetRules open source toolset released Nov. 2004– working with RuleML
– Several technical advances esp. on RuleML-based • W3C Rule Interchange Format Working Group since Dec. 2005 interoperability
– influenced by RuleML, along with SWSI (SWSL, SWSF) and • SWSI’s SWSL/RuleML-update drafted; contributed to W3CWSMO (WSML, WRL) and Joint Committee (SWRL,
• WSML/WRL drafted; contributed to W3CSWRL-FOL)
• OMG standards effort formed • Oasis very interested too
• W3C Working Group formed– Influenced by RuleML, in collaboration with SWSI, WSMO
• Oasis effort being contemplated • Also: ISO has Common Logic standards effort (slow moving,
for last few years) on First Order Logic (+…)
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 23 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 24
4Upcoming Conference: Outline of Part A.
RuleML-2006 A. Core -- KR Languages and Standards
1. Intro • Particularly relevant conference is:
nd 2. Overview of Logic Knowledge Representations and Standards• 2 International Conference on Rules and Rule Markup Languages
for the Semantic Web 3. Horn Logic / Horn LP
th– Actually 5 in series, in 2002-2004 it was a Workshop 4. Nonmonotonic LP
5. Procedural Attachments • Nov. 9-10 2006; with Workshops on Nov. 11
6. Frame syntax/logic; Hilog; Lloyd-Topor• In Athens, Georgia, USA
7. RuleML• Co-located with ISWC-2006 (International Semantic Web 8. Combining Rules with Ontologies; Description LPConference)
9. Datatypes– Co-located events ever since ISWC began in 2002
10. Review of OWL and RDF
• Paper submissions still possible! 11. SWRL
– Paper deadline 5 June 2006, abstract deadline 27 May 2006 12. W3C RIF and OMG PRR
13. Additional Aspects and Approaches
• For more info: http://2006.ruleml.org - Default/OO Inheritance, Integrity Constraints
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 25 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 26
Concept of KR Knowledge Representation:
What’s the Game?
• A KR S is defined as a triple (LP, LC, |=), where:
• Expressiveness: useful, natural, complex enough
– LP is a formal language of sets of premises (i.e., premise expressions)
• Reasoning algorithms– LC is a formal language of sets of conclusions (i.e., conclusion expressions)
• Remark: In declarative logic programs KR, LC is a subset of LP
• Syntax: encoding data format -- here, in XML
– |= is the entailment relation.
• Semantics: principles of sanctioned inference, independent of • Conc(P,S) stands for the set of conclusions
reasoning algorithms
that are entailed in KR S by a set of premises P
• We assume here that |= is a functional relation. • Computational Tractability (esp. worst-case): scale up in a manner
qualitatively similar to relational databases: computation cycles go up as a
polynomial function of input size
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 27 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 28
W3C Semantic Web “Stack”: Standardization Steps The Web Rule Language in its Context
[2002]
[by RuleML & SWSI & WSMO 04-2005]
Emerging Standards
pioneered in DARPA Agent Markup
Language (DAML) program:
•RuleML FOL++
•OWL
Rules OWLVocabulary
RDF(S)Model &
Syntax
XML
[Diagram http://www.w3.org/DesignIssues/diagrams/sw-stack-2002.png is courtesy Tim Berners-Lee] Unicode URI
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 29 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 30
5Overview of Logic Knowledge Representations 08-2005 W3C Semantic Web “Stack”: Standardization Steps
(KR’s) and Markup Standards
• First Order Logic (FOL)
DLP = – Standards efforts:
Description • ISO Simplified Common Logic (SCL) (formerly Knowledge Interchange
Logic Format)
Programs • FOL-RuleML (sublanguage of RuleML) & the closely related SWRL-FOL
– Restriction: Horn FOL
– Restriction: Description Logic (DL)
• Standard: W3C OWL-DL & the closely related RDF-Schema (subset)
– Extension: Higher Order Logic (HOL)
• Logic Programs (LP)
– (Here: in the declarative sense.)
– Standards efforts: RuleML & the closely related SWRL (subset)
– Extension features:
• Nonmonotonicity: Negation-As-Failure (NAF) ; Priorities (cf. Courteous)
• Procedural Attachments (aproc’s) for tests and actions (cf. Situated)
– Restriction: Horn LP
– Restriction: Description Logic Programs (DLP): overlaps with DL
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 31 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 32
Description Logic: KR Expressiveness, in briefVenn Diagram: Expressive Overlaps among KR’s
• Restriction of First Order Logic (FOL)
First-Order – Most essentially on the patterns of variable appearances
Logic – Class predicates of arity 1
– Property predicates of arity 2
– Complex class expressions
Description Horn Logic – Membership axioms: foo instance-of BarClass
Logic Programs – Inclusion axioms between classes (possibly complex)
• C1 subsumed-by C2
Logic • I.e., x instance-of C1 ⇒ x instance-of C2
Programs • No logical functions
• Cannot directly represent n-ary predicates, but can indirectlyDescription
(Negation As NB: Nonmon LP, Logic • Good for representing: Failure) including Courteous,
Programs relies on NAF as – Many kinds of ontological schemas, including taxonomies
fundamental – Taxonomic/category subsumptions (with strict inheritance)(Procedural
underlying KR – Some kinds of categorization/classification tasksAttachments) expressive
– Some kinds of configuration tasks mechanism
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 33 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 34
Summary of Computational Complexity of KR’s Overview of Computational Complexity of KR’s
• For task of inferencing, i.e., computing entailment of a given query. • For task of inferencing, i.e., computing entailment of a given query.
– Tractable = time is polynomial in n = |premises|– Tractable = time is polynomial in n ; where n = |premises|
• First Order Logic (FOL):
• First Order Logic (FOL) – Intractable (co-NP-complete) but decidable, for restriction to Propositional
– Intractable but decidable, for restriction to Description Logic cf. OWL-DL – Intractable for restriction to Description Logic, or to
– Undecidable, in general; e.g., for restriction to SWRL Propositional
• Logic Programs (LP) with extensions for NAF, Courteous, Test/Action Aproc’s:
– Undecidable, in general – Tractable, for restriction VB Datalog: (Similar to Relational DB’s)
• Logic Programs (LP) with extensions for NAF, Courteous, 1. Datalog* = no logical functions of arity > 0 ; and
2. VB = constant-bounded number of distinct variables per rule Test/Action Aproc’s
– … Can actually tractably compute all atomic conclusions – Tractable, under common restrictions; complexity similar – … (Under well-founded-semantics definition of NAF, tractable aproc call)
to Relational DB’s – Tractable, therefore, for restriction to Description Logic Programs
2 2– O(n ), for restriction to Propositional with NAF – O(n ), for restriction to Propositional with NAF
– Intractable but decidable, in general– Intractable, in general
– * Can relax to: no recursion through logical functions (ensures tractable Herbrand universe)
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 35 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 36
6z
z
z
z
z
z
z
Horn LP as Foundation Core KR Outline of Part A.
A. Core -- KR Languages and Standards • Horn LP provides the foundation core KR and conceptual
1. Intro intuitions for Rules
2. Overview of Logic Knowledge Representations and Standards
– pre- Semantic Web3. Horn Logic / Horn LP
4. Nonmonotonic LP – Semantic Web – including RuleML
5. Procedural Attachments
6. Frame syntax/logic; Hilog; Lloyd-Topor
7. RuleML
8. Combining Rules with Ontologies; Description LP
9. Datatypes
10. Review of OWL and RDF
11. SWRL
12. W3C RIF and OMG PRR
13. Additional Aspects and Approaches
- Default/OO Inheritance, Integrity Constraints
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 37 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 38
Horn FOL Advantage of Horn: Reduced Complexity
The Horn subset of FOL is defined relative to clausal form of FOL.
• Horn is less complex computationally -- and algorithmicallyA Horn clause is one in which there is at most one positive literal.
It takes one of the two forms:
1. H \/ ¬B1 \/ … \/ ¬Bm . A.k.a. a definite clause / rule • Propositional FOL is co-NP-complete (recall 3-SAT is NP-complete…)
Fact H . is special case of rule (H ground, m=0)
2. ¬B1 \/ … \/ ¬Bm . A.k.a. an integrity constraint
• Propositional Horn FOL is O(n)
where m ≥ 0, H and Bi’s are atoms.
(An atom = pred(term_1,…,term_k) where pred has arity k.) • (For task of inferencing, i.e., computing entailment of a given query.
– n = |Premise KB| )A definite clause (1.) can be written equivalently as an implication:
Rule := H ⇐ B1 /\ … /\ Bm . where m ≥ 0, H and Bi’s are atoms
head if body ;
An integrity constraint (2.) can likewise be written as:
⊥⇐B1 /\ … /\ Bm . A.k.a. empty-head rule (⊥ is often omitted).
For refutation theorem-proving , represent a negated goal as (2.).
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 39 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 40
Horn LP Syntax and Semantics Example of Horn LP vs. Horn FOL
• Let P be:• Horn LP syntax is similar to implication form of Horn FOL.
– DangerousTo(?x,?y) ← PredatorAnimal(?x) and Human(?y).– The implication connective’s semantics are a bit weaker however.
– PredatorAnimal(?x) ← Lion(?x). We will write it as ← instead of ⇐.
– Lion(Simba).
• Declarative LP with model-theoretic semantics – Human(Joey).
– Same for forward-direction (“derivation” / “bottom-up”) and backward-direction • I1 = {Lion(Simba), Human(Joey)}(“query” / “top-down”) inferencing
• I2 = {PredatorAnimal(Simba),Lion(Simba), Human(Joey)}– Model M(P) = a set of (concluded) ground atoms
• I3 = {DangerousTo(Simba,Joey), PredatorAnimal(Simba),Lion(Simba), Human(Joey)}
• (P = the set of premise rules) • I4 = I3. Thus M(P) = I3.
• Semantics is defined via the least fixed point of an operator T . TP P
outputs conclusions that are immediately derivable (through some rule • Let P’ be the Horn FOL rulebase version of P above, where ⇐ replaces ←.
in P) from an input set of intermediate conclusions I . • Then the ground atomic conclusions of P’ are exactly those in M(P) above.j
• P’ also entails various non-ground-atom conclusions, including: – I = T (I) ; I = emptysetj+1 P j 0
1. Non-unit derived clauses, e.g., DangerousTo(Simba,?y) ⇐ Human(?y). • I = all head atoms of rules whose bodies are satisfied by I . j+1 j
2. All tautologies of FOL, e.g., Human(?z) \/ ¬Human(?z). – M(P) = LeastFixedPoint(T ) (LFP = I such that I = I )m m+1 mP 3. Combinations of (1.) and (2.), e.g., ¬Human(?y) ⇐¬DangerousTo(Simba,?y).
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 41 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 42
7Horn LP Compared to Horn FOL Summary: The “Spirit” of LP
• Fundamental Theorem connects Horn LP to Horn FOL: The following summarizes the “spirit” of how LP differs from FOL:
– M(P) = {all ground atoms entailed by P inOL}
• “Avoid Disjunction”
– Avoid disjunctive expressions as premises or conclusions.• Horn FOL has additional non-ground-atom conclusions, notably:
– I.e., disjunctions of positive literals are not permitted as – non-unit derived clauses; tautologies
premises, nor as intermediate or final conclusions. Permitting • Can thus view Horn LP as the f-weakening of Horn FOL. such disjunctions is what creates exponential blowup of
– “f-” here stands for “fact-form conclusions only” computational complexity in propositional FOL (3-SAT NP-
– A restriction on form of conclusions (not of premises). hard).
• Horn LP -- differences from Horn FOL: – No “reasoning by cases”, therefore.
– Conclusions Conc(P) = essentially a set of ground atoms. • “Stay Grounded”• Can extend to permit more complex-form queries/conclusions.
– Avoid non-ground conclusions.– Consider Herbrand models only, in typical formulation and usage.
• P can then be replaced equivalently by {all ground instantiations of each rule in P}
Straightforwardly extensible, therefore, to:• Can extend to permit: equalities in rules/conclusions. (Also: universal queries.)
– Rule has non-empty head, in typical formulation and usage. – Non-monotonicity (negation-by-failure, then prioritized defaults)
• Can extend to detect violation of integrity constraints. – Procedural attachments (external actions, external premise facts)
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 43 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 44
Horn LP Computational Complexity Outline of Part A.
• For task of inferencing, i.e., computing entailment of a given query. A. Core -- KR Languages and Standards
– n = |Premise KB| i.e., |P|
1. Intro
2. Overview of Logic Knowledge Representations and Standards• Tractable, for restriction VB Datalog*: (Similar to Relational DB’s)
3. Horn Logic / Horn LP1. Datalog = no logical functions of arity > 0 ; and
4. Nonmonotonic LP2. VB = constant-bounded number of distinct variables per rule
5. Procedural Attachments – … Can actually tractably compute all atomic conclusions
v+1 6. Frame syntax/logic; Hilog; Lloyd-Topor– O(n ) where v is the bound in VB
7. RuleML– Tractable, therefore, for restriction to Description Logic Programs
• In DL form of DLP, VB ≡ constant-bounded number of distinct DL quantifiers 8. Combining Rules with Ontologies; Description LP
(incl. min/max cardinality) in class descriptions per inclusion axiom 9. Datatypes
– O(n), for restriction to Propositional 10. Review of OWL and RDF
11. SWRL
12. W3C RIF and OMG PRR
13. Additional Aspects and Approaches– * Can relax to: no recursion through logical functions (ensures tractable Herbrand universe)
- Default/OO Inheritance, Integrity Constraints
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 45 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 46
Concept of Logical MonotonicityVenn Diagram: Expressive Overlaps among KR’s
• A KR S is said to be logically monotonic when in it:First-Order
Logic P1 ⊆ P2 ⇒ Conc(P1,S) ⊆ Conc(P2,S)
• Where P1, P2 are each a set of premises in SDescription Horn Logic
Logic Programs • I.e., whenever one adds to the set of premises, the
Logic set of conclusions non-strictly grows (one does not
Programs retract conclusions).
Description
(Negation As NB: Nonmon LP, Logic
including Courteous, Failure)Programs relies on NAF as • Monotonicity is good for pure mathematics.
fundamental (Procedural
underlying KR – “Proving a theorem means never having to say you’re sorry.”Attachments) expressive
mechanism
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 47 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 48
8Nonmonotonicity Motivations Negation As Failure: Intro
• Pragmatic reasoning is, in general, nonmonotonic. • NAF is the most common form of negation in commercially
– E.g., policies for taking actions, exception handling, legal important rule and knowledge-based systems.
argumentation, Bayesian/statistical/inductive, etc.
• Concept/Intuition for ~q (~ stands for NAF)
– Monotonic is a special case – simpler wrt updating/merging, good
– q is not derivable from the available premise infofor pure mathematics.
– fail to believe q • Most commercially important rule systems and applications use
nonmonotonicity – … but might also not believe q to be false
• A basic expressive construct is ubiquitous there: – A.k.a. default negation, weak negation
– Negation-As-Failure (NAF) a.k.a. Default Negation
• Contrast with: ¬q (¬ stands for classical negation)• Another kind of expressive construct, almost as ubiquitous there, is:
– q is believed to be false – Priorities between rules
• Such nonmonotonicity enables: – A.k.a. strong negation
– Modularity and locality in revision/updating/merging
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 49 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 50
LP with Negation As Failure Semantics for LP with Negation As Failure
• Ordinary LP (OLP), a.k.a. Normal LP (a.k.a. “general” LP) • For fully general case, there are multiple proposed
semantics.– Adds NAF to Horn LP
– They all agree for a broad restricted case: stratified OLP• Syntax: Rule generalized to permit NAF’d body literals:
– The Well Founded Semantics (WFS) is the most popular • H ← B /\ … /\ B /\ ~ B /\ … /\ ~B .1 k k+1 m
among commercial system implementers (e.g., XSB) and where m ≥ 0, H and Bi’s are atoms
probably also among researchers
– A previous Stable Semantics is also still popular among
• Semantics has subtleties for the fully general case.
some researchers
– Difficulty is interaction of NAF with “recursion”, i.e.,
cyclic dependencies (thru the rules) of predicates/atoms.
– Lots of theory developed during 1984-1994
– Well-understood theoretically since mid-1990’s
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 51 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 52
Basic Example of LP with NAF Brief Examples of Non-Stratified OLP
(NB: this example is purely fictional.)• RB1: • RB3:
– price(Amazon,Sony5401,?day,?cust,49.99) – a.
← inUSA(?cust) /\ inMonth(?day,2004-10) /\ ~onSale(?day). – c ← a /\ ~b.
– price(Amazon,Sony5401,?day,?cust,39.99) – p ← ~p.
← inUSA(?cust) /\ inMonth(?day,2004-10) /\ onSale(?day). • Well Founded Semantics (WFS) for RB3 entails conclusions {a,c}.
p is not entailed. p has “undefined” (u) truth value (in 3-valued logic). – inMonth(2004-10-12,2004-10).
• Stable Semantics for RB3: there does not exist a set of conclusions. – inMonth(2004-10-30,2004-10).
(NOT: there is a set of conclusions that is empty.) – inUSA(BarbaraJones).
– inUSA(SalimBirza).
• RB4:– onSale(2004-10-30).
– a.• RB1 entails: (among other conclusions)
– c ← a /\ ~b. 1. Price(Amazon,Sony5401,2004-10-12,BarbaraJones,49.99)
– p ← ~q.2. Price(Amony5401,2004-10-30,SalimBirza,39.99)
– q ← ~p.• RB2 = RB1 updated to add: onSale(2004-10-12).
• WFS for RB4 entails conclusions {a,c}. p,q have truth value u. • RB2 does NOT entail (1.). Instead (nonmonotonically) it entails:
• Stable Semantics for RB4 results in two alternative conclusion sets: {a,c,p} and 3. Price(Amazon,Sony5401,2004-10-12,BarbaraJones,39.99)
{a,c,q}. Note their intersection {a,c} is the same as the WFS conclusions.
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 53 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 54
9Negation As Failure Implementations:Computing Well Founded Semantics for OLP
Current Limitations
• Always exactly one set of conclusions (entailed ground atoms).
• Tractable to compute all conclusions:
• Practice in Prolog and other currently commercially important (CCI)2– O(n ) for Propositional case
rule systems is often “sloppy” (incomplete / cut-corners) relative to 2v+2)– O(n ) for VB Datalog case canonical semantics for NAF
– NAF only moderately increases computational complexity – in cases of recursive rules, WFS algorithms required are more complex
compared to Horn (frequently linear, at worst quadratic) – ongoing diffusion of WFS theory & algorithms, beginning in Prolog’s
• By contrast, for Stable Semantics:
– There may be zero, or one, or a few, or very many alternative conclusion sets
• Current implemented OLP inferencing systems often do not handle – Intractable even for Propositional case
the fully general case in a semantically clean and complete fashion. • Proof procedures are known that handle the non-stratified general case
– Many are still based on older algorithms that preceded WFS theory/algorithms– backward-direction: notably, SLS-resolution
• Fairly mature wrt performance, e.g., tabling refinements
– forward-direction • Other CCI rule systems’ implementations of NAF are often “ad hoc”
• Not very mature yet, esp. wrt performance, for fully general case.
– Lacked understanding/attention to semantics, when developed
• (Fairly mature wrt performance for broad restricted cases, e.g., magic sets.)
5/30/2006 5/30/2006Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 55 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 56
Ubiquity of Priorities Well Founded Semantics: Implementations of
in Commercially Important Rules -- and Ontologiesnon-stratified general case
• Updating in relational databases
• Commercial implementations that handle non-stratified – more recent fact overrides less recent fact
general case: • Static rule ordering in Prolog
– rule earlier in file overrides rule later in file– XSB Prolog (backward inferencing) is the currently most
• Dynamic rule ordering in production rule systems (OPS5)important and mature
– “meta-”rules can specify agenda of rule-firing sequence – Not many others (?none)
• Event-Condition-Action rule systems rule ordering
– often static or dynamic, in manner above
• There are a few other research implementations that handle • Exceptions in default inheritance in object-oriented/frame systems
non-stratified general case: – subclass’s property value overrides superclass’s property value,
– Smodels (exhaustive forward inferencing) is the e.g., method redefinitions
currently most important • All lack Declarative KR Semantics
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 57 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 58
Semantical KR Approaches to Prioritized LP Courteous LP: the What
The currently most important for Semantic Web are: • Updating/merging of rule sets: is crucial, often generates conflict.
1. Courteous LP • Courteous LP’s feature prioritized handling of conflicts.
• Specify scope of conflict via a set of pairwise mutual exclusion constraints.• KR extension to Ordinary LP
– E.g., ⊥ ← discount(?product,5%) ∧ discount(?product,10%) .
• In RuleML, since 2001
– E.g., ⊥ ← loyalCustomer(?c,?s) ∧ premiereCustomer(?c,?s) .
• Commercially implemented and applied – Permit classical-negation of atoms: ¬p means p has truth value false
– IBM CommonRules, since 1999 • implicitly, ⊥ ← p ∧ ¬p for every atom p.
2. Defeasible Logic • Priorities between rules: partially-ordered.
• Closely related to Courteous LP – Represent priorities via reserved predicate that compares rule labels:
– Less general wrt typical patterns of prioritized conflict handling • overrides(rule1,rule2) means rule1 is higher-priority than rule2.
needed in e-business applications • Each rule optionally has a rule label whose form is a functional term.
– In progress: theoretical unification with Courteous LP • overrides can be reasoned about, just like any other predicate.
5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 59 5/30/2006 Copyright 2006 by Benjamin Grosof and Mike Dean. All Rights Reserved 60
10

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin