A set of views defined by selection queries splits a database relation into sub-relations, each containing a subset of the original rows. This decomposition into horizontal fragments is lossless when the initial relation can be reconstructed from the fragments by union. In this paper, we consider horizontal decomposition in a setting where some of the attributes in the database schema are interpreted over a specific domain, on which a set of special predicates and functions is defined. We study losslessness in the presence of integrity constraints on the database schema. We consider the class of conditional domain constraints (CDCs), which restrict the values that the interpreted attributes may take whenever a certain condition holds on the non-interpreted ones, and investigate lossless horizontal decomposition under CDCs in isolation, as well as in combination with functional and unary inclusion dependencies.

We present a natural language genera-tion system which supports the incremen-tal specification of ontology-based queries in natural language. Our contribution is two fold. First, we introduce a chart based surface realisation algorithm which supports the kind of incremental process-ing required by ontology-based querying. Crucially, this algorithm avoids confusing the end user by preserving a consistent ordering of the query elements through-out the incremental query formulation pro-cess. Second, we show that grammar based surface realisation better supports the generation of fluent, natural sounding queries than previous template-based ap-proaches. 1

Automated support to enterprise modeling has increasingly become a subject of interest for organizations seeking solutions for storage, distribution and analysis of knowledge about business processes. This interest has recently resulted in approving the standard for specifying Semantics of Business Vocabulary and Business Rules (SBVR). Despite the existence of formally grounded notations, up to now SBVR still lacks a sound and consistent logical formalization which would allow developing automated solutions able to check the consistency of a set of business rules. This work reports on the attempt to provide logical foundations for SBVR by the means of defining a specific first-order deontic-alethic logic (FODAL). The connections of FODAL with the modal logic QK and the description logic 𝒜ℒ𝒞𝒬ℐ have been investigated and, on top of the obtained theoretical results, a special tool providing automated support for consistency checks of a set of 𝒜ℒ𝒞𝒬ℐ-expressible deontic and alethic business rules has been implemented.

The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.

We study a general framework for query rewriting in the presence of an arbitrary first-order logic ontology over a database signature. The framework supports deciding the existence of a safe-range first-order equivalent reformulation of a query in terms of the database signature, and if so, it provides an effective approach to construct the reformulation based on interpolation using standard theorem proving techniques (e.g., tableau). Since the reformulation is a safe-range formula, it is effectively executable as an SQL query. At the end, we present a non-trivial application of the framework with ontologies in the very expressive ALCHOIQ description logic, by providing effective means to compute safe-range first-order exact reformulations of queries.

Editors/Supervisors: Walsh T

Editors/Supervisors: Walsh T

After an introduction where the notion of ontology will be introduced in a rigorous way as a set of constraints over legal database instances playing the role of a conceptual model or of a set of dependencies , the tutorial will be divided in three parts. In the first part, we will discuss, mostly driven by examples, the role of ontologies in information systems design and the advantages and the challenges when adopting a formal approach based on logics. In the second part, a real-world tool for ontology design will be used to see the "logic" in action. In the third and most important part, we will discuss the use for information access of ontologies in data intensive scenarios based on database technologies, based on a scenario where a logic-based ontology mediates between the user information need and the data structured in the source database. The tutorial will emphasise the advantages of adopting a logic-based approach to the use of ontologies in data intensive applications, and the challenges that the research should still face to make this approach feasible and scalable in association with current database technology. The audience can be of both database researchers and practitioners, since I will try to explain all the concepts through examples and the central demo, although the concepts that the audience will at the end get will be non-trivial ones. The main goal of this tutorial is to let the audience understand haw these novel technologies are non-trivial, but useful in perspective and worthwhile researching; I will also show that there are already some data intensive scenarios where a rigorous ontology-based approach is already applicable with success; at the same time, I will warn about the wrong usages of ontology-based technologies.

