Digital devices are an integral part of our lives. Through these devices, people produce and save personal data, with or without their explicit awareness. This personal digital information has been exploited by companies, but users find it hard to access and search in a uniform way, due to the heterogeneity, fragmentation of data and non-uniform access interface. By integrating and organizing this information into common kinds of everyday episodes ("scripts") that people engage in, we can help users recall and explore forgotten details of their past. However, being able to recognize such episodes in the user’s personal digital information requires not only script knowledge (e.g., the steps/actions in the script), but also explicit knowledge about the digital traces potentially left behind by each of the actions. In this paper, we present "One Of Us", a web-based multiplayer game, which collects descriptions of different kinds of personal digital traces, by having players identify the digital traces that might be produced by each of the actions in a given script. We report on the results of an experimental study, which gives evidence that our game is i) enjoyable, ii) accounts for uncommon answers, iii) validates and assesses knowledge by having the players vote on other’s responses - thus not requiring a second round of quality assessment, and iv) dynamically acquires new pieces of information.

Personal information is typically fragmented across multiple, heterogeneous, distributed sources and saved as small, heterogeneous data objects, or traces. The DigitalSelf project at Rutgers University focuses on developing tools and techniques to manage (organize, search, summarize, make inferences on and personalize) such heterogeneous collections of personal digital traces. We propose to demonstrate YourDigitalSelf, a mobile phone-based personal information organization application developed as part of the DigitalSelf project. The demonstration will use a sample user data set to show how several disparate data traces can be integrated and combined to create personal narratives, or coherent episodes, of the user's activities. Conference attendees will be given the option to install YourDigitalSelf on their own devices to interact with their own data.

In many applications it is important to find a meaningful relationship between the schemas of a source and target database. This relationship is expressed in terms of declarative logical expressions called schema mappings. The more successful previous solutions have relied on inputs such as simple element correspondences between schemas in addition to local schema constraints such as keys and referential integrity. In this paper, we investigate the use of an alternate source of information about schemas, namely the presumed presence of semantics for each table, expressed in terms of a conceptual model (CM) associated with it. Our approach first compiles each CM into a graph and represents each table's semantics as a subtree in it. We then develop algorithms for discovering subgraphs that are plausible connections between those concepts/nodes in the CM graph that have attributes participating in element correspondences. A conceptual mapping candidate is now a pair of source and target subgraphs which are semantically similar. At the end, these are converted to expressions at the database level. We offer experimental results demonstrating that, for test cases of non-trivial mapping expressions involving schemas from a number of domains, the "semantic" approach outperforms the traditional technique in terms of recall and especially precision.

Description logics and reasoners, which are descendants of the KL-ONE language, have been studied in depth in artificial intelligence. After a brief introduction, we survey their application to the problems of information management, using the framework of an abstract information server equipped with several operations-each involving one or more languages. Specifically, we indicate how one can achieve enhanced access to data and knowledge by using descriptions in languages for schema design and integration, queries, answers, updates, rules, and constraints.>

Description languages form the basis of several object-centered knowledge base management systems developed in recent years, including ones in industrial use. Originally used for conceptual modeling (to define views), DLs are seeing increased use as query languages for retrieving information. This paper, aimed at a general audience that includes database researchers, considers the relationship between the expressive power of DLs and that of query languages based on Predicate Calculus.

Knowledge-base management systems (KBMS) based on description logics are being used in a variety of situations where access is needed to large amounts of data stored in existing relational databases. We present the architecture and algorithms of a system that converts most of the inferences made by the KBMS into a collection of SQL queries, thereby relying on the optimization facilities of existing DBMS to gain efficiency, while maintaining an object-centered view of the world with a substantive semantics and significantly different reasoning facilities than those provided by Relational DBMS and their deductive extensions. We address a number of optimization issues that arise in the translation process due to the fact that SQL queries with different syntax (but identical semantics) are not treated uniformly by current database management systems.

We first explore the similarities and differences between concept definitions in description/terminological logics such as KL-ONE, Classic, Back, Loom, etc. and the types normally encountered in programming languages. The similarities lead us to consider the application of natural semantics — the mechanism most frequently used to describe type systems — to the definition of knowledge base management systems that use such description logics. The paper presents inference rules in the natural semantics style for a variety of judgments involving descriptions, such as “subsumption” and “object membership”, and provides the full definition of subsumption in the Classic KBMS as a proof system. One of our objectives is to document some advantages of this approach, including the utility of multiple complementary semantics, and especially the characterization of implementations that are computationally tractable but are incomplete relative to standard denotational semantics.

