New Horizons in Information Management: 20th British National Conference on Databases, BNCOD 20, Coventry, UK, July 15-17, 2003, Proceedings (Lecture Notes in Computer Science, 2712)

This book constitutes the refereed proceedings of the 20th British National Conference on Databases, BNCOD 20, held in Coventry, UK, in July 2003. The 20 revised full papers presented together with abstracts of 2 invited talks were carefully reviewed and selected from numerous submissions. The papers are organized in topical sections on XML and semi-structured data; performance in searching and mining; transformation, integration, and extension; events and transactions; and personalization and the Web. Lecture Notes in Computer Science Preface Organization Acknowledgements Table of Contents Multivalued Dependencies in XML Introduction Preliminary Definitions XMVDs in XML XMVDs in XML and MVDs in Relations Mapping from Relations to XML Conclusions Processing XML Path Expressions Using XML Materialised Views* 1 Introduction 2 Related Work 3 Rewriting XML Path Expressions 3.1 Examples Example 3.1 Example 3.2 Example 3.3 Example 3.4 Example 3.5 Example 3.6 3.2 Model of XML View 3.3 Determining Query Processing Type 3.4 Rewriting of Path Expression 3.5 Examples of Query Rewriting 4 Implementation 4.1 Table Schema 4.2 View Selection and Query Rewriting 4.3 XML Path Expression to SQL Mapping 4.4 XML Tagging 4.5 Preliminary Performance Evaluation 5 Concluding Remarks References WebVigiL: User Profile-Based Change Detection for HTML/XML Documents 1 Introduction 2 Related Work 3 Problem Overview 3.1 What Is a Change 3.2 Importance of User Intent 3.3 XML Problem Overview 4 HTML Change Detection 4.1 Changes of Interest in a Page 4.2 Object Identification and Extraction 4.3 Detecting Changes to Objects 4.3.1 CH-Diff: A Customized Change Detection Algorithm for HTML 5 Change Detection for XML 5.1 Change Operation 5.2 CX-Diff: Customized Change Detection for Ordered Documents 5.2.1 Object Extraction and Signature Computation 5.2.2 Filtering Unique Inserts/Deletes 5.2.3 Finding the Common Order Subsequence 5.2.4 Optimization 6 Change Presentation 7 Conclusion References 8 Appendix Aggregate Table-Driven Querying via Navigation Ontologies in Distributed Statistical Databases Introduction Motivation Data Model for Ontologies Modelling Client Functions Visual Query Formulation 5.1 Macro Table Object and Table-Driven Queries 5.2 The Client Interface 5.3 An Example Conclusion Acknowledgement. The work is partially supported by the MISSION project (IST 1999-10655) and partially supported by the ICONS project (IST-2001-32429). These are funded by the European Framework V. The authors would like to acknowledge the contributions m References External Ontologies in the Semantic Web 1 Introduction 2 Fundamentals 3 View Language 4 External Ontologies 5 Implementation 5.1 Query Answering 5.2 Materialization 6 Discussion Quantization Techniques for Similarity Search in High-Dimensional Data Spaces 1 Introduction 1.1 Problem Statement 1.2 Plan and Contributions 2 Related Work 2.1 Indexing Techniques 2.2 Clustering 2.3 Quantization Techniques 2.4 Clustering and Vector Quantization 3 Comparison of Three Techniques 3.1 Data Sets 3.2 Environment 3.3 Evaluation Results 4 Clustered IQ-Tree 4.1 Data Space Partitioning 4.2 Clustering by a Modiÿed k-Means Algorithm 5 Comparison of CIQ-Tree with the Other Techniques 5.1 Experiments Based on Real Data Sets 5.2 Experiments Based on Synthetic Data Sets 6 Conclusions Performance Evaluation and Analysis of K-Way Join Variants for Association Rule Mining1 1 Introduction 1.1 Focus of This Paper 2 Association Rules 2.1 Apriori Algorithm 2.2 Candidate Generation 2.3 Support Counting 3.1 Methodology for Experimental Evaluation 3.2 Cost Analysis of the Basic K-Way Join (Kwj) Approach 3.3 Pruning the Input Table (Pi) 3.4 Second Pass Optimization (Spo) 3.5 Reuse of Item Combinations (Ric) 4 Combinations of Basic Optimizations 4.1 Second Pass Optimization on Pruned Input (SpoPi) 4.2 Reuse of Item Combinations on Pruned Input (RicPi) 4.3 Reuse of Item Combinations and Spo (RicSpo) 4.4 Reuse of Item Combinations on Pruned Input with Spo (All) 5 Summary of Experimental Results 6 Conclusions and Future Work References External Sorting with On-the-Fly Compression Introduction Compression in Retrieval Systems External Sorting External Sorting with Compression Compression Techniques for External Sorting Results Conclusions MaxDomino: Efficiently Mining Maximal Sets 1 Introduction 2 The Model and Notations 3 Implementation of MaxDomino 3.1 Transaction List Generation 3.2 Hash Table Construction, Support Counting, and Itemset Pruning 4 Experimental Results 5 Summary and Future Research Directions References Evaluating Maintenance Policies for Externally Materialised Multi-source Views Introduction Background Maintaining a Join View Alternatives for Join View Maintenance Policies Consistency Implications Source Capabilities TMID -- A Testbed for Maintenance of Integrated Data Evaluating Maintenance Policies Analysing Policy Timings Analysing the Choice between Incremental and Recompute Analysing Auxiliary Views Conclusions Appendix Database Schema Transformation Optimisation Techniques for the AutoMed System Introduction The AutoMed Framework Optimising Transformation Pathways Semantics of Transformations and a Transformation Manipulation Language Properties of the TML Rules for Optimisation An Optimisation Example Conclusion Using Similarity-Based Operations for Resolving Data-Level Conflicts 1 Introduction 2 Related Work 3 Similarity Measures 3.1 Basic Similarity Predicates 3.2 Complex and Application-Specific Similarity 4 Semantics of the Similarity Operators 5 Implementation and Optimization 5.1 Similarity Join 5.2 Similarity-Based Grouping 5.3 Implementation Using Oracle8i 6 Evaluation 7 Applications 8 Conclusions ProSQL: A Prototyping Tool for SQL Temporal Language Extensions Introduction Motivation Previous Work Application 4.1 Support for a DDL 4.2 Definition of New Non Atomic Data Type 4.3 Database Definition 4.4 Support for a DML 4.5 Definition of Operations 4.6 Definition of Functions 4.7 Definitions of Functions on Relations 4.8 Limitations Conclusions References MVMBS: A Multiple Views Supporting Multiple Behaviours System for Interoperable Objects-Oriented Database Systems Introduction The Object Model Sharing Behaviour -- Scope and Requirements Semantic Requirements for Reusing and Sharing Behaviour in MDBS Detection of Semantic Relationships Overview of MVMBS Architecture Schema Meta Translator (SMT) MVMBS Internal Intermediate Data Model (IIDM) Class Comparison Processor (CCP) Shareable Method Detector (SMD) Equivalent Method Detector (EMD) Class Similarity Detector (CSD) Meta Integration Language (MIL) Global Class Materialisation Rules Efficient Filtering of Composite Events Introduction Background Application Scenario: Remote Monitoring Concepts: Events, Profiles, and Notifications Methods for Composite Event Filtering Composite Event Detection in a Single Step Performance Evaluation Performance Tests and Discussion Implementation Variants Summary Multilevel Secure Rules and Its Impact on the Design of Active Database Systems Introduction Our Model of an MLS Database Rules in an MLS Active Database Events in an MLS Active Database Systems Conditions in an MLS Active Database System Actions in an MLS Active Database System Relationship of Security Levels Associated with a Rule Execution Model Rule Processing Granularity Conflict Resolution and Rule Priorities Sequential versus Concurrent Execution Coupling Modes Iterative versus Recursive Algorithms Error Handling Architecture Architecture for an MLS Active Database System Related Work Related Work in Multilevel Secure Active Databases Related Work in Expert Systems Related Work in Active Databases Related Work in Multilevel Secure Databases Conclusion and Future Work Using the Compliant Systems Architecture to Deliver Flexible Policies within Two-Phase Commit Introduction The Compliant Systems Architecture Application to Two-Phase Commit Policy Identification Related Work Conclusion and Future Directions A Concurrent Blink-Tree Algorithm Using a Cooprerative Locking Protocol* Introduction Preliminaries Backgrounds on B$^{link}$-Tree Concurrency Control The Basic Idea of the Proposed B$^{link}$-Tree CC Algorithm The Proposed B$^{link}$-Tree CC Algorithm The Key Search Algorithm Algorithm for Inserting a New Index Entry Algorithm for Deleting an Index Entry Lock Cooperation Restructuring an Underflow Node Transferring the Index Entries Merging the Half-Full Nodes Deadlock-Freeness of the Proposed Locking Protocol The Performance Overview Conclusion Tools for Personalised Presentation of Information Introduction The Personalisation Framework Personalisation Toolkit 3.1 Service User Base Content Base Knowledge Base 3.2 Filtering Engine 3.3 Customisation Engine 3.4 Output Engine 3.5 User Interface Breastfeeding Prototype Conclusions Acknowledgements. The authors acknowledge the support received from the Engineering and Physical Science Research Council under grant reference GR/N22229/01 (Dynamic Information Presentation). They also wish to thank Dr. Jamie Inglis and Kerr Donaldson of References Extracting Database Information from E-mail Messages1 Introduction The Information Extraction Process 2.1 The Information Extraction Architecture 2.2 The Information Extraction Process 2.3 A System for Extracting Information from E-mail Messages Conclusions References Author Index

this Book Constitutes The Refereed Proceedings Of The 20th British National Conference On Databases, Bncod 20, Held In Coventry, Uk, In July 2003.

the 20 Revised Full Papers Presented Together With Abstracts Of 2 Invited Talks Were Carefully Reviewed And Selected From Numerous Submissions. The Papers Are Organized In Topical Sections On Xml And Semi-structured Data; Performance In Searching And Mining; Transformation, Integration, And Extension; Events And Transactions; And Personalization And The Web.