The Resource Description Framework (RDF [Hayes, 2004]) is a W3C standard language for representing information about resources in the World Wide Web; RDF provides a common framework for expressing this information so it can be exchanged between applications without loss of meaning. In this tutorial, RDF will be presented as a data model in the database sense. Its motivations will be analysed, and its current formal status revised. The data model can be understood both from a graph theoretical perspective and from a logical perspective. While the former has been the focus of most theoretical (see, e.g., [Gutierrez et al., 2004]) and practical approaches to RDF, the logical view of RDF has been mostly neglected by the community so far. Two provably correct (w.r.t. the normative W3C definitions of RDF [Hayes, 2004]) logical reconstructions of RDF will be presented, by reducing (a fragment of) it to a classical first-order framework suitable for knowledge representation (first developed in [de Bruijn et al., 2005]), and by encoding the full RDF data model in the HiLog logic introduced by Kifer et al. several years ago [Chen et al., 1993]. An emphasis will be given to three main characteristics of RDF: the presence of anonymous bnodes, the non-well-foundedness of the basic rdf:type relation, and the presence of the RDF vocabulary in the mode itself.In the second part of the tutorial, the relation of the logical reconstructions of RDF with a database perspective will be introduced. An RDF database is seen as a model of a suitable theory in first order logic or in HiLog. While in the pure RDF sense the two approaches are equivalent, it will be shown how the difference becomes relevant whenever additional constraints (e.g., in the form of ontologies or database dependencies) are introduced in the framework. In order to allow for additional constraints (e.g., in the standard W3C OWL-DL ontology language [Patel-Schneider et al., 2004]) while keeping the framework first order, only a fragment of RDF can be considered; this restriction is not needed if the framework is in HiLog (see, e.g., [Motik, 2005]). Various complexity and decidability results will be summarised. In the last part of the tutorial, the W3C standard query language for RDF (SPARQL [Prud'hommeaux and Seaborne, 2006]) will be presented. SPARQL is currently a candidate recommendation. The core of SPARQL is a conjunctive query language, with the added complication that the data model includes existential information in the form of bnodes, and that bnodes may be returned by the query. The formal semantics of the core query language will be given. The problem of the canonical representation of the answer set will be introduced, since bnodes introduce a behaviour similar to the null values in SQL. Complexity results for query answering will be given for different cases. Finally, the possible extensions of SPARQL with various classes of constraints will be discussed.

1Bolzano 2Liverpool 3Liverpool 4Bolzano

This paper presents an approach to answering queries over an ontology modelled using a description logic. The ontology acts as a global schema, providing a declarative description of the concepts of the domain, the instances of which are stored in (potentially many) object-wrapped sources. Queries are expressed using terms from the rich vocabulary of the ontology, and are translated into an equivalent calculus expression, which references only the objects available in the source databases. The query is then optimized on the basis of information from the ontology and the source databases. Distinctive features of the approach include: the use of the expressive ALCQI description logic, which supports both ontology definition and query expression; the adoption of a global-as-view approach to relating the ontology to the sources; and the use of the ontology to direct semantic optimization of queries phrased over specific sources. The approach is being developed in, and is illustrated using examples from, bioinformatics.

The ESPRIT Project DWQ (Foundations of Data Warehouse Quality) aimed at improving the quality of DW design and operation through systematic enrichment of the semantic foundations of data warehousing. Logic-based knowledge representation and reasoning techniques were developed to control accuracy, consistency, and completeness via advanced conceptual modeling techniques for source integration, data reconciliation, and multi-dimensional aggregation. This is complemented by quantitative optimization techniques for view materialization, optimizing timeliness and responsiveness without losing the semantic advantages from the conceptual approach. At the operational level, query rewriting and materialization refreshment algorithms exploit the knowledge developed at design time. The demonstration shows the interplay of these tools under a shared metadata repository, based on an example extracted from an application at Telecom Italia.

E Franconi, G De Giacomo, IR Horrocks, DL McGuinness, W Nutt, PF Patel-Schneider, CA Welty; Conferences. Report on the 1998 International Workshop on Descriptio

A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties. The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL -- able to express interval temporal networks -- together with the non-temporal logic F -- a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF. The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.