We describe Telos, a language intended to support the development of information systems. The design principles for the language are based on the premise that information system development is knowledge intensive and that the primary responsibility of any language intended for the task is to be able to formally represent the relevent knowledge. Accordingly, the proposed language is founded on concepts from knowledge representations. Indeed, the language is appropriate for representing knowledge about a variety of worlds related to a particular information system, such as the subject world (application domain), the usage world (user models, environments), the system world (software requirements, design), and the development world (teams, metodologies). We introduce the features of the language through examples, focusing on those provided for desribing metaconcepts that can then be used to describe knowledge relevant to a particular information system. Telos' fetures include an object-centered framework which supports aggregation, generalization, and classification; a novel treatment of attributes; an explicit representation of time; and facilities for specifying integrity constraints and deductive rules. We review actual applications of the language through further examples, and we sketch a formalization of the language.

Type checking at query compilation time is important for both detecting programmer errors and reducing the running time of queries. We have argued elsewhere [2] that entity-based data management systems which support class hierarchies, such as semantic data models and object-oriented dbms, should not be confined to have “strict inheritance” — i.e., they should permit contradictions between class specifications, albeit in an explicit and controlled way. In this paper we present a type system for queries manipulating objects in such classes. We provide sound and complete axiomatizations of the predications “σ is a subtype of τ” and “expression e has type τ”. The absence of strict inheritance has normally been felt to preclude effective type checking. We show that the problem is co-NP-hard when disjoint types are admitted in the schema, but present a low-order polynomial-time algorithm that determines the absence of type errors in a query when the database has only entities.

We argue that accessing the transitive closure of relationships is an important component of both databases and knowledge representation systems in Artificial Intelligence. The demands for efficient access and management of large relationships motivate the need for explicitly storing the transitive closure in a compressed and local way, while allowing updates to the base relation to be propagated incrementally. We present a transitive closure compression technique, based on labeling spanning trees with numeric intervals, and provide both analytical and empirical evidence of its efficacy, including a proof of optimality.

CLASSIC is a data model that encourages the description of objects not only in terms of their relations to other known objects, but in terms of a level of intensional structure as well. The CLASSIC language of structured descriptions permits i) partial descriptions of individuals, under an 'open world' assumption, ii) answers to queries either as extensional lists of values or as descriptions that necessarily hold of all possible answers, and iii) an easily extensible schema, which can be accessed uniformly with the data. One of the strengths of the approach is that the same language plays multiple roles in the processes of defining and populating the DB, as well as querying and answering.

One characteristic feature of object-oriented systems and knowledge bases (semantic data models, conceptual modeling languages, Al frames) is that they offer as a basic paradigm the notion of objects grouped into classes, which are themselves organized in subclass hierarchies. Through ideas such as inheritance and bounded polymorphism, this feature supports the technique of “abstraction by generalization”, which has been argued to be of importance in designing Information Systems [11, 2].

The features of a compiler for the Taxis design language are described and discussed. Taxis offers an entity-based framework for designing interactive information systems and supports generalisation, classification and aggregation as abstraction mechanisms. Its features include multiple inheritance of attributes, isA hierarchies of transactions, metaclasses, typed attributes, a procedural exception-handling mechanism and an iteration construct based on the abstraction mechanisms supported Developing a compiler for the language involved dealing with the problems of efficiently representing and accessing a large collection of entities, performing (static) type checking and representing isA hierarchies of transactions.

An exception-handling facility suitable for languages used to implement database-intensive information systems is presented. Such a mechanism facilitates the development and maintenance of more flexible software systems by supporting the abstraction of details concerning special or abnormal occurrences. The type constraints imposed by the schema as well as various semantic integrity assertions are considered to be normalcy conditions, and the key contribution of this work is to allow exceptions to these constraints to persist. To achieve this, solutions are proposed to a range of problems, including sharing and computing with exceptional information, exception handling by users, the logic of constraints with exceptions, and implementation issues. The use of exception handling in dealing with null values, estimates, and measurement is also illustrated.