An Introduction to Data Profiling

Loading...

An Introduction to Data Profiling

16.4.2013 Felix Naumann

Overview 2

■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profiling ■ Profiling challenges

Felix Naumann | Profiling & Cleansing | Summer 2013

Definition Data Profiling 3

■ Data profiling is the process of examining the data available in an existing data source [...] and collecting statistics and information about that data. Wikipedia 03/2013 ■ Data profiling refers to the activity of creating small but informative summaries of a database. Ted Johnson, Encyclopedia of Database Systems ■ Define as a set of data profiling tasks / results

Felix Naumann | Profiling & Cleansing | Summer 2013

Classification of Profiling Tasks 4

Cardinalities Single column

Patterns and data types

Data profiling

Value distributions Key discovery Uniqueness

Conditional Partial

Multiple columns

Foreign key discovery Inclusion dependencies

Conditional Partial

Functional dependencies

Felix Naumann | Profiling & Cleansing | Summer 2013

Conditional Partial

Single-column vs. multi-column 5

■ Single column profiling □ Most basic form of data profiling □ Assumption: All values are of same type □ Assumption: All values have some common properties ◊ That are to be discovered □ Often part of the basic statistics gathered by DBMS □ Complexity: Number of values/rows ■ Multicolumn profiling □ Discover joint properties □ Discover dependencies □ Complexity: Number of columns and number of values

Felix Naumann | Profiling & Cleansing | Summer 2013

Cardinalities 6

■ Number of values ■ Number of distinct values ■ Number of NULLs ■ MIN and MAX value ■ Useful for □ Query optimization □ Categorization of attribute □ Relevance of attribute

Felix Naumann | Profiling & Cleansing | Summer 2013

Numeric distributions 7

■ Probability distribution for numeric values ■ Detect whether data follows some well-known distribution □ Determine that distribution function for data values ■ If no specific/useful function detectable: histograms

Normal distributions Felix Naumann | Profiling & Cleansing | Summer 2013

Laplace distributions

Histograms 8

■ Determine (and display) value frequencies for value intervals □ Or for individual values □ Estimation of probability distribution for continuous variables Grade distribution 15 10 5 0 1,0 1,3 1,7 2,0 2,3 2,7 3,0 3,3 3,7 4,0 5,0

■ Useful for □ Query optimization □ Outlier detection □ Visualize distribution Felix Naumann | Profiling & Cleansing | Summer 2013

Data types and value patterns 9

■ String vs. number ■ String vs. number vs. date ■ Categorical vs. continuous ■ SQL data types □ CHAR, INT, DECIMAL, TIMESTAMP, BIT, CLOB, … ■ Domains □ VARCHAR(12) vs. VARCHAR (13) ■ XML data types □ More fine grained ■ Regular expressions (\d{3})-(\d{3})-(\d{4})-(\d+) ■ Semantic domains □ Adress, phone, email, first name Felix Naumann | Profiling & Cleansing | Summer 2013

Uniqueness and keys 10

■ Unique column □ Only unique values ■ Unique column combination □ Only unique value combinations □ Minimality: No subset is unique ■ Key candidate □ No null values □ Uniqueness and non-null in one instance does not imply key: Only human can specify keys (and foreign keys) ■ Meaning of NULL values? ■ Useful for □ Schema design, data integration, indexing, optimization □ Inverse: non-uniques are duplicates Felix Naumann | Profiling & Cleansing | Summer 2013

Inclusion dependencies and foreign keys 11

■ A ⊆ B: All values in A are also present in B ■ A1,…,Ai ⊆ B1,…,Bi: All value combinations in A1,…,Ai are also present in B1,…,Bi ■ Prerequisite for foreign key □ Used across relations □ Use across databases □ But again: Discovery on a given instance, only user can specify for schema

Felix Naumann | Profiling & Cleansing | Summer 2013

Functional dependencies 12

■ „X → A“: whenever two records have the same X values, they also have the same A values.

■ Useful for □ Schema design ◊ Normalization ◊ Keys

Felix Naumann | Profiling & Cleansing | Summer 2013

Partial dependencies 13

■ INDs and FDs that do not perfectly hold □ For all but 10 of the tuples □ Only for 80% of the tuples □ Only for 1% of the tuples ■ Also for patterns, types, uniques, and other constraints ■ Useful for □ Data cleansing

Felix Naumann | Profiling & Cleansing | Summer 2013

Conditional dependencies 14

■ Given a partial IND or FD: For which part do the hold? ■ Expressed as a condition over the attributes of the relation ■ Problems: □ Infinite possibilities of conditions □ Interestingness: ◊ Many distinct values: less interesting ◊ Few distinct values: surprising condition – high coverage ■ Useful for □ Integration: cross-source cINDs

