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.

Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functions. We show how to control conjunctions on left-hand-sides of subsumptions and use this restriction to develop a parameter-tractable algorithm for reasoning about knowledge base consistency. We then show how the resulting logic can simulate partial features, and present algorithms for efficient query answering in that setting.

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.

A referring expression in linguistics is a noun phrase that identifies individuals to listeners. In the context of a query over a first order knowledge base, referring expressions to answers are usually constant symbols. This paper motivates and initiates the exploration of allowing more general formulas, called singular referring expressions, to replace constants in this role. Referring expression types play a novel and significant role in analyzing the properties of candidate expressions.

Coherence Management refers to all efforts one needs to invest, in order to ensure that information shown in, and implied by a representation of requirements makes sense as a whole, is coherent. Coherence Management is an umbrella term we use to cover, and more importantly, stimulate research on relationships between identification, measurement, and action on phenomena which reflect tensions between information in requirements representations. Such tensions exist between information which is, for example, logically inconsistent, or stakeholders disagree on, or signals tradeoffs (meaning that improvement on some requirements, for instance, necessarily means some quantifiable (or not) deterioration of others). These tensions are an important topic of research in Requirements Engineering, and various methods have been proposed for the identification, measurement, and action on logical inconsistency in requirements models, on negotiating disagreements, and on settling tradeoffs. Despite focusing on related phenomena, these methods are different and each come with their own specific definition of when a representation of requirements is incoherent and what to do about it. This makes it hard to compare existing methods, design new ones, and choose those to apply when doing RE. In this short communication we outline our research agenda for developing a unified formal framework for the systematization and classification of Coherence Management efforts in the context of RE, as well as exploring their compatibility.

Non-functional requirements (NFRs) have been the focus of research in Requirements Engineering (RE) for more than 20 years. Despite this attention, their ontological nature is still an open question, thereby hampering efforts to develop concepts, tools and techniques for eliciting, modeling, and analyzing them, in order to produce a specification for a system-to-be. In this paper, we propose to treat NFRs as qualities, based on definitions of the UFO foundational ontology. Furthermore, based on these ontological definitions, we provide guidelines for distinguishing between non-functional and functional requirements, and sketch a syntax of a specification language that can be used for capturing NFRs.

We propose a modeling language for non-functional requirements (NFRs) that views NFRs as requirements over qualities, mapping a software-related domain to a quality space. The language is compositional in that it allows (recursively) complex NFRs to be constructed in several ways. Importantly, the language allows the definition of requirements about the quality of fulfillment of other requirements, thus capturing, among others, the essence of probabilistic and fuzzy goals as proposed in the literature. We also offer a methodology for systematically refining informal NFRs elicited from stakeholders, resulting in unambiguous, de-idealized, and measurable requirements. The proposal is evaluated with a requirements dataset that includes 370 NFRs crossing 15 projects. The results suggest that our framework can adequately handle and clarify NFRs generated in practice.

In this position paper we review the history of requirements models and conclude that a goal-oriented perspective offers a suitable abstraction for requirements analysis. We stake positions on the nature of modelling languages in general, and requirements modelling languages in particular. We then sketch some of the desirable features (... “requirements”) of design-time and runtime requirements models and draw conclusions about their similarities and differences.

Goal models capture stakeholder requirements for a system-to-be, but also circumscribe a space of alternative specifications for fulfilling these requirements. Recent proposals for self-adaptive software systems rely on variants of goal models to support monitoring and adaptation functions. In such cases, goal models serve as mechanisms in terms of which systems reflect upon their requirements during their operation. We argue that existing proposals for using goal models at runtime are using design artifacts for purposes they were not intended, i.e., for reasoning about runtime system behavior. In this paper, we propose a conceptual distinction between Design-time Goal Models (DGMs)-used to design a system-and Runtime Goal Models (RGMs)-used to analyze a system's runtime behavior with respect to its requirements. RGMs extend DGMs with additional state, behavioral and historical information about the fulfillment of goals. We propose a syntactic structure for RGMs, a method for deriving them from DGMs, and runtime algorithms that support their monitoring.

