Because widely used real-world ontologies are often complex and large, one important challenge has emerged: designing tools for users to focus on sub-ontologies corresponding to their specific interests. To this end, various modules have been introduced to provide concise ontology views. This work concentrates on extracting deductive modules that preserve logical entailment over a given vocabulary. Existing deductive module proposals are either inefficient from a computing point of view or unsatisfactory from a quality point of view because the modules extracted are not concise enough. For example, minimal modules guarantee the most concise results, but their computation is highly time-consuming, while ⊥⊤∗-modules are easy to compute but usually contain many redundant items. To overcome computation cost and lack of quality, we propose to compute two kinds of deductive modules called pseudo-minimal modules and complete modules for EL-ontology. Our deductive module definitions rely on associating a tree representation with an ontology, and their computation is based on SAT encoding. Our experiments on real-world ontologies show that our pseudo-minimal modules are indeed minimal modules in almost all cases (98.9%), and computing pseudo-minimal modules is more efficient (99.79 times faster on average) than the state-of-the-art method Zoom for computing minimal modules. Also, our complete modules are more compact than ⊥⊤∗-modules, but their computation time remains comparable. Finally, note that our proposal applies to EL-ontologies while Zoom only works for EL-terminologies.

We present a method for extracting general modules for ontologies formulated in the description logic ALC. A module for an ontology is an ideally substantially smaller ontology that preserves all entailments for a user-specified set of terms. As such, it has applications such as ontology reuse and ontology analysis. Different from classical modules, general modules may use axioms not explicitly present in the input ontology, which allows for additional conciseness. So far, general modules have only been investigated for lightweight description logics. We present the first work that considers the more expressive description logic ALC. In particular, our contribution is a new method based on uniform interpolation supported by some new theoretical results. Our evaluation indicates that our general modules are often smaller than classical modules and uniform interpolants computed by the state-of-the-art, and compared with uniform interpolants, can be computed in significantly shorter time. Moreover, our method can be used for, and in fact, improves the computation of uniform interpolants and classical modules.

Answering a Why-Not question consists in explaining why a query result does not contain some expected data, called missing answers. This paper focuses on processing Why-Not questions in a query-based approach that identifies the culprit query components. Our first contribution is a general definition of a Why-Not explanation by means of a polynomial. Intuitively, the polynomial provides all possible explanations to explore in order to recover the missing answers, together with an estimation of the number of recoverable answers. Moreover, this formalism allows us to represent Why-Not explanations in a unified way for extended relational models with probabilistic or bag semantics. We further present an algorithm to efficiently compute the polynomial for a given Why-Not question. An experimental evaluation demonstrates the practicality of the solution both in terms of efficiency and explanation quality, compared to existing algorithms.

One important issue in modern database applications is supporting the user with efficient tools to debug and fix queries because such tasks are both time and skill demanding. One particular problem is known as Why-Not question and focusses on the reasons for missing tuples from query results. The EFQ platform demonstrated here has been designed in this context to efficiently leverage Why-Not Answers polynomials , a novel approach that provides the user with complete explanations to Why-Not questions and allows for automatic, relevant query refinements.

International audience

In this demo we will showcase a research prototype for processing queries and updates on large XML documents. The prototype is based on the idea of statically and dynamically partitioning the input document, so to distribute the computing load among the machines of a Map/Reduce cluster. Attendees will be able to run predefined queries and updates on documents conforming to the XMark schema, as well as to submit their own queries and updates.

This paper presents an XML partitioning technique that allows main-memory query engines to process a class of XQuery queries, that we dub iterative queries, on arbitrarily large input documents. We provide a static analysis technique to recognize these queries. The static analysis is based on paths extracted from queries and does not need additional schema information. We then provide an algorithm using path information for partitioning the input documents of iterative queries. This algorithm admits a streaming implementation, whose effectiveness is experimentally validated.

This paper presents a novel static analysis technique to detect XML query-update independence, in the presence of a schema. Rather than types, our system infers chains of types. Each chain represents a path that can be traversed on a valid document during query/update evaluation. The resulting independence analysis is precise, although it raises a challenging issue: recursive schemas may lead to inference of infinitely many chains. A sound and complete approximation technique ensuring a finite analysis in any case is presented, together with an efficient implementation performing the chain-based analysis in polynomial space and time.

While projection techniques have been extensively investigated for XML querying, we are not aware of applications to XML updating. This paper investigates a projection based optimization mechanism for XQuery Update Facility expressions in the presence of a schema. This paper includes a formal development and study of the method as well as experiments testifying its effectiveness.

