Repetitively formatted historical books are tokenized and tagged according to eight token types (capitalized words, numbers, punctuation ...). To extract family information, templates of short sequences of tags are generated around frequent proper nouns and specified tokens like "born". Each template is associated with a user-assigned class (head of household, father, mother, spouse, geographic location ...) and a pointer to an overlapping or nearby fragment of text to be extracted. Matching the template against the book text yields class-labeled factoids. In an interaction cycle, new extraction templates are proposed for user approval or editing. Each edit-then-extract cycle typically yields thousands of factoids and a dozen new templates. With five approximately half-hour interactive sessions, 44,000 genealogical factoids were extracted from a 17th century Scottish register of marriages and births and from published 19th-20th century Ohio funeral parlor records. The experience indicates that this method quickly yields quality results with higher F-score than reported for hand-constructed rule templates.

Machine reading is a relatively new field that features computer programs designed to read flowing text and extract fact assertions expressed by the narrative content. This task involves two core technologies: natural language processing (NLP) and information extraction (IE). In this paper we describe a machine reading system that we have developed within a cognitive architecture. We show how we have integrated into the framework several levels of knowledge for a particular domain, ideas from cognitive semantics and construction grammar, plus tools from prior NLP and IE research. The result is a system that is capable of reading and interpreting complex and fairly idiosyncratic texts in the family history domain. We describe the architecture and performance of the system. After presenting the results from several evaluations that we have carried out, we summarize possible future directions.

Automating the conversion of human-readable HTML tables into machine-readable relational tables will enable end-user query processing of the millions of data tables found on the web. Theoretically sound and experimentally successful methods for index-based segmentation, extraction of category hierarchies, and construction of a canonical table suitable for direct input to a relational database are demonstrated on 200 heterogeneous web tables. The methods are scalable: the program generates the 198 Access compatible CSV files in ~0.1s per table (two tables could not be indexed).

HTML tables represent a significant fraction of web data. The often complex headers of such tables are determined accurately using their indexing property. Isolated headers are factored to extract category hierarchies. Web tables are then transformed into a canonical form and imported into a relational database. The proposed processing allows for the formulation of arbitrary SQL queries over the collection of induced relational tables.

We present a method based on header paths for efficient and complete extraction of labeled data from tables meant for humans. Although many table configurations yield to the proposed syntactic analysis, some require access to semantic knowledge. Clicking on one or two critical cells per table, through a simple interface, is sufficient to resolve most of these problem tables. Header paths, a purely syntactic representation of visual tables, can be transformed ("factored") into existing representations of structured data such as category trees, relational tables, and RDF triples. From a random sample of 200 web tables from ten large statistical web sites, we generated 376 relational tables and 34,110 subject-predicate-object RDF triples.

Automatic recognition and formalization of constraints from free-form service requests is a challenging problem. Its resolution would go a long way toward allowing users to make requests using free-form, natural-language-like specifications. In this paper, we address this challenge by offering an ontology-based, semantic-data-modeling approach to recognize constraints in free-form service requests. We encode domain information such as possible constraints and instances within a domain ontology in terms of object sets, relationship sets among these object sets, and operations over values in object sets and relationship sets. Our system recognizes the constraints in a service request by finding the domain ontology that best matches the request and then by using relationships and operations relevant to the request in the matched ontology to generate the service-request constraints. In experiments conducted with our prototype implementation, our system achieved an average of 96% recall and 99% precision.

As XML data becomes more and more prevalent and as larger quantities of data find their way into XML documents, the need for quality XML data organization only increase. One standard way of structuring data well is to reduce and, if possible, eliminate redundancy, while at the same time making the storage structures as compact as possible. In this paper, we present a methodology to generate XML storage structures where conforming XML documents are redundancy-free, and for most practical cases, are also fully compact. Our methodology assumes the input is a conceptual-model hypergraph. For the special case that every edge in the hypergraph is binary, we present a simple algorithm, guaranteed to always generate redundancy-free storage structures. We show, however, that generating a minimum number of redundancy-free storage structures is NP-hard. We therefore provide heuristics to guide the process and observe that these heuristics result in satisfactory solutions, which are often optimal. We then present a general algorithm for n-ary edges and show that it generates redundancy-free storage structures. The general algorithm must overcome several problems that do not arise in the special case

Automating schema matching is challenging. Previous approaches to automating schema matching focus on computing direct element matches between two schemas. Schemas, however rarely match directly. Thus, to complete the task of schema matching, we must also compute indirect element matches. In this paper we present a framework for generating direct as well as many indirect element matches between a source schema and a target schema. Recognizing expected data values associated with schema elements and applying schema-structure heuristics are the key ideas to computing indirect matches. Experiments we have conducted over several real-world application domains show encouraging results, yielding over 90% precision and recall for both direct and indirect element matches.

We often need to access and reorganize information available in multiple tables in diverse Web pages. To understand tables, we rely on acquired expertise, background information, and practice. Current computerized tools seldom consider the structure and content in the context of other tables with related information. This paper addresses the table processing issue by developing a new framework to table understanding that applies an ontology-based conceptual modeling extraction approach to: (i) understand a table's structure and conceptual content to the extent possible; (ii) discover the constraints that hold between concepts extracted from the table; (iii) match the recognized concepts with ones from a more general specification of related concepts; and (iv) merge the resulting structure with other similar knowledge representations for use in future situations. The result is a formalized method of processing the format and content of tables while incrementally building a relevant reusable conceptual ontology.