Felix Naumann | Profiling & Cleansing | Summer 2013

Data profiling vs. data mining 15

■ Data profiling gathers technical metadata to support data management ■ Data mining and data analytics discovers non-obvious results to support business management ■ Data profiling results: information about columns and column sets ■ Data mining results: information about rows or row sets □ clustering, summarization, association rules, … ■ Rahm and Do, 2000 □ Profiling: Individual attributes □ Mining: Multiple attributes Felix Naumann | Profiling & Cleansing | Summer 2013

Use Cases for Profiling 16

■ Query optimization □ Counts and histograms ■ Data cleansing □ Patterns and violations ■ Data integration □ Cross-DB inclusion dependencies ■ Scientific data management □ Handle new datasets ■ Data analytics □ Profiling as preparation and for initial insights □ Borderline to data mining ■ Database reverse engineering ■ Data profiling as preparation for any other data management task Felix Naumann | Profiling & Cleansing | Summer 2013

Overview 17

■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profiling ■ Profiling challenges

Felix Naumann | Profiling & Cleansing | Summer 2013

Data profiling tools and algorithms 18



Often packaged with data quality / data cleansing software



IBM InfoSphere Information Analyzer □



Oracle Enterprise Data Quality □







http://www.sap.com/germany/solutions/sapbusinessobjects/large/eim/datainsight/index.epx



http://www.sap.com/germany/solutions/sapbusinessobjects/large/eim/information-steward/index.epx

Informatica Data Explorer

http://www.trilliumsoftware.com/home/products/data-profiling.aspx

CloverETL Data Profiler □



http://msdn.microsoft.com/en-us/library/bb895310.aspx

Trillium Software Data Profiling □



http://www.informatica.com/us/products/data-quality/data-explorer/

Microsoft SQL Server Integration Services Data Profiling Task and Viewer □



http://www.ataccama.com/en/products/dq-analyzer.html

SAP BusinessObjects Data Insight and SAP BusinessObjects Information Steward

□ ■

http://www.talend.com/products/data-quality

Ataccama DQ Analyzer □



http://www.oracle.com/us/products/middleware/data-integration/enterprise-dataquality/overview/index.html

Talend Data Quality □



http://www.ibm.com/software/data/infosphere/information-analyzer/

http://www.cloveretl.com/products/profiler

and many more…

Felix Naumann | Profiling & Cleansing | Summer 2013

Very long feature lists 19 ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

Num rows Min value length Median value length Max value length Avg value length Precision of numeric values Scale of numeric values Quartiles Basic data types Num distinct values ("cardinality") Percentage null values Data class and data type Uniqueness and constancy Single-column frequency histogram Multi-column frequency histogram Pattern discovery (Aa9) Soundex frequencies Benford Law Frequency

■ Single column primary key discovery ■ Multi-column primary key discovery ■ Single column IND discovery ■ Inclusion percentage ■ Single-column FK discovery ■ Multi-column IND discovery ■ Multi-column FK discovery ■ Value overlap (cross domain analysis) ■ Single-column FD discovery ■ Multi-column FD discovery ■ Text profiling

Felix Naumann | Profiling & Cleansing | Summer 2013

Aside: Benford Law Frequency (first digit law) 20

■ Statement about the distribution of first digits d in (many) naturally occurring numbers: □

1

1



40 20 0 1 2 3 4 5 6 7 8 9 □ Holds if log(x) is uniformly distibuted

Picking a random x position uniformly on this number line, roughly 30% of the time the first digit of the number will be 1. Felix Naumann | Profiling & Cleansing | Summer 2013

Explanation for Benford‘s Law 21

■ Law is true if the mantissae of the logarithms of the numbers are uniformly distributed □ 1 ≤ x < 2  x begins with 1 ... □ 9 ≤ x < 10  x begins with 9 □ log 1 ≤ log x < log 2  x begins with 1 … □ log 9 ≤ log x < log 10  x begins with 9 □ [log 1, log 2] > [log 9, log 10]

■ Likely to be (approximately) true if the numbers range over several orders of magnitude.

Felix Naumann | Profiling & Cleansing | Summer 2013

Explanation for Benford‘s Law 22

■ Exponential growth

■ First digit

□ Year 1: 1-100

□ 1: 2 years

□ Year 2: 101-200

□ 2: 7 months in year 3

□ Year 3: 201-400

◊ (log2(300/100)+1 – 2) * 12

□ Year 4: 401-800

□ 3: remaining 5 months

□ Year 5: 801-1600

□ 4 – 9: few months each

□ Year 6: 3200

□ 1: again after under 4 months in year 5 for 1 year

■ Function: 2(

)

∙ 100

◊ (log2(10)+1 – 4) * 12

Felix Naumann | Profiling & Cleansing | Summer 2013

Examples for Benford‘s Law 23

Heights of the 60 tallest structures

■ Main application: Fraud detection

Surface areas of 335 rivers Sizes of 3259 US populations 104 physical constants 1800 molecular weights 5000 entries from a mathematical handbook 308 numbers contained in an issue of Reader's Digest ■ Street addresses of the first 342 persons listed in American Men of Science ■ ■ ■ ■ ■ ■

Populations of all 237 countries

Felix Naumann | Profiling & Cleansing | Summer 2013

Typical Shortcomings of Tools 24

■ Usability □ Complex to configure □ Results complex to view and interpret ■ Scalability □ Main-memory based □ SQL based ■ Efficiency □ Coffee, Lunch, Overnight ■ Functionality □ Restricted to simplest tasks □ Restricted to individual columns or small column sets □ „Checking“ vs. „discovery“ Felix Naumann | Profiling & Cleansing | Summer 2013

Screenshots from Talend 25

Felix Naumann | Profiling & Cleansing | Summer 2013

Screenshots from Talend 26

Felix Naumann | Profiling & Cleansing | Summer 2013

Screenshots from Talend 27

Felix Naumann | Profiling & Cleansing | Summer 2013

Screenshots for IBM Information Analyzer 28

Felix Naumann | Profiling & Cleansing | Summer 2013

Screenshots for IBM Information Analyzer 29

Felix Naumann | Profiling & Cleansing | Summer 2013

Overview 30

■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profiling ■ Profiling challenges

Felix Naumann | Profiling & Cleansing | Summer 2013

Motivation 31

■ Human in the loop for data profiling and data cleansing. ■ Advanced visualization technqiues □ Beyond bar- and pie-charts ■ Interactive visualization □ Support users in visualizing data, profiling results □ Support any action taken upon the results ◊ Cleansing, sorting, … ■ Further reading: http://vgc.poly.edu/~juliana/courses/cs9223/Lectures/intro-tovisualization.pdf Felix Naumann | Profiling & Cleansing | Summer 2013

Massive screens for massive data 32

■ Powerwall, Uni Konstanz ■ 5.20 m x 2.15 m; fast neun Millionen Bildpunkte

http://www.informatik.uni-konstanz.de/forschung/powerwall/application-pictures/

Felix Naumann | Profiling & Cleansing | Summer 2013

Gapminder.org 33

http://www.gapminder.org/GapminderMedia/wp-uploads/Gapminder-World-2012.pdf

Felix Naumann | Profiling & Cleansing | Summer 2013

Overview 34

■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profiling ■ Profiling challenges

Felix Naumann | Profiling & Cleansing | Summer 2013

Extended Classification of Profiling Tasks

Cardinalities Uniqueness and keys

Single column Patterns and data types

35

Distributions Single source Uniqueness and keys

Data Profiling

Inclusion and foreign key dep. Multiple columns Functional dependencies Conditional and approximate dep. Duplicate detection Data overlap Record linkage Schema matching Multiple sources

Schematic overlap

Cross-schema dependencies Topic discovery

Topical overlap

Felix Naumann | Profiling & Cleansing | Summer 2013

Topical clustering

Schema Matching 36

■ Automatically determine cross-schema value correspondences between attributes ■ Traditionally: Input for data transformation and exchange tasks ■ For data profiling □ Determine closeness of two schemata □ Determine „schema fit“ ◊ Complement or union

Felix Naumann | Profiling & Cleansing | Summer 2013

Duplicate Detection and Record Linkage 37

■ Detect multiple (different) representations of the same real-world entity ■ Traditionally: Input for data cleansing and data fusion tasks ■ For data profiling □ Intra-source: Determine duplicity/cleanliness □ Inter-sources: Determine „data fit“ ◊ Complement or union

Felix Naumann | Profiling & Cleansing | Summer 2013

Together: Profiling for Integration 38

■ Create measures to estimate integration (and cleansing) effort □ Schema and data overlap □ Severity of heterogeneity ■ Schema matching/mapping □ What constitutes the “difficulty” of matching/mapping? ■ Duplicate detection □ Estimate data overlap □ Estimate fusion effort ■ Overall: Determine integration complexity and integration effort □ Intrinsic complexity: Schema and data □ Extrinsic complexity: Tools and expertise Felix Naumann | Profiling & Cleansing | Summer 2013