The management of temporal data is a crucial issue in many applications. Recently, XML has become the standard for data exchange and representation. Consequently, important efforts have been made on the development of temporal extensions for XML. This paper investigates how to generate or maintain space-efficient time-stamped documents. We formally define a notion of compactness which allows for comparing documents. Then, we present two methods. For the first one, called general method, no restriction is made on the evolution of the XML documents whereas for the second one, called update-based method, changes are assumed to be specified by updates. For both methods, the issue is to enable processing very large documents, to use existing engines and to comply to Xquery Update Facility. The two methods are compared in terms of space-efficiency. The update-based method produces time-stamped XML documents that are more satisfactory wrt space-efficiency than the general method. This goes to show that the update-based method effectively takes advantage of the updates.

Journal Article Fixpoint and While Temporal Query Languages Get access Nicole Bidoit, Nicole Bidoit Univ. Paris-Sud, UMR 8623 and CNRS, Orsay F-91405, France. Search for other works by this author on: Oxford Academic Google Scholar Matthieu Objois Matthieu Objois Univ. Paris-Sud, UMR 8623 and CNRS, Orsay F-91405, France. Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 19, Issue 2, April 2009, Pages 369–404, https://doi.org/10.1093/logcom/exn056 Published: 21 October 2008 Article history Received: 03 October 2007 Published: 21 October 2008

The paper introduces and investigates relational temporal machine (RTM) as a general abstract model for generic temporal querying. The RTM devices subsume most temporal query languages that have emerged in the literature. A first contribution of the paper is to provide two simplified forms for our machines, namely extended one- tape RTMS and one-tape RTMS. Another contribution is to establish connections between RTMS and the T-WHILE and TS-WHILE extensions of FO based on complexity criteria.

A temporal database can be represented as a finite sequence of relational instances. Queries over such temporal instances usually map the input sequences to relation instances. Motivated by emerging applications, we are investigating a new type of queries over temporal instances, called t2t queries (temporal-to-temporal queries). The issue is to develop languages able to define mappings from temporal instances to temporal instances. The paper proposes and investigates two types of t2t query languages: pointwise languages and SQTL languages.

We investigate the expressive power of implicit temporal query languages. The initial motivation was refining the results of (S. Abiteboul et al., 1999) and enrich them with comparison to /spl mu/TL (M.Y. Vardi, 1988). Thus, we address two classes of temporal query languages: /spl mu/TL-like languages based on TL and T-WHILE-like languages based on WHILE. We provide a two-level hierarchy (w.r t. expressive power) for these temporal query languages. One of the contributions solves an open problem: the relative expressivity of /spl mu/TL and T-FIXPOINT.

The paper investigates temporal properties that are invariant with respect to the temporal ordering and that are expressible by temporal query languages either explicit like FO(≤) or implicit like TL. In the case of an explicit time representation, these ‘order invariant’ temporal properties are simply those expressible in the language FO(=). In the case of an implicit time representation, we introduce a new language, TL(Ei) that captures exactly these properties. The expressive power of the language TL(Ei) is characterized via a game à la Ehrenfeucht-Fraïssé. This provides another proof, using a more classical technique, that the implicit temporal language TL is strictly less expressive than the explicit temporal language FO(≤). This alternative proof is interesting by itself and opens new perspectives in the investigation of results of the same kind for more expressive implicit temporal languages than TL.

The aim of this paper is to propose linear logic as a proof system allowing one to perform updates of databases containing incomplete information. In our approach, a database is specified by facts, deduction rules (among which default rules) and update constraints. Updates will always preserve consistency, i.e. any update of a ‘consistent’ database will produce a new base which is ‘consistent’. The computation of the ‘static semantics’ of a database DB corresponds to the construction of a proof in a logical theory associated to the database; the non logical axioms of such a theory are linear sequents formalising the deduction rules and the update constraints of DB. Similarly, the calculus of the ‘update semantics’ of a database DB w.r.t. the insertion of a literal L, is the construction of a proof in the very same linear theory.

Article Positivism vs minimalism in deductive databases Share on Authors: Nicole Bidoit View Profile , Richard Hull View Profile Authors Info & Claims PODS '86: Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systemsJune 1985 Pages 123–132https://doi.org/10.1145/6012.15409Online:01 June 1985Publication History 24citation589DownloadsMetricsTotal Citations24Total Downloads589Last 12 Months30Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Non first normal form relations to represent hierarchically organized data Authors: Serge Abiteboul Institut National de Recherche en Informatique et Automatique, 78153 Le Chesnay, FRANCE Institut National de Recherche en Informatique et Automatique, 78153 Le Chesnay, FRANCEView Profile , Nicole Bidoit Institut National de Recherche en Informatique et Automatique, 78153 Le Chesnay, FRANCE and Laboratoire de Recherche en Informatique, Université de Paris-Sud, Orsay, FRANCE. Institut National de Recherche en Informatique et Automatique, 78153 Le Chesnay, FRANCE and Laboratoire de Recherche en Informatique, Université de Paris-Sud, Orsay, FRANCE.View Profile Authors Info & Claims PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systemsApril 1984 Pages 191–200https://doi.org/10.1145/588011.588038Online:02 April 1984Publication History 96citation665DownloadsMetricsTotal Citations96Total Downloads665Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF