- From: Axel Polleres <axel.polleres@urjc.es>
- Date: Wed, 17 May 2006 17:12:58 +0200
- To: public-rif-wg@w3.org
http://www.w3.org/2005/rules/wg/track/actions/15
http:/www.w3.org/2006/05/09-rif-minutes.html
I follow Hassan's approach by using his scheme to apply the RIFRAF criteria
(http://www.w3.org/2005/rules/wg/wiki/Rulesystem_Arrangement_Framework)
to DLV. Thanks to Giovambattista Ianni from the DLV team for assisting
me with this analysis.
Whereever I didn't find the current RAF discriminators appropriate or
sufficient, or where more explanations should be added in RAF in my
opinion, (which was, I guess the primary sense of this exercise ;-) ) I
added comments preceeded by
"--> comment axel:"
In total I found the exercise quite useful for analysing the RAF and
hope the comments are helpful.
Short Introduction:
DLV is a mostly academic rule engine which supports several extensions
of Datalog following the so-called Answer Set Programming (ASP)
Paradigm, see [1,2]. ASP extends Datalog with several useful features
such as disjunction in the head, negation as failure under the stable
model semantics, strong negation, aggregates, strong and weak
constraints, external predicates and rule templates. The paradigm has
proven a valuable rule and query language in practical applications
such as information integration. Especially remarkable are recent
extensions in the Semantic Web realm, such as dl-predicates, and its
generalization dlhex-predicates [3,4].
While many of the DLV features might not be of immediate importance to
RIF, at least in phase 1, some other might play a role, such as , how
to deal with unstratified negation, hybrid vs. homogeneous integration
with OWL, aggregates.
In examples, I use the concrete syntax of the DLV system
http://www.dlvsystem.com
and its extensions
dlt (which supports rule templates and higher-order syntax),
http://www.mat.unical.it/ianni/wiki/dlt
dlvex (external built-ins)
http://www.mat.unical.it/ianni/wiki/dlvex
dlvhex (higher-order external built-ins, OWL and RDF querying), see
http://con.fusion.at/dlvhex/
The core of the language is very similar to Prolog and thus I assume
that less explanation is needed.
Another extension, OntoDLV (which supports frame syntax, taxonomies,
typing, and modularization of rules)
http://www.exeura.it/ontodlv
will not be covered in all details, since I am not that familiar with
it, but, if there is interest in the WG, I could extend the discussion
in this direction.
axel
1. C. Baral. Knowledge Representation, Reasoning, and Declarative
Problem Solving. Cambridge University Press, Cambridge, UK, 2003.
2. DLV: http://www.w3.org/2005/rules/wg/wiki/DLV
3. T. Eiter, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Combining
answer set programming with description logics for the Semantic Web.
In Proceedings KR-2004, 2004.
4. Thomas Eiter, Giovambattista Ianni, Roman Schindlauer, and Hans
Tompits. A uniform integration of higher-order reasoning and
external evaluations in answer set programming. In Proceedings
of the 19th International Joint Conference on Artificial
Intelligence (IJCAI-05), 2005
-------------------------------------------------------------------
CLASSIFYING DLV AS RULE SYSTEM
===== SYN: SYNTACTIC DISCRIMINATORS =====
SYN.1. RESTRICTED VS. UNRESTRICTED USE OF LOGIC VARIABLES
SYN.1.1. SINGLE OCCURRENCE VS. MULTIPLE OCCURRENCE (IMPLICIT VARIABLE
EQUALITY)
[DLV] Variables (denoted by capital letters like in Prolog)
are scoped over rules, no global variables, except
constant definitions.
Variables are untypedin core DLV.
OntoDLV supports typing.
Typing could be also added by adding
built-in type-checking predicates with dlvex.
--> comment axel: Also concerning the recent mailinglist
discussions I miss an own category for typed vs.
untyped variables in the RIFRAF classification.
SYN.1.2. RANGE-RESTRICTED RULES (NO HEAD-ONLY VARIABLES)
VS. NON-RANGE-RESTRICTED RULES
[DLV]
Variables usage is restricted by only allowing "safe" variable
use, i.e. each variable has to appear in at least one
positive, non-built-in body atom.
example:
ok:
% A pc member who is author of a paper with the same
% keyword is a candidate for reviewing paper P:
cand(X,P) :- kw(P,K), pc(X), url(U),
isAuthorOf(X,P1), keyword(P1,K).
cand(X,P) :- kw(P,K), pc(X), url(U),
isAuthorOf(X,P1), keyword(P1,K), P != P1.
unsafe:
% The variables here are not range-restricted,
% since they only appear in builtin atoms:
ordered(X,Y,Z) :- X>Y, Y>Z.
% The variable X here is not range-restricted,
% since they only in negation as failure atoms:
cand1(X,P) :- paper(P), not pc(X).
In some cases, the range restrictions might be relaxed,
i.e. built-in predicates with functional dependencies among
their may have different allowed binding patterns:
e.g.
p(Y) :- a(X), Y = X + 1.
and
p(X) :- a(Y), Y = X + 1.
are safe as well.
SYN.1.3. (FURTHER RESTRICTIONS FROM STATIC ANALYSIS RESEARCH)
--> comment axel: unclear, please explain?
SYN.2. PREDICATE VARIABLES PERMITTED VS. NOT PERMITTED
* SECOND-ORDER SYNTACTIC SUGAR ALLOWING VARIABLES IN PREDICATE
POSITIONS OF QUERIES OR RULE BODIES AND POSSIBLY RULE HEADS
(FURTHER GENERALIZED TO FUNCTION AND EVEN ATOM POSITIONS IN
[HTTP://WWW.W3.ORG/SUBMISSION/SWSF-SWSL/#SWSL-RULES-HILOG])
[DLV]
DLV in it's core language does not support 2nd-order style use
of variables.
The DLT extenstion allows the defnition of rule templates and
the use of frame-style syntax inspired by F-Logic.
e.g.
X : C :- X : D, D[subClassOf->C].
(note that not full F-Logic is supported at the moment)
SYN.3. MONOTONIC LLOYD-TOPOR EXTENSIONS ALLOWED VS. NOT ALLOWED
* SYNTACTIC SUGAR FOR EXTENDING HORN LOGIC WITH DISJUNCTION IN RULE
BODIES AS WELL AS CONJUNCTION AND CLASSICAL IMPLICATION IN RULE
HEADS [HTTP://WWW.W3.ORG/SUBMISSION/SWSF-SWSL/#SWSL-RULES-MON-LT]
[DLV]
DLV in it's core language does not support disjunction
in rule bodies or conjunction and implication in rule heads,
a prototype for a precompiler for nested expressions
(similar in spirit to LT transformation, but allows full
freedom of expressions allowed in head and body,
except quantifiers) exists at:
http://www.cs.uni-potsdam.de/~torsten/nlp/
--> comment axel: this shows us that there rewritings
beyond extensions of Lloyd-Topor, which also allow
formulae in the rule head. Has not been considered
in current RAF, but might be worthwhile at least for phase 2
SYN.4. EXPLICIT VS. IMPLICIT RULE SCOPE
* ALLOWING FORMULAS AND/OR NAMES DENOTING WHAT HAS BEEN CALLED
MODULES, CONTEXTS, RULESETS, OR MODELS
[HTTP://WWW.ISI.EDU/~ARGOS/MATTHEW/TRIPLE_BY_EXAMPLE.HTML]
[DLV]
DLV core no.
DLT templates allow a particular form of module/template
definitions.
SYN.4.1. SLOTTED (KEYED, ROLE-NAMED) VS. POSITIONAL ARGUMENTS
* ALLOWING N-ARY ATOMS WITH A SET OF N 'ATTRIBUTE=VALUE' PAIRS
AS IN RDF/OWL PROPERTIES, F-LOGIC METHODS, AND OBJECT-ORIENTED
SYSTEMS [HTTP://WWW.RULEML.ORG/INDOO]
[DLV]
DLV core no.
DLT extension allow the use of F-Logic frame syntax, see above.
SYN.5. WEBIZED VS. NON-WEBIZED NAMES
* ALLOWING URIS AS OIDS FOR CONSTANTS, FUNCTIONS, SLOTS, PREDICATES,
CLASSES, AND/OR LABELS [HTTP://WWW.W3.ORG/2000/10/SWAP/PRIMER.HTML]
[DLV]
DLV Core No (except in form of strings)
DLVHEX extension allows namespace definitions for abbreviation
(treating namespaces a la RDF)
===== SES: SYNTACTIC-ENTAILING-SEMANTIC DISCRIMINATORS =====
SES.1. HOMOGENEOUS (BODY HAS SINGLE EXPRESSIVENESS CLASS) VS. HYBRID (BODY
HAS TWO EXPRESSIVENESS CLASSES) RULES
[DLV] does supports not support the splitting body in a
resolution and a query part, as Harold called this.
--> comment axel: however, I am not sure whether this discriminator is
really applicable, in principle, what Harold mentioned in his
comment to Hassan:
"'constraints' (e.g., solved by DL engines) goals."
are achievable by dlvhex predicates.
--> comment axel (alternative): In case this refers to the terms
homogeneous vs. heterogeneous ontology integration as described in
http://rewerse.net/deliverables/m12/i3-d3.pdf
(which would IMO probably be the better discriminator here,
I'd reformulate this as follows:
[DLV] the DLVHex extension follows hybrid ontology integration
via hex-predicates, these are external predicates to interface by
querying and feeding back factual knowledge to ontologies in
OWL, see [3,4].
SES.2. FACT-ONLY (DATABASE TABLES) VS. RULE-ONLY VS. FACT-AND-RULE BASES
[DLV] facts and rules, as well as ODBC interface to support database
factual integration.
SES.2.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS
(ALSO UNDER "VARIABLE-FUL VS. ... CLAUSES")
[DLV]
DLV facts are ground only, non-ground facts amount to
unsafe rules and are thus forbidden
SES.3. FUNCTION-FUL (FO HORN LOGIC) VS. FUNCTION-FREE (FO DATALOG)
[DLV] DLV does not support function symbols and is based on
extensions of Datalog.
SES.3.1. FUNCTION ARITY/ARITIES
[DLV] DLV does not support function symbols and is based on
extensions of Datalog.
SES.3.2. FIXED VS. UNFIXED FUNCTION NESTING DEPTH
[DLV] DLV does not support function symbols and is based on extensions
of Datalog.
SES.3.3. UNINTERPRETED VS. INTERPRETED FUNCTIONS
[DLV] External functions are supported by external builtin predicates
(dlvex-extension). Variables use is limited in these to safe
variable usage. A list of custom external builtin predicates are
currently publicly available at
http://www.mat.unical.it/ianni/wiki/dlvex
External interpreted functions can be used like normal
predicates and support different binding patterns.
--> comment axel: I didn't find anything on binding patterns in the
descriminators, but most systems which support interpreted
functions support such different binding patterns,
e.g. that the interpreted function X = Y + Z is used with the
binding patterns "bfb","bbf","fbb", where "b" stands for
'bound' and "f" for 'free'. Probably this should be added in
the discriminators for interpreted functions?
SES.4. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) CLAUSES
SES.4.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS
(ALSO UNDER "FACT-ONLY ... BASES")
[DLV] Variables are allowed only if guarded by a positive body atom,
see SYN1.2
--> comment axel: there seems to be an overlap with this
discriminator with SYN1.2 and SES2.1
SES.5. PREDICATE ARITY/ARITIES
[DLV] Each predicate may only appear with one arity, use of the same
predicate with different arities causes an error.
SES.6. NUMBER OF PREMISES IN RULES
[DLV]
Rules are of the form:
h_1 v ... h_k :- b_1, ... b_m, not c_1, ..., not c_n
i.e. he premise of a rule consists of an unlimited number of positive
or default negated classical literal and external predicates,
interpreted conjunctively, the conclusion consists of a discjunction
of classical literals.
SES.7. LABELED (ANCHORED, OIDED) VS. UNLABELED CLAUSES
[DLV] rules are not labeled in dlv.
SES.7.1. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF USER PREDICATES
[DLV] rules and facts are not labeled in dlv, neither are predicate
arguments.
--> comment axel: Please clarify this criterion! If you mean named
attributes in relations, I don't see this as a subcriterion
of labels for rules.
What exactly is meant by "user predicates"?
SES.7.2. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF
PRIORITY-GIVING SYSTEM PREDICATE 'OVERRIDES' (CF. SCLP)
[DLV] rules are not labeled in dlv, thus not directly.
However, priorities can be specified in terms of weak
constraints instead, which are defined in terms of rules
with an empty head plus a violation "priority",
e.g.
% Avoid to have a paper assigned to a coauthor of the author
:~ coauthor(A,A1), paper(P,A), reviewer(P,A1). [1:1]
% However: even worse is to assign a paper to a family member:
:~ relatives(A,A1), paper(P,A), reviewer(P,A1). [1:2]
Here, [w:l] denote vialation value (w) and priority level (l).
DLV prefers answer sets with a low vialation values.
--> comment axel: Please clarify this criterion! The current
formulation seems to suggest a particular framerwork for
modeling preferences/priorities, while as we see for instance in
the example there are many options for this.
SES.8. CERTAIN VS. UNCERTAIN CLAUSES AND ATOMS
[DLV] supports qualitative uncertainty by disjuntive rule heads and
unstratified negation. quantitative uncertainty in terms of
probabilities or fuzzy conclusions is not supported.
===== SEM: SEMANTIC DISCRIMINATORS =====
SEM.1. TERMINATING (ALL QUERIES TERMINATE) VS. NON-TERMINATING (AT
LEAST ONE QUERY DOES NOT TERMINATE) RULEBASES
[DLV] DLV, including DLT guarantee termination.
DLVHEX extension (external reasoner/query engine call) depends on
whether external reasoner/query engine guarantees termination.
DLVEX (external functions) might cause non-termination if safety
checking is disabled (if you respect the particular range
restriction rules, everything is fine)
Intuitively
INT(1).
INT(X) :- INT(Y), #succ(Y,X).
has an infinite model if #succ is defined as 'X is the successor
of Y'.Syntactic restrictions (which can be disabled)
prevent this problem.
--> comment axel: obviously even simple interpreted functions can
cause non-termination even for a datalog based engine, which
makes such syntactic restrictions useful. In what way will
we be able to describe such syntactic restrictions in RIF?
It is probably important to also be able to exchange
such syntactic restrictions (which e.g. prohibit certain uses of
recursvie rules in a formally defined way.
SEM.2. FINITE-MODEL VS. INFINITE-MODEL RULEBASES (CF. DECIDABILITY)
[DLV] DLV is based on datalog and stable model semantics
(i.e. finite Herbrand models)
As for extensions, see above. In practice only DLVEX may fall in
undecidability and only if range restrictions are disabled.
SEM.3. MODALITY/INTENTIONALITY (BEYOND FOL)
[DLV] There are no modalities in DLV. DLVHEX can in principle plug some
external atom that mimics a modal operator.
===== PRAG: PRAGMATIC DISCRIMINATORS =====
PRAG.1. INFERENCE CONTROL
PRAG.1.1. FORWARD CHAINING VS. BACKWARD CHAINING VS. BIDIRECTIONAL
CHAINING
[DLV] Positive rule sets in DLV are evaluated in an intelligent
grounding+forward-chaining manner. The evaluation of disjunctive
rules and rules with unstratified negation cannot be categorized
in these terms but rather underlies a backtracking model-checking
algorithm more similar to Davis-Putnam style SAT solvers.
PRAG.1.2. INCREMENTAL VS. EXHAUSTIVE
[DLV] Exhaustive.
--> comment axel: I am not sure about how this criterion fits to
forward-chaining but several answer sets. If it concerns the
strategy of forward-chaining evaluation, then I'd say. However,
DLV incrementally computes all stable models,
i.e. incrementally, whereas one could also compute ALL and only
give the cautious entailments in ALL stable models.
PRAG.2. COMPLEXITY
DLV and it's underlying core language have
P/EXPTIME complexity for positive rules (data/program complexity)
NP/NEXPTIME complexity for nondisjunctive rules (data/program compl)
Sigma_P^2/NEXPTIME complexity for disj. rules (data/program compl)
PRAG.3. INTEROPERABILITY
[DLV]
- Interoperability with DL reasoners by dl-predicates in DLVHEX.
- Plugins for other reasoners can be added via a generic API
- Import of RDF data in DLVHEX.
- Interoperability with SWL databases via ODBC.
PRAG.3.1. ANNOTATIONS (INCLUDING CONTROLLED ENGLISH)
[DLV] Annotations are limited to comments.
PRAG.3.2. TEST CASES
[DLV] Mostly academic. However, practical adoption increasing.
Answer-Set Programming has been successfully applied to many areas
including
* configuration,
* information integration,
* security analysis,
* agent systems,
* semantic web, or
* planning.
see: http://www.kr.tuwien.ac.at/projects/WASP/showcase.html
for details. There is also a benchmark suite, although I am not sure
whether this is publically available.
--> comment axel: I am not sure what you put here, at least
"test cases" do not seem to be a proper "discriminator", unless
you put a set of several practical test caes and ask: "Can this be
expressed/solved in your rule language/engine?" I.e. the WG should
provide these test cases derived from these discriminators, yes?
PRAG.3.3. MAPPINGS
[DLV] some of the extensions (e.g. rule templates, nested
expressions) are mappable back to DLV core language directly,
others DLVHEX, DLVEX external interpreted functions and external
reasoner calls obviously not.
--> comment axel: ???? I still don't really sure to understand that
criterion, even after Harold's comment: "Does the system have
pre-defined mappings between various of it own sublanguages?"
Please clarify if I misinterpreted this.
PRAG.3.3.1. WITHIN EXPRESSIVE EQUIVALENCE CLASSES ("CLUSTERS")
--> comment axel: ???? see above.
PRAG.3.3.2. BETWEEN EXPRESSIVE EQUIVALENCE CLASSES (IMPERFECT OR
"LOSSY")
--> comment axel: ???? see above. I think for some extensions this
discriminator cannot be answered yes or no. Depends how you
define lossy/imperfect.
PRAG.3.4. (FURTHER INTEROPERABILITY DISCRIMINATORS SHOULD GO HERE)
--> comment axel: Features, I didn't find a category for:
- preference/priorities of rules: DLV's weak constraint and several
other ASP extensions supports a certain kind of preference definition
between rule derivations, which can be adopted in case of conflicting
conclusions. I'd assume that this is an important feature also
supported by other rule languages? (P.S.: priorization/preference
frameworks for rules probably would deserve an own ontology to be
analyzed in this WG, although for sure not in phase 1)
- Aggregates: In which discriminator do features such as the use of
aggregates in rule bodies (e.g. sum/avg/max/min) go? (yes, this is
also probably phase 2)
Received on Wednesday, 17 May 2006 15:13:22 UTC