Cross-Schema Dependencies 39

■ Inclusion dependencies across schemata □ Join paths betwen data sources ■ Conditional INDs □ Typical pattern among crossreferencing sources ToyDB Catalog

EntityID

further data

Unit cost

DBName

ProdID

17

abcd…

200 USD

ToyDB

17

18

efgh…

50 EUR

ToyDB

18

1000 QAR

FashionDB

18

Felix Naumann | Profiling & Cleansing | Summer 2013

FashionDB EntityID

further data

18

abcd…

19

efgh…

Integration effort estimation 40 I

J

SS

T

Schema analysis (matching)

Integration specialist

Data analysis (profiling)

Complexity model

Integration tools (mapping & ETL)

Integration result

Tool capabilities

Measured effort

Production side

Effort model

Estimated effort

Estimation side

Felix Naumann | Profiling & Cleansing | Summer 2013

Topic discovery and clustering 41

■ What is a data set about? □ Domain(s), topics, entity types ■ Single-topic datasets □ GraceDB, IMDB, Sports databases, etc. ■ Multi-topic datasets □ General purpose knowledge bases: YAGO, Dbpedia □ Tables crawled from the Web ■ What is a topic? □ Wikipedia categories? ■ Topical clustering for □ Source selection, query processing Felix Naumann | Profiling & Cleansing | Summer 2013

Wikipedia Categories 42

Felix Naumann | Profiling & Cleansing | Summer 2013

Overview 43

■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profiling ■ Profiling challenges

Felix Naumann | Profiling & Cleansing | Summer 2013

Profiling Challenges 44

■ Scalable profiling ■ Holistic profiling ■ Incremental profiling ■ Online profiling ■ Profiling query results ■ Profiling new types of data ■ Data generation and testing ■ Data profiling benchmark

Each of these is worth one (or more) master‘s theses! Felix Naumann | Profiling & Cleansing | Summer 2013

Scalable profiling 45

■ Scalable in number of rows ■ Scalable in number of columns □ Number of column combinations is exponential □ Small table with 100 columns: 2100 – 1 = 1,267,650,600,228,229,401,496,703,205,376 = 1.3 nonillion combinations ◊ Impossible to check ◊ Impossible even to enumerate ■ Solutions □ Scale up: More RAM, faster CPUs ◊ Expensive □ Scale in: More cores ◊ More complex (threads) □ Scale out: More machines ◊ Communication overhead Felix Naumann | Profiling & Cleansing | Summer 2013

Holistic Profiling 46

■ Various profiling methods for various profiling tasks ■ Commonalities □ Search space: All column combinations (or pairs thereof) □ I/O: Read all data at least once □ Data structure: Some index or hash table □ Pruning and candidate generation: based on subset/superset relationships ■ Idea: Develop single method to output all/most profiling results

Felix Naumann | Profiling & Cleansing | Summer 2013

Incremental profiling 47

■ Data is dynamic □ Insert (batch or tuple-based) □ Updates □ Deletes ■ Problem: Keep profiling results up-to-date without reprofiling the entire data set □ Easy examples: SUM, MIN, MAX, COUNT, AVG □ Difficult examples: MEDIAN, uniqueness, FDs, etc.

Felix Naumann | Profiling & Cleansing | Summer 2013

Online profiling 48

■ Profiling is long procedure □ Boring for developer □ Expensive for machines (I/O and CPU) ■ Problem: Display intermediate results □ Of improving/converging accuracy □ Allow early abortion of profiling run ■ Gear algorithms toward that goal □ Allow intermediate output □ Enable early output (progressive profiling)

Felix Naumann | Profiling & Cleansing | Summer 2013

Profiling query results 49

■ Query results are boring: Spruce them up with some metadata □ Usually only: Row count □ For each column, give some statistics ◊ Uniqueness, histogram, AVG, etc. ◊ Show FDs ■ Idea: Piggy-back profiling on query execution □ Re-use sortations, hash tables, etc. Felix Naumann | Profiling & Cleansing | Summer 2013

Profiling new types of data 50

■ Traditional data profiling: Single table or multiple tables ■ More and more data in other models □ XML / nested relational / JSON □ RDF triples □ Textual data ◊ Blogs, Tweets, News ◊ In tables (CLOBS): Produkt descriptions, CVs, reviews □ Multimedia ■ All models offer new dimensions to profile □ Nestedness, measures at different nesting levels □ Graph structure, in- and outdegrees □ Sentiment, sentence structure, complexity, and other linguistic measures □ Color, video-length, volume, etc. Felix Naumann | Profiling & Cleansing | Summer 2013

Example: Text profiling 51

■ Statistical measures □ Syllables per word □ Sentence length □ Proportions of parts of speech ■ Vocabulary measures □ Frequencies of specific words □ Type-token ratio □ Simpson’s index (vocabulary richness) □ Number of hapax (dis)legomena ◊ Token that occurs exactly once (twice) in the corpus ◊ Characterize style of an author ■ Idea and following figures based on: □ „Literature Fingerprinting: A New Method for Visual Literary Analysis” by Daniel A. Keim and Daniela Oelke (IEEE Symposium on Visual Analytics Science and Technology 2007) Felix Naumann | Profiling & Cleansing | Summer 2013

Average sentence length 52

Felix Naumann | Profiling & Cleansing | Summer 2013

„Literature Fingerprinting: A New Method for Visual Literary Analysis” by Daniel A. Keim and Daniela Oelke

Hapax Legomena 53

Felix Naumann | Profiling & Cleansing | Summer 2013

„Literature Fingerprinting: A New Method for Visual Literary Analysis” by Daniel A. Keim and Daniela Oelke

Verse length 54

Felix Naumann | Profiling & Cleansing | Summer 2013

„Literature Fingerprinting: A New Method for Visual Literary Analysis” by Daniel A. Keim and Daniela Oelke

Data generation and testing 55

■ Generate volumes of data with certain properties □ Test extreme cases □ Test scalability ■ Problem: Interaction between properties □ FDs vs. uniqueness □ Patterns vs. conditional INDs □ Distributions vs. all others… ■ Problem: Create realistic data □ Distibutions, patterns □ Example: TPCH (see next slide) ■ Problem: Consistently produce same, randomized data Felix Naumann | Profiling & Cleansing | Summer 2013

TPCH – Uniques and Non-Uniques 56

■ Using the first 8 columns of the lineitems table

Felix Naumann | Profiling & Cleansing | Summer 2013

Data profiling benchmark 57

■ Define data □ Data generation □ Real-world dataset(s) □ Different scale-factors: Rows and columns ■ Define tasks □ Individual tasks □ Sets of tasks ■ Define measures □ Speed □ Speed/cost □ Minimum hardware requirements □ Accuracy for approximate approaches Felix Naumann | Profiling & Cleansing | Summer 2013

Summary 58

Data Profiling

Multiple sources

Single source

Single column

Multiple columns

Topical overlap

Schematic overlap

Data overlap

Cardinalities

Uniqueness and keys

Topic discovery

Schema matching

Duplicate detection

Uniqueness and keys

Inclusion and foreign key dep.

Topical clustering

Cross-schema dependencies

Record linkage

Patterns and data types

Functional dependencies

Distributions

Conditional and approximate dep.

Felix Naumann | Profiling & Cleansing | Summer 2013

Loading...

An Introduction to Data Profiling

An Introduction to Data Profiling 16.4.2013 Felix Naumann Overview 2 ■ Profiling tasks ■ Profiling tools ■ Visualization ■ Next generation profili...

2MB Sizes 35 Downloads 13 Views

Recommend Documents

An Introduction to Data Mining
A recent META Group survey of data warehouse projects found that 19% of respondents are beyond the 50 gigabyte level, wh

An introduction to data integration
5. Evolution from Application Servers. Data driven. Application servers. Enteprise Application Integration. (EAI). Extra

Criminal Profiling, Second Edition: An Introduction To Behavioral
Here you can easily download by Brent E. Turvey Criminal Profiling, Second. Edition: An Introduction To Behavioral Evide

Introduction to Data Warehousing
1. Introduction to Data. Warehousing. ▫ Why data warehousing? ▫ What is data warehousing? ▫ Characteristics of dat

An Introduction to Telugu
Linguists also determined that the four major southern Indian languages, namely Telugu, Tamil, Kannada and Malayalam bel

AN INTRODUCTION TO FERMENTATION
Fermentation is the term used by microbiologists to describe any process for the .... Growth rate is independent of subs

An Introduction to Plastics
Thermoplastics - these are plastics that can be softened and formed using heat, and when cool, will take ... Thermosetti

An Introduction to Optimization.pdf
Some of the exercises require using MATLAB. The student edition of MATLAB is sufficient for all of the MATLAB exercises

An Introduction to C++
Dedication. These notes are dedicated to the people who have implemented the gcc suite of software, to. Dinkumware and t

e-Books Box: Phonetic Data Analysis : An Introduction to Fieldwork
Oct 3, 2003 - e-Books Box: Phonetic Data Analysis : An Introduction to Fieldwork and Instrumental Techniques 97806312326