The W⁴ Project

Well-founded semantics for the World Wide Web

(c) Carlos Viegas Damásio

The W4 project aims at developing Standard Prolog interoperable tools for supporting distributed, secure, and integrated reasoning activities in the Semantic Web.

• Development of Prolog technology for XML, RDF and RuleML.

• Development of a General Semantic framework for RuleML including default and explicit negation, supporting uncertain, incomplete, and paraconsistent reasoning.

• Development of distributed query evaluation procedures for RuleML based on tabulation, according to the previous semantics.

• Development of Dynamic Semantics for evolution/update of Rule ML knowledge bases.

• Integration of different semantics in Rule ML (namely, Well-founded Semantics, Answer Sets, Fuzzy Logic Programming, Annotated Logic Programming, and Probabilistic Logic Programming).

• THE adopted semantics for definite, acyclic and (locally) stratified logic programs.
• Defined for every normal logic program, i.e. with default negation in the bodies.
• Polynomial data complexity.
• Efficient existing implementations, namely the SLG-WAM engine implemented in XSB.
• Good structural properties.
• It has an undefined truth-value...
• A lot of extensions are built over WFS, capturing paraconsistent, incomplete and uncertain reasoning.
• Update semantics via Dynamic Logic Programs
• It can be readily "combined" with DBMSs, Prolog and Stable Models engines.

I have proposed  well-founded semantics and its extensions as an appropriate semantics for the Rule Markup Language in the Dagstuhl Seminar Rule Markup Techniques for the Semantic Web, organized by H. Boley, B. Grosof, S. Tabet, and G. Wagner.

The slides of my talk at Dagstuhl provide a non-technical overview of the available theories, technologies and potential applications.

The success of the World Wide Web is unquestionable promoting and encouraging new forms of communication, organization and making business.  The World Wide Web has observed an exponential growth of content but it faces a dilemma: most of the documents are for human consumption and are not machine-understandable. Consequently, a large number of activities cannot be fully automated while there is no common way of expressing information or knowledge about the contents of documents and data available in the Web. The W3C launched recently the Semantic Web Activity in order to address theses issues and shape the Web of the future.

The eXtensible Markup Language provides a way of organizing data and documents in a structured and universally accepted format. However, the tags used have no predefined meaning. The W3C has proposed the Resource Description Framework (RDF) for exposing the meaning of a document to the Web community of people, machines, and intelligent agents. 

Conveying the content of documents is just a first step for achieving the full potential of the Semantic Web. Additionally, it is mandatory to be able to reason with and about information spread across the World Wide Web. The applications range from electronic commerce applications, data integration and sharing, information gathering, security access and control, law, diagnosis, B2B, and of course, to modeling of business rules and processes. Rules provide the natural and wide-accepted mechanism to perform automated reasoning, with mature and available theory and technology. This has been identified as a Design Issue  for the Semantic Web, as clearly stated by Tim Berners-Lee et al in [The Semantic Web, Scientific American, May 2001]:

• “For the semantic web to function, computers must have access to structured collections of information and sets of inference rules that they can use to conduct automated reasoning.”

• “The challenge of the Semantic Web, therefore, is to provide a language that expresses both data and rules for reasoning about the data and that allows rules from any existing knowledge-representation system to be exported onto the Web.”

• “Adding logic to the Web—the means to use rules to make inferences, choose courses of action and answer questions—is the task before the Semantic Web community at the moment.”

 The RuleML initiative aims at defining a core format for rule interchange, resorting to XML.  Several forms have been identified, namely derivation rules, transformation rules, integrity-constraints, and reaction rules (or event-condition-action rules). For instance, in a business environment, derivation rules can be used to express marketing policies, client discounts and management, accounting rules, and security policies. Transformation rules may be used to calculate interests or to produce documents in specified formats. Integrity constraints describe invariants (something that must always hold) that are permanently put in force and checked, guaranteeing soundness and coherence of the whole system. A good example is that no bank account should be left overdrawn after any transaction. Last but not the least, reaction rules can specify the behavior of the system, communication and flow of information across several applications and agents (human or not). A typical business rule is that a receipt should be issued and sent to every client after receiving the corresponding payment. This involves knowing that a client has paid (triggered by an external event), sending the receipt (probably by e-mail), and updating the internal knowledge or database.

Modeling business rules and processes is an important and adequate application for the Web rule based technology, due to the spectrum of practical problems that need to be addressed. This may involve integrating several reasoning forms and respective inference mechanisms, namely classical logic, non-monotonicity, uncertainty, knowledge updating and evolution, conflict resolution, preferences and paraconsistency in a scalable reactive rule real-time business environment. The appropriate reasoning forms and tools to use will be selected by the more relevant practical requirements for modeling business processes.

The W4 project will resort to proposals, standards and recommendations emanating from the W3C and related initiatives, in particular XML, RDF, OWL and RuleML. As a result, it is expected that the application to modeling of business processes will help to understand and clarify some of the still open issues of RuleML and at the same time provide a test-bed for this new fundamental emerging technology.

The use of logic programming technological and theoretical developments may bring new insights,  issues, and solutions to this promising area of investigation and commercial applications. The W4 project aims at developing logic programming tools to atack the following topics:

• Development of Prolog technology for XML, RDF and RuleML.

• Development of a General Semantic framework for RuleML including default and explicit negation, supporting uncertain, incomplete, and paraconsistent reasoning.

• Development of distributed query evaluation procedures for RuleML based on tabulation, according to the previous semantics.

• Development of Dynamic Semantics for evolution/update of Rule ML knowledge bases.

• Integration of different semantics in Rule ML (namely, Well-founded Semantics, Answer Sets, Fuzzy Logic Programming, Annotated Logic Programming, and Probabilistic Logic Programming).

There will be availabe very soon the following tools developed for XSB Prolog (2.5 or later), but can be readily adapted for other Prolog systems:

• Non-validating XML parser with support for XML Namespaces, XML Base, complying to the recommendations of XML Info Sets. It can read US-ASCII, UTF-8, UTF-16, and ISO-8859-1 encodings.
• Converter of XML to Prolog terms.
• RuleML compiler for the hornlog fragment of the language extended with default and explicit negation, as well as update program syntax.
• Query evaluation procedures under the Paraconsistent Well-founded Semantics with Explicit Negation [C. V. Damásio and L. M. Pereira, A paraconsistent semantics with contradiction support detection. In J. Dix, U. Furbach and A. Nerode (eds), Logic Programming and NonMonotonic Reasoning, 4th International Conference, LPNMR'97, Lecture Notes in Artificial Intelligence 1265, Springer-Verlag, Dagstuhl, Germany, July 1997, pp. 224-243. © Springer-Verlag]