This paper considers the problem of learning task specific web-service descriptions from traces of users successfully completing a task. Unlike prior approaches, we take a traditional machine-learning perspective to the construction of web-service mo

This paper investigates aspects of the problem of software evolution resulting from top-level requirements change. In particular, while most research on design for software focuses on finding some correct solution, this ignores that such a solution is often only correct in a particular, and often short-lived, context. Using a logic-based goal-oriented requirements modeling language, the paper poses the problem of finding desirable solutions as the requirements change. Among other possible criteria of desirability, we consider minimizing the effort required to implement the new solution, which involves reusing parts of the old solution. In general, the solution of requirements problems is viewed as an exploration using a “requirements engineering knowledge base” (REKB), whose specification is formalized. The paper reports on experience implementing the REKB on top of a so-called “reason-maintenance system”, and provides evidence that incremental solution finding is indeed more efficient.

Techne is an abstract requirements modeling language that lays formal foundations for new modeling languages applicable during early phases of the requirements engineering process. During these phases, the requirements problem for the system-to-be is being structured, its candidate solutions described and compared in terms of how desirable they are to stakeholders. We motivate the need for Techne, introduce it through examples, and sketch its formalization.

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.

We present details of a goal-oriented process for database requirements analysis. This process consists of a number of steps, spanning the spectrum from high-level stakeholder goal analysis to detailed conceptual schema design. The paper shows how goal modeling contributes to systematic scoping and analysis of the application domain, and subsequent formal specification of database requirements based on this domain analysis. Moreover, a goal-oriented design strategy is proposed to structure the transformation from the domain model to the conceptual schema, according to a set of user defined design issues, also modeled as goals. The proposed process is illustrated step-by-step using a running example from the design of a real-world, industrial biological database. We also report early progress towards building full tool support, by presenting a prototype that captures and stores design sessions in a queryable form. This facility makes it possible to answer questions that are hard, if not impossible, to answer using existing methodologies for database design.

We present a case study of a real-world industrial application which produced several versions of conceptual schema design for a biological database during its evolution. We apply the techniques of early requirements analysis to produce a goal model of the problem domain. We then show that by incorporating goal analysis in the design process we can account for the original schemas by tracing them back to stakeholder goals. Moreover, the goal-oriented analysis supports the systematic examination of the space of design alternatives, and better explains what the output of the design process (a conceptual schema) really means. Our results advocate the need for an extended design methodology for databases driven by stakeholder goals

Functional relationships between objects, called `attributes', are of considerable importance in knowledge representation languages, including Description Logics (DLs). A study of the literature indicates that papers have made, often implicitly, different assumptions about the nature of attributes: whether they are always required to have a value, or whether they can be partial functions. The work presented here is the first explicit study of this difference for subclasses of the CLASSIC DL, involving the same-as concept constructor. It is shown that although determining subsumption between concept descriptions has the same complexity (though requiring different algorithms), the story is different in the case of determining the least common subsumer (lcs). For attributes interpreted as partial functions, the lcs exists and can be computed relatively easily; even in this case our results correct and extend three previous papers about the lcs of DLs. In the case where attributes must have a value, the lcs may not exist, and even if it exists it may be of exponential size. Interestingly, it is possible to decide in polynomial time if the lcs exists.

Practical process-support and workflow systems should be built to describe the simple, normal flow of events and then deal easily with irregularities, including tolerating deviations. Similarly, these systems should describe the normal format and constraints concerning the large amounts of data that are usually stored, but then deal with abnormalities and possibly accommodate exceptional values. We offer a framework for treating both kinds of irregularities uniformly by using the notion of exception handling (with human agents as potential online exception handlers) and applying it to processes that have been reified as objects in classes with steps as attributes. As a result, only a small number of new constructs, which can be applied orthogonally, need to be introduced. Special runtime checks are used to deal with the consequences of permitting deviations from the norm to persist as violations of constraints. A logical semantics of process coordination and deviations is presented as a specification for implementations.

In an open component market place, interface description languages (IDLs), such as CORBA'S, provide for the consumer only a weak guarantee (concerning type signatures) that a software service will work in a particular context as anticipated.Stronger guarantees, regarding the intended semantics of the service, would help, especially if formalized in a language that allowed effective, automatic and static checking of compatibility between the server and the client's service descriptionsWe propose an approach based on a family of formalisms called description logics (DLs), providing three examples of the use of DLs to augment IDL: (1) for the CORBA Cos Relationship service; (2) for capturing information models described using STEP Express, the IS0 standard language used in the manufacturing domain (and a basis of the OMG PDM effort); and (3) constraints involving methods. While traditionalformal specification techniques are more powerful, DLs offer certain advantages: they have decidable, even efficient reasoning algorithms, yet they still excel at modeling natural domains, and are thus well-suited for specifying application-and domain-specific services.

This paper offers an approach to extensible knowledge representation and reasoning for a family of formalisms known as Description Logics. The approach is based on the notion of adding new concept constructors, and includes a heuristic methodology for specifying the desired extensions, as well as a modularized software architecture that supports implementing extensions. The architecture detailed here falls in the normalize-compared paradigm, and supports both intentional reasoning (subsumption) involving concepts, and extensional reasoning involving individuals after incremental updates to the knowledge base. The resulting approach can be used to extend the reasoner with specialized notions that are motivated by specific problems or application areas, such as reasoning about dates, plans, etc. In addition, it provides an opportunity to implement constructors that are not currently yet sufficiently well understood theoretically, but are needed in practice. Also, for constructors that are provably hard to reason with (e.g., ones whose presence would lead to undecidability), it allows the implementation of incomplete reasoners where the incompleteness is tailored to be acceptable for the application at hand.

Matching concepts against patterns (concepts with variables) is a relatively new operation that has been introduced in the context of concept description languages (description logics). The original goal was to help filter out unimportant aspects of complicated concepts appearing in large industrial knowledge bases. We propose a new approach to performing matching, based on a 'concept-centred' normal form, rather than the more standard 'structural subsumption' normal form for concepts. As a result, matching can be performed (in polynomial time) using arbitrary concept patterns of the description language ALN, thus removing restrictions from previous work. The paper also addresses the question of matching problems with additional 'side conditions', which were motivated by practical needs. Key words: Knowledge representation, description logics, matching.

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.>

The paper provides examples of situations where formal specifications of procedures in the standard pre/postcondition style become lengthy, cumbersome and difficult to change, a problem which is particularly acute in the case of object oriented specifications with inheritance. We identify the problem as the inability to express that a procedure changes only those things it has to, leaving everything else unmodified, and review some attempts at dealing with this "frame problem" in the software specification community. The second part of the paper adapts a recent proposal for a solution to the frame problem in artificial intelligence-the notion of explanation closure axioms-to provide an approach whereby one can state such conditions succinctly and modularly, with the added advantage of having the specifier be reminded of things that she may have omitted saying in procedure specifications. Since this approach is based on standard predicate logic, its semantics are relatively straightforward. The paper also suggests an algorithm which generates syntactically the explanation closure axioms from the pre/postcondition specifications, provided they are written in a restricted language; it also suggests a model theory supporting it.>

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.

This paper analyzes the correctness of the subsumption algorithm used in CLASSIC, a description logic-based knowledge representation system that is being used in practical applications. In order to deal efficiently with individuals in CLASSIC descriptions, the developers have had to use an algorithm that is incomplete with respect to the standard, model-theoretic semantics for description logics. We provide a variant semantics for descriptions with respect to which the current implementation is complete, and which can be independently motivated. The soundness and completeness of the polynomial-time subsumption algorithm is established using description graphs, which are an abstracted version of the implementation structures used in CLASSIC, and are of independent interest.

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.