Microfilm documents contain a wealth of information, but extracting and organizing this information by hand is slow, error-prone, and tedious. As an initial step toward automating access to this information, we describe in this paper an algorithmic process to automatically identify record patterns found in microfilm tables for pre-specified application domains. Our table-processing algorithm accepts an XML input file describing the individual cells of a table taken from a microfilm document, and finds for each record in the document the cells that together comprise the record. Two key features drive the algorithm: (1) geometric layout and (2) label matching with respect to a given domain-specific application ontology. The algorithm achieved an accuracy of 92% on our test corpus of genealogical microfilm tables.

Deals with the problem of how to gain information from many heterogeneous data sources. As a solution, we propose a general framework for mediated information gain: it minimizes and supports the human burden, clearly identifies the algorithmically tractable subtasks and assures a well-understood level of quality. We identify a "mediation task" as an extended amalgamation of searching, querying and updating in traditional information systems, and we introduce the notion of a "formal information state" which unifies and extends the classical notions of a schema, an instance, a query with additional specifications, and a returned answer. The quality is concerned with correctness, precision and completeness. Correctness is guaranteed by maintaining internal consistency, precision is achieved by embeddings identifying only the relevant parts of the sources, and completeness is reached by user interactions with revisions and by iteration. The whole framework is characterized by 18 rules which capture the essentials and suggest a high-level architecture for implementations.

Extraction of information from unstructured or semistructured Web documents often requires a recognition and delimitation of records. (By “record” we mean a group of information relevant to some entity.) Without first chunking documents that contain multiple records according to record boundaries, extraction of record information will not likely succeed. In this paper we describe a heuristic approach to discovering record boundaries in Web documents. In our approach, we capture the structure of a document as a tree of nested HTML tags, locate the subtree containing the records of interest, identify candidate separator tags within the subtree using five independent heuristics, and select a consensus separator tag based on a combined heuristic. Our approach is fast (runs linearly for practical cases within the context of the larger data-extraction problem) and accurate (100% in the experiments we conducted).

We can extract and structure information from documents if we can match attributes with document data values and associate these matched attribute-value pairs as tuples in relations. In this paper we present a general approach to extracting and structuring information from unstructured documents that are data rich (have many recognizable constants). In our approach to this problem we start with an application ontology that describes the objects, relationships, and constraints in a domain of interest. We parse this ontology to generate recognition rules for constants and context keywords and to extract structural and constraint information. Given the generated rules and an unstructured document, we apply a recognizer to extract the constants and keywords, and we then apply a structure builder to match constant values with attributes, to associate attribute-value pairs as relations, and to populate a generated database schema with the extracted data according to the constraints of the application ontology. When applied to a list of several similar unstructured documents, the result is a populated database structured according to and ltered with respect to the application ontology. To make our approach general, we x all the processes and change only the ontological description for a di erent application domain. In experiments we conducted on two di erent types of unstructured documents taken from the Web, our approach attained recall ratios in the 80 % and 90 % range and precision ratios near 98%.

We give a straightforward definition for redundancy in individual nested relations and define a new normal form that precisely characterizes redundancy for nested relations. We base our definition of redundancy on an arbitrary set of functional and multivalued dependencies, and show that our definition of nested normal form generalizes standard relational normalization theory. In addition, we give a condition that can prevent an unwanted structural anomaly in nested relations, namely, embedded nested relations with at most one tuple. Like other normal forms, our nested normal form can serve as a guide for database design.

article Free Access Share on Turnable formalism in object-oriented systems analysis: meeting the needs of both theoreticians and practitioners Authors: Stephen W. Clyde View Profile , David E. Embley View Profile , Scott N. Woodfield View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 27Issue 10Oct. 1992 pp 452–465https://doi.org/10.1145/141937.141972Published:31 October 1992Publication History 17citation355DownloadsMetricsTotal Citations17Total Downloads355Last 12 Months10Last 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

A means by which ordinary forms can be exploited to provide a basis for nonprocedural specification of information processing is discussed. The Natural Forms Query Language (NFQL) is defined. In NFQL data retrieval requests and computation specifications are formulated by sketching ordinary forms to show what data are desired and update operations are specified by altering data on filled-in forms. The meaning of a form depends on a store of knowledge that includes extended abstract data types for defining elementary data items, a database scheme defined by an entity-relationship model, and a conceptual model of an ordinary form. Based on this store of knowledge, several issues are addressed and resolved in the context of NFQL. These issues include automatic generation of query expressions from weak specifications, the view update problem, power and completeness, and a heuristic approach to resolving computational relationships. A brief status report of an implementation of NFQL is also given.

A language is introduced in which both schema integration and query formulation for federated database systems can be performed. The relational model is augmented with connectors that impose predicate conditions over attributes of relations either at the same or different sites. The relational model with connectors has a natural diagrammatic representation, and thus, the language has a graphical user interface. The theoretical foundation for the graphical language is algebraic. Bach algebraic operator maps a diagram (of relations with connectors) into another diagram, and every diagram represents a possible user query. Operators specifically designed to operate on incompatible schemas are introduced and formally defined. Possible domain incompatibilities are resolved by using extended abstract data types.

For some time now we have also been interested in studying human factors aspects of computer text editors. We have surveyed the literature [9], and we have conducted several investigations of our own [10] ranging from an application of file-comparison algorithms in editor research [1], through prediction of editing performance [7], to the design and implementation of SIMPLE, our own editing system for beginners [8, 11].Currently we are concentrating our efforts on gathering data to determine how much time users spend performing various editing activities. We intend to extend the work begun in previous studies, to investigate suboptimal editor performance including errors and nonoptimal means of achieving goals, and to study the broder aspects of editing such as file manipulation and job control that have largely been ignored.

A lectureless mode of instruction for programming courses is described. The observations collected in a pilot experiment teaching FORTRAN to about one hundred business students are recorded and analyzed. Advantages and disadvantages of the method, and implications for other languages and other clienteles